Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Created November 29, 2013 07:02
Show Gist options
  • Save mycodeschool/7702441 to your computer and use it in GitHub Desktop.
Save mycodeschool/7702441 to your computer and use it in GitHub Desktop.
/*
Evaluation Of postfix Expression in C++
Input Postfix expression must be in a desired format.
Operands must be integers and there should be space in between two operands.
Only '+' , '-' , '*' and '/' operators are expected.
*/
#include<iostream>
#include<stack>
#include<string>
using namespace std;
// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression);
// Function to perform an operation and return output.
int PerformOperation(char operation, int operand1, int operand2);
// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C);
// Function to verify whether a character is numeric digit.
bool IsNumericDigit(char C);
int main()
{
string expression;
cout<<"Enter Postfix Expression \n";
getline(cin,expression);
int result = EvaluatePostfix(expression);
cout<<"Output = "<<result<<"\n";
}
// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression)
{
// Declaring a Stack from Standard template library in C++.
stack<int> S;
for(int i = 0;i< expression.length();i++) {
// Scanning each character from left.
// If character is a delimitter, move on.
if(expression[i] == ' ' || expression[i] == ',') continue;
// If character is operator, pop two elements from stack, perform operation and push the result back.
else if(IsOperator(expression[i])) {
// Pop two operands.
int operand2 = S.top(); S.pop();
int operand1 = S.top(); S.pop();
// Perform operation
int result = PerformOperation(expression[i], operand1, operand2);
//Push back result of operation on stack.
S.push(result);
}
else if(IsNumericDigit(expression[i])){
// Extract the numeric operand from the string
// Keep incrementing i as long as you are getting a numeric digit.
int operand = 0;
while(i<expression.length() && IsNumericDigit(expression[i])) {
// For a number with more than one digits, as we are scanning from left to right.
// Everytime , we get a digit towards right, we can multiply current total in operand by 10
// and add the new digit.
operand = (operand*10) + (expression[i] - '0');
i++;
}
// Finally, you will come out of while loop with i set to a non-numeric character or end of string
// decrement i because it will be incremented in increment section of loop once again.
// We do not want to skip the non-numeric character by incrementing i twice.
i--;
// Push operand on stack.
S.push(operand);
}
}
// If expression is in correct format, Stack will finally have one element. This will be the output.
return S.top();
}
// Function to verify whether a character is numeric digit.
bool IsNumericDigit(char C)
{
if(C >= '0' && C <= '9') return true;
return false;
}
// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C)
{
if(C == '+' || C == '-' || C == '*' || C == '/')
return true;
return false;
}
// Function to perform an operation and return output.
int PerformOperation(char operation, int operand1, int operand2)
{
if(operation == '+') return operand1 +operand2;
else if(operation == '-') return operand1 - operand2;
else if(operation == '*') return operand1 * operand2;
else if(operation == '/') return operand1 / operand2;
else cout<<"Unexpected Error \n";
return -1;
}
@hungnguyen1895
Copy link

@snehaagarwal625: the operand variable will store one - two digit number.
expression[i] - '0' is just a way to convert from char to int.

@MOHAMMED-ABD-RAZAQ
Copy link

complete
last update
thanks

@sid-fireskull
Copy link

@jaychou0129
Copy link

@Mushi123
I just stopped by...
You can check an ASCII table for reference. The characters '0' through '9' match the decimal code of 48 to 57 correspondingly.
So if
char c1='2';
char c2='4';
Then c1 + c2 = 50 + 52 = 102

@suresh68
Copy link

// check this out complete code in c

