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
- Initialize an empty stack.
- Scan postfix expression from left to right.
- If the scanned character is an operand, then push it to the stack.
- If the scanned character is an operator, then pop operands from the stack. Perform the operation and push the result back to the stack.
- Repeat step 2 till all characters of infix are read.
- In the end, the stack will contain only 1 value, that is the answer to the postfix expression.
Note:
- The number of operands pop depends upon the type of operator (2 for binary, 1 for unary, etc).
- 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 Expression | Stack | Description |
---|---|---|
12323^^*+62/4– | 1 | Push 1 to stack. |
2323^^*+62/4– | 1,2 | Push 2 to stack. |
323^^*+62/4– | 1,2,3 | Push 3 to stack. |
23^^*+62/4– | 1,2,3,2 | Push 2 to stack. |
3^^*+62/4– | 1,2,3,2,3 | Push 3 to stack. |
^^*+62/4– | 1,2,3,8 | op1 = stack top (3) Pop stack. op2 = stack top (2) Pop stack. Push op2 ^ op1 (2^3) to stack . |
^*+62/4– | 1,2,6561 | op1 = stack top (8) Pop stack. op2 = stack top (3) Pop stack. Push op2 ^ op1 (3^8) to stack. |
*+62/4– | 1,13122 | op1 = stack top (6561) Pop stack. op2 = stack top (2) Pop stack. Push op2 ^ op1 (2*6561) to stack. |
+62/4– | 13123 | op1 = stack top (13122) Pop stack. op2 = stack top (1) Pop stack. Push op2 + op1 (1+13122) to stack. |
62/4– | 13123,6 | Push 6 to stack. |
2/4– | 13123,6,2 | Push 2 to stack. |
/4*- | 13123,3 | op1 = stack top (2) Pop stack. op2 = stack top (6) Pop stack. Push op2 + op1 (6/2) to stack. |
4*- | 13123,3,4 | Push 4 to stack |
*– | 13123,12 | op1 = stack top (4) Pop stack. op2 = stack top (3) Pop stack. Push op2 + op1 (3*4) to stack. |
– | 13111 | op1 = stack top (12) Pop stack. op2 = stack top (13123) Pop stack. Push op2 + op1 (13123-12) to stack. |
References
https://simple.wikipedia.org/wiki/Postfix_notation