Evaluation of Postfix Expression Using Stack

In order to solve a complex expression, we first convert the expression from infix to postfix. This is done because the evaluation of postfix expression does not involve parenthesis. Evaluation of postfix expression can be easily done using stack.

Algorithm

  1. Initialize an empty stack.
  2. Scan postfix expression from left to right.
    1. If the scanned character is an operand, then push it to the stack.
    2. If the scanned character is an operator, then pop operands from the stack. Perform the operation and push the result back to the stack.
  3. Repeat step 2 till all characters of infix are read.
  4. In the end, the stack will contain only 1 value, that is the answer to the postfix expression.

Note:

  1. The number of operands pop depends upon the type of operator (2 for binary, 1 for unary, etc).
  2. The operands popped are placed right to left. For example, if the scanned character is “+” then we pop 2 operands from stack. The first popped operand is v1 and the second operand is v2. The “+” operation is performed as “v2+v1”.

Pseudo Code

postfix: post expression
stack: initially empty stack
token: stores scanned character at each iteration

FOR i = 1 TO postfix.LENGTH DO
	token := postfix[i]
	IF token is operand THEN
		PUSH token to stack
	ELSE IF token is operator THEN
		POP operands from stack.
		Perform the operation
		PUSH the result to stack
	END
END FOR

Code

#include<iostream>
#include<stack>
#include<math.h>
using namespace std;

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

bool isOperator(char t) {
	switch (t) {
	case '+':
	case '-':
	case '/':
	case '*':
	case '^':
		return true;
	}
	return false;
}

int evaluatePostfixExpression(string postfix){
	stack<int> stk;
	char token;
	
	for(int i=0;i<postfix.length();++i){
		token = postfix[i];
		if(isOperand(token)){
			stk.push(token-'0'); // substracting '0' converts token to it's equivalent integer
		}
		else if(isOperator(token)){
			// since we are only using bianry operators
			// we can pop stack before knowing the operator
			// in case out postfix contain multiple types of operators (unary,binary,ternary,...)
			// we pop operands only after checking the operator
			int v1,v2;
			v1 = stk.top();
			stk.pop();
			v2 = stk.top();
			stk.pop();
			
			switch(token){
				case '+': 
					stk.push(v2+v1);
					break;
				case '-': 
					stk.push(v2-v1);
					break;
				case '*': 
					stk.push(v2*v1);
					break;
				case '/': 
					stk.push(v2/v1);
					break;
				case '^': 
					stk.push(pow(v2,v1));
					break;
			}
		}
	}
	return stk.top();
}

int main(){
	string postfix;
	cout<<"Enter Postfix Expression: ";
	cin>>postfix;
	cout<<"The result is: "<<evaluatePostfixExpression(postfix)<<endl;
}


Output

Enter Postfix Expression: 12323^^*+62/4*-
The result is: 13111

Note: In the above program, we have assumed operands to be between 0 to 9. If we want the program to work for all numbers, we need to use some separator.

Step-by-Step Example

Now, we solve the Postfix expression “12323^^*+62/4-“ step-by-step.

Postfix ExpressionStackDescription
12323^^*+62/41Push 1 to stack.
2323^^*+62/41,2Push 2 to stack.
323^^*+62/41,2,3Push 3 to stack.
23^^*+62/41,2,3,2Push 2 to stack.
3^^*+62/41,2,3,2,3Push 3 to stack.
^^*+62/41,2,3,8op1 = stack top (3)
Pop stack.
op2 = stack top (2)
Pop stack.
Push op2 ^ op1 (2^3) to stack .
^*+62/41,2,6561op1 = stack top (8)
Pop stack.
op2 = stack top (3)
Pop stack.
Push op2 ^ op1 (3^8) to stack.
*+62/41,13122op1 = stack top (6561)
Pop stack.
op2 = stack top (2)
Pop stack.
Push op2 ^ op1 (2*6561) to stack.
+62/413123op1 = stack top (13122)
Pop stack.
op2 = stack top (1)
Pop stack.
Push op2 + op1 (1+13122) to stack.
62/413123,6Push 6 to stack.
2/413123,6,2Push 2 to stack.
/4*-13123,3op1 = stack top (2)
Pop stack.
op2 = stack top (6)
Pop stack.
Push op2 + op1 (6/2) to stack.
4*-13123,3,4Push 4 to stack
*13123,12op1 = stack top (4)
Pop stack.
op2 = stack top (3)
Pop stack.
Push op2 + op1 (3*4) to stack.
13111op1 = stack top (12)
Pop stack.
op2 = stack top (13123)
Pop stack.
Push op2 + op1 (13123-12) to stack.
evaluation of postfix expression using stack

References

https://simple.wikipedia.org/wiki/Postfix_notation

Leave a Comment

Your email address will not be published. Required fields are marked *