#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#include<stdlib.h>
struct node
{
int data;
struct node* next;
};
struct node* top = NULL;
void push(int x)
{
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->data = x;
temp->next = top;
top = temp;
}
int pop()
{
int data;
struct node* temp = top;
if(top == NULL)
{
return -1;
}
temp = top;
data = top->data;
top = top->next;
free(temp);
return data;
}
bool isoperator(char x)
{
if(x=='+'||x=='-'||x==''||x=='/')
return true;
return false;
}
bool isnumericdigit(char x)
{
if(x>='0'&&x<='9')
return true;
return false;
}
int preop(char x,int operand1,int operand2)
{
if(x=='+')
return operand1+operand2;
else if(x=='-')
return operand1-operand2;
else if(x=='
')
return operand1operand2;
else if(x=='/')
return operand1/operand2;
else
{
printf("invalid operator\n");
return -1;
}
}
int evalpostfix(char arr,int len)
{
int i;
for(i=0;i<len;i++)
{
if(
(arr+i)==' '||
(arr+i)==',')
continue;
else if(isnumericdigit((arr+i)))
{
int operand = 0;
while(i<len && isnumericdigit(
(arr+i)))
{
operand = ((arr+i)-'0');
i++;
}
i--;
push(operand);
}
else if(isoperator(
(arr+i)))
{
int res;
int operand2 = pop();
int operand1 = pop();
res = preop(*(arr+i),operand1,operand2);
push(res);
}
}
return top->data;
}
int main()
{
char arr[20];
int res,length;
printf("enter the postfix expression: ");
gets(arr);
puts(arr);
length = strlen(arr);
printf("%d\n",length);
res = evalpostfix(arr,length);
printf("result = %d",res);
return 0;
}

@mehransaeed7810
Copy link

why have you multiply operand with 10

@mafsan786git
Copy link

mafsan786git commented Feb 11, 2019

why have you multiply operand with 10 @mehransaeed7810

bcse in program he used string to read every character so if we have 123 then 1st character is 1 and we would check whether it is integer or operator if it is integer then we have to multiply by 10 every time read all 1 ,2, 3 and then do that 1100+210+3*1, just check the problem based on reverse of number .

@Ivoo25
Copy link

Ivoo25 commented May 11, 2019

Hey does anybody has something simillar but with variables?
Like a =4; b= 7 then a+b or simillar?

@sauravgpt
Copy link

Why -'0' in line 64

because it will typecast character to an integer type.

@aravindmedamoni
Copy link

1

else if(IsNumericDigit(expression[i])){
  | // Extract the numeric operand from the string
  | // Keep incrementing i as long as you are getting a numeric digit.
  | int operand = 0;
  | while(i<expression.length() && IsNumericDigit(expression[i])) {
  | // For a number with more than one digits, as we are scanning from left to right.
  | // Everytime , we get a digit towards right, we can multiply current total in operand by 10
  | // and add the new digit.
  | operand = (operand*10) + (expression[i] - '0');
  | i++;
  | }
  | // Finally, you will come out of while loop with i set to a non-numeric character or end of string
  | // decrement i because it will be incremented in increment section of loop once again.
  | // We do not want to skip the non-numeric character by incrementing i twice.
  | i--;
  |  
  | // Push operand on stack.
  | S.push(operand);
  | }

i dint understand this part of the code .....pls explain me this part word by word
you have not mentioned this part in your you video so i dint understand....
and if possible can you please give me a c code for this????

actually it is write to check more than one digit number in our expression but its not working, here logic is incorrect, for loop and while loops never end so we will get segmentation fault..

@asad2200
Copy link

Here is java code
`
import java.util.Scanner;
import java.util.Stack;

public class EvaluationPostfix {
static int operation(char operator,int op1,int op2){
switch(operator){
case '/':
return op1/op2;
case '':
return op1
op2;
case '+':
return op1+op2;
case '-':
return op1-op2;
}
return 0;
}
static boolean isDigit(char c){
if('0' <= c && '9' >= c)
return true;
return false;
}
static int evaluate(String exp){
Stack st = new Stack<>();
char arr[] = exp.toCharArray();
int op1,op2;
for(int i=0;i<exp.length();i++){
if(arr[i] == ' ' || arr[i] == ',')
continue;
else if(arr[i] == '' || arr[i] == '/' || arr[i] == '+' || arr[i] == '-'){
op2=st.pop();
op1=st.pop();
st.push(operation(arr[i],op1,op2));
}else if(isDigit(arr[i])) {
int operand = 0;
while(i<exp.length() && isDigit(arr[i])){
operand = (operand
10) + (arr[i]-'0');
i++;
}
i--;
st.push(operand);
}
}
return st.pop();
}

public static void main(String[] args) throws Exception {
    System.out.println("Insert PostFix expression");
    Scanner sc = new Scanner(System.in);
    String exp = sc.nextLine();
    sc.close();
    System.out.println("Answer is "+evaluate(exp));
}

}`

@Adarshv194
Copy link

Java Prefix Evaluation code
import java.util.Scanner;
class PrefixEvaluation
{
String exp;
int []stack;
int top;
public PrefixEvaluation()
{
top=-1;
Scanner inp = new Scanner(System.in);
exp = inp.nextLine();
stack = new int[exp.length()];
}
public void push(int n)
{
stack[++top] = n;
}
public int pop()
{
return stack[top--];
}
public void evaluate()
{
for(int i=exp.length()-1;i>=0;i--)
{
char ch = exp.charAt(i);
if(ch == ' ')
{
// do nothing
}
else if(Character.isDigit(ch))
{
int temp_top=top;
int n=0;
while(Character.isDigit(ch))
{
n = (int)(ch - '0');
push(n);
i--;
ch = exp.charAt(i);
}
i++;
if(top!=temp_top)
{
n=0;
while(top!=temp_top)
{
n = n10 + pop();
}
push(n);
}
}
else
{
int result;
int val1 = pop();
int val2 = pop();
switch(ch)
{
case '+' :
result = val1 + val2;
push(result);
break;
case '
' :
result = val1 * val2;
push(result);
break;
case '/' :
result = val1 / val2;
push(result);
break;
case '-' :
result = val1 - val2;
push(result);
break;
}
}
}
System.out.println("String length "+exp.length());
System.out.println("Top is at "+top);
System.out.println("Answer of the expression is "+stack[top]);
}
public static void main(String []args)
{
PrefixEvaluation ex = new PrefixEvaluation();
ex.evaluate();
}
}

@arsharaj
Copy link

arsharaj commented May 10, 2020

Here is my implemetation for the same problem in C++

// Include all the required files
#include<iostream>
#include<stack>

// Define the namespace for standard library
using namespace std;

// Evaluates the result in the postfix expression.
int EvaluateResult(int operand1, int operand2, char symbol){
  if(symbol=='+') return operand1+operand2;       // Addition
  else if(symbol=='-') return operand1-operand2;  // Subtraction
  else if(symbol=='*') return operand1*operand2;  // Multiplication
  else if(symbol=='/') return operand1/operand2;  // Division
  else if(symbol=='%') return operand1%operand2;  // Modulus
  else if(symbol=='^') return operand1^operand2;  // Exponentiation
  else return -1;
}

// Evaluate PostFix expression using the stack algorithm methodology.
// Return -1 of invalid expression is given otherwise return the result.
int EvaluatePostfix(string expression){
  int i,num=-1;             // Variable declarations
  stack<int> temp_stack;

  for(i=0;i<expression.length();i++){ // Iterate over characters

    int mychar=expression[i];

    if(mychar==','){  // Delimiter comma handling
      if(num!=(-1)){
        temp_stack.push(num);
        num=-1;
      }
      continue;
    }else if(mychar-'0' <= 9 && mychar-'0' >= 0){  // Numbers handling 
      if(num==-1){
        num=mychar-'0'; // Find the exact number from the character
      }else{
        num=num*10+(mychar-'0');  // Number is greater than 1 digit.
      }
    }else if(mychar=='+'||mychar=='-'||mychar=='*'||mychar=='/'||mychar=='^'||mychar=='%'){  
      // Operating on the given symbols

      // Main Algorithm for the evaluation of result
      if(temp_stack.empty()) return -1;
      int operand2=temp_stack.top();
      temp_stack.pop();

      if(temp_stack.empty()) return -1;
      int operand1=temp_stack.top();
      temp_stack.pop();

      // Pop two previous elements from the stack and push their result onto stack again.
      temp_stack.push(EvaluateResult(operand1,operand2,mychar));
    }else{
      cout<<"Invalid operand";
    }
  }

  return temp_stack.top();
} // End of evaluation postfix

Include the main function as per your need. I have made a function to do the job :-)

@nik-maheshwari19
Copy link

Why do we need Linked List to store the data of Top element of the stack?

@nik-maheshwari19
Copy link

if(expression[i] == ' ' || expression[i] == ',') continue;
This line causing the error. So, I have to give input like "87-" with no space between and I can only use single-digit numbers. How to solve this Problem?

@arsharaj
Copy link

arsharaj commented Jun 13, 2020 via email

@vaibhavs017
Copy link

vaibhavs017 commented Jul 5, 2020

Why -'0' in line 64

Because 0 in ASCII table is referred as 48 in decimal and 9 as 54 in decimal notation form.
Hence when evaluating the char to get integers this is very nice way of doing .

@abhisheknaw
Copy link

@arsharaj what function/work does this portion of your code do?
if(mychar==','){ // Delimiter comma handling
if(num!=(-1)){
temp_stack.push(num);
num=-1;
}
plzz can u explain?

@GrezzyTap
Copy link

The fact that '0' is 48, is it like a built in value? so if I write a program like:
char c1='2';
char c2='4';
then would c1+c2=6?

int x=c1+c2;
above expression will result in 102
so to get 6 do the following,
int x=c1+c2-2*'0';

@Malikhaidar
Copy link

evaluate expression to postfix() method 12 38 + 5 * with algorithm.
solution?

@kesava-karri
Copy link

sir this code is not debuging

Don't forget to give the input in post fix form...

@kesava-karri
Copy link

kesava-karri commented Oct 31, 2020

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int do_operation(int op2, int op1, char opr);
bool is_operator(char C);
bool is_operand(char C);

int evaluatePostfix(string exp) {
    stack<int> S;
    for(int i=0; i<exp.length(); i++) {
        if(exp[i] == ' ' || exp[i] ==',') {
            continue;
        }
        else if(is_operand(exp[i])) {
            int operand = 0;
            while(is_operand(exp[i])) {
                operand = operand*10 + exp[i] - '0' ;
                i++;
            }
            i--;
            S.push(operand);
        }

        else if(is_operator(exp[i])) {
            int op2 = S.top(); 
            S.pop();
            int op1 = S.top();
            S.pop();
            int result = do_operation(op2, op1, exp[i]);
            S.push(result);
        }
    }
    return S.top();
}

int do_operation(int op2, int op1, char opr) {
    if(opr == '/') return op1/op2;
    else if(opr == '*') return op1*op2;
    else if(opr == '+') return op1+op2;
    else if(opr == '-') return op1-op2;
    else {
        return -1;
    }
}

bool is_operator(char C) {
    if(C == '/' or '*' or '+' or '-') {
        return true;
    }
    else 
        return false;
}

bool is_operand(char C) {
    if(C>='0' && C<='9') {
        return true;
    }
    else 
        return false;
}

int main() {
    cout << evaluatePostfix("12 38 + 5 *"); // The input should be in postfix form
}

evaluate expression to postfix() method 12 38 + 5 * with algorithm.
solution?

@Malikhaidar

@akshittrivedi007
Copy link

Why -'0' in line 64

Because of ASCII value , reference with 0

@soumyabag
Copy link

Hey can you leave the C code for it please?

#include<stdio.h>
#include<string.h>
#define MAX 30
struct stack
{
char str[MAX];
int top;
}s;

int checkoperand(char ch)
{
if(ch>='0' && ch<='9')
return 1;
return 0;
}

int operator(char ch)
{
if(ch=='*' || ch=='+' || ch=='/' || ch=='-')
return 1;
return 0;
}

void push(int data)
{
s.top++;
s.str[s.top]=data;
}

char peek()
{
return s.str[s.top];
}

void pop()
{
s.top--;
}

int operation(int x, int y, char op)
{
if(op == '+')
return y+x;
else if(op == '-')
return y-x;
else if(op == '')
return y
x;
else if(op == '/')
return y/x;
else
return 0;
}

void evaluation()
{
int i,x,y;
char postfix[MAX];
printf("Enter postfix: ");
scanf("%s",&postfix);
for(i=0;i<strlen(postfix);)
{
if(checkoperand(postfix[i]))
push(postfix[i++]-'0');
else if(operator(postfix[i]))
{
x=peek();
pop();
y=peek();
pop();
push(operation(x,y,postfix[i]));
i++;
}
}
printf("%d",s.str[s.top]);
}

int main()
{
s.top=-1;
evaluation();
return 0;
}

@Ishikanagar07
Copy link

Ishikanagar07 commented May 26, 2021

I made minor changes in this code
It works fine now
Segementation error removed

/*
Evaluation Of postfix Expression in C++
Input Postfix expression must be in a desired format.
Operands must be single-digit integers and there should be space in between two operands.
Only '+' , '-' , '*' and '/' operators are expected.
*/

#include
#include
#include

using namespace std;

// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression);

// Function to perform an operation and return output.
int PerformOperation(char operation, int operand1, int operand2);

// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C);

// Function to verify whether a character is numeric digit.
bool IsNumericDigit(char C);

int main()
{
string expression;
cout<<"Enter Postfix Expression \n";
getline(cin,expression);
int result = EvaluatePostfix(expression);
cout<<"Output = "<<result<<"\n";
}

// Function to evaluate Postfix expression and return output
int EvaluatePostfix(string expression)
{
// Declaring a Stack from Standard template library in C++.
stack S;

for(int i = 0;i< expression.length();i++) {

	// Scanning each character from left. 
	// If character is a delimitter, move on. 
	if(expression[i] == ' ' || expression[i] == ',') continue; 

	// If character is operator, pop two elements from stack, perform operation and push the result back. 
	else if(IsOperator(expression[i])) {
		// Pop two operands. 
		int operand2 = S.top(); S.pop();
		int operand1 = S.top(); S.pop();
		// Perform operation
		int result = PerformOperation(expression[i], operand1, operand2);
		//Push back result of operation on stack. 
		S.push(result);
	}


           else if(IsNumericDigit(expression[i])) {		    
                    int operand;		    
                    operand = expression[i] - '0';	
			
                   // Push operand on stack. 			
                   S.push(operand);		
             }

}
// If expression is in correct format, Stack will finally have one element. This will be the output. 
return S.top();

}

// Function to verify whether a character is numeric digit.
bool IsNumericDigit(char C)
{
if(C >= '0' && C <= '9') return true;
return false;
}

// Function to verify whether a character is operator symbol or not.
bool IsOperator(char C)
{
if(C == '+' || C == '-' || C == '*' || C == '/')
return true;

return false;

}

// Function to perform an operation and return output.
int PerformOperation(char operation, int operand1, int operand2)
{
if(operation == '+') return operand1 +operand2;
else if(operation == '-') return operand1 - operand2;
else if(operation == '*') return operand1 * operand2;
else if(operation == '/') return operand1 / operand2;

else cout<<"Unexpected Error \n";
return -1; 

}

// here we are only considering single-digit integers, because if we start considering integers > 9 then 2 single-digit integer might get interpreted as 1 two-digit integer and we will get segmentaion error (because PerformOperation function is expecting two integers in stack whereas only 1 is found)

@vk7024
Copy link

vk7024 commented Jun 4, 2021

Why -'0' in line 64
为了把字符转换成数字

@Ishikanagar07
Copy link

char in C++ evaluates to the decimal equivalent.
'0' is 48
'1' is 49
'2' is 50
.
.
.
if expression[i] = '2' which evaluates to 50
so (expression[i] - '0') in this case will be (50 - 48) = 2

@nofrie
Copy link

nofrie commented Aug 26, 2022

The reason segmentation fault happens is that you don't put space between each operand.
For example, if you type: "11+", it's buggy. It must be "1 1+" or "1 1 +".
By applying this logic, it can count up multi digits numbers.

@saku123hh
Copy link

Here is my implemention, I have fixed the while loop error:
#include
using namespace std;
#include
#include

bool IsOperator(char x) {
if (x == '+' || x == '-' || x == '*') {
return true;
}
return false;
}

bool IsOperand(char x) {
// cout<<"x"<<x<<endl;
if (x <= '9' && x >= '0') return true;
return false;

}

int PerformOperation(char c, int x, int y) {
if (c == '+') return(x + y);
else if (c == '-') return(x - y);
else if (c == '*') return(x * y);
else cout << "unexpected error" << endl;
return -1;
}

void Print(stack S) {
while (!S.empty()) {
cout << S.top() << endl;
S.pop();
}
cout << "" << endl;
}

int EvaluatePostfix(string expression) {
stack S;

for (int i = 0; i < expression.length(); i++) {
    // cout<<IsOperator(expression[i])<<endl;
   //  cout<<IsOperand(expression[i])<<endl;
    if (expression[i] == ' ' || expression[i] == ',') continue;
    else if (IsOperator(expression[i])) {
        int operand2 = S.top(); S.pop();
        if (S.empty()) { cout << "Error: check your postfix" << endl; return -1; }
        int operand1 = S.top(); S.pop();
        int result = PerformOperation(expression[i], operand1, operand2);
        S.push(result);
        cout << "进入operatorS is:" << endl;
        Print(S);
    }

    else if (IsOperand(expression[i])) {
        int operand = 0;
        while (IsOperand(expression[i]) && i < expression.length()) {
            operand = operand * 10 + (expression[i] - '0');
            i++;
            cout << i << endl;
        }
        i--;  //比如35 6+ 在遇到5后i++=2 在这次程序结束后还要自动+1 会跳过对i=2的判断  所以需要-1
        S.push(operand);
        cout << "进入operand S is:" << endl;
        Print(S);
    }


    //  cout << i << endl;
}
return S.top();

}

int main()
{
cout << "input postfix" << endl;
string expression;
// cin>>expression;
getline(cin, expression);
cout << "expression:" << expression << endl;
int result = EvaluatePostfix(expression);
cout << "result is " << result << endl;

}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment