For evaluating an arithmetic expression, we need to convert it into prefix or postfix notation. I have talked about it in this post. Here also we will use a stack data structure to evaluate prefix and postfix expressions.
Evaluation of Postfix Expression
Input: 3 6 4 + * 5 /
Output: 6
Algorithm to evaluate postfix expression
- Scan the postfix expression from left to right.
- If the scanned character is an operand, then push it to the stack.
- Else if the scanned character is an operator, pop two operands from the top of the stack and evaluate them with the scanned operator and push the result into the stack. (Note: here evaluation should be second_pop_operand operator first_pop_operand.)
- Repeat steps 2 and 3 until all the characters in the postfix expression are scanned.
- Print the final result from the top of the stack.
Step by step evaluation of postfix expression “3 6 4 + * 5 /” is shown below in the table,
Steps |
Scanned Character |
Stack |
Action |
Initially |
|
[Empty Stack] |
|
1 |
3 |
3 |
Push 3 |
2 |
6 |
3,6 |
Push 6 |
3 |
4 |
3,6,4 |
Push 4 |
4 |
+ |
3,10 |
Pop 4, Pop 6 and Push 6+4 = 10 |
5 |
* |
30 |
Pop 10, Pop 3 and Push 3*10= 30 |
6 |
5 |
30,5 |
Push 5 |
7 |
/ |
6 |
Pop 5, Pop 30 and Push 30/5 = 6 |
Final Result:- |
6 |
- C/C++
- Python
- Java
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
// Check if a character is operator or not.
int operators(char ch)
{
if (ch == '^' || ch == '/' || ch == '*' || ch == '+' || ch == '-' || ch == '(')
{
return 1;
}
return 0;
}
int evaluate(char op, int e1, int e2)
{
switch (op)
{
case '^':
return pow(e1, e2);
case '*':
return e1 * e2;
case '/':
return e1 / e2;
case '+':
return e1 + e2;
case '-':
return e1 - e2;
}
return 0;
}
int evalPostfix(string expression)
{
stack<int> Stack;
istringstream stm(expression);
string expr;
while (stm >> expr)
{
if (operators(expr[0]))
{
int a = Stack.top();
Stack.pop();
int b = Stack.top();
Stack.pop();
int res = evaluate(expr[0], b, a);
Stack.push(res);
}
else
Stack.push(stoi(expr));
}
return Stack.top();
}
int main()
{
string expr = "3 6 4 + * 5 /";
cout << "Postfix: " << expr << endl;
cout << "Result: " << evalPostfix(expr);
}
Evaluation of Prefix expression
Input: * 3 / + 6 4 5
Output: 6
Algorithm to Evaluate Prefix Expression
Steps to evaluate prefix expression is same as evaluation of postfix expression with one additional step i.e. step 1.
- Reverse the prefix expression.
- Scan the reversed prefix expression from left to right.
- If the scanned character is an operand, then push it to the stack.
- Else if the scanned character is an operator, pop two operands from the top of the stack and evaluate them with the scanned operator and push the result into the stack. (Note: here evaluation should be first_pop_operand operator second_pop_operand.)
- Repeat steps 2 and 3 until all the characters in reversed prefix expression are scanned.
- Print the final result from the top of the stack.
Step by step evaluation of prefix expression “* 3 / + 6 4 5” is shown below in the table. In step 1, the prefix expression is reversed and hence the new expression becomes “5 4 6 + / 3 *”.
Steps |
Scanned Character |
Stack |
Action |
Initially |
|
[Empty Stack] |
|
1 |
5 |
5 |
Push 5 |
2 |
4 |
5,4 |
Push 4 |
3 |
6 |
5,4,6 |
Push 6 |
4 |
+ |
5,10 |
Pop 6, Pop 4 and Push 6+4 = 10 |
5 |
/ |
2 |
Pop 10, Pop 5 and Push 10/5 = 30 |
6 |
3 |
2,3 |
Push 3 |
7 |
* |
6 |
Pop 3, Pop 2 and Push 3*2 = 6 |
Final Result:- |
6 |
- C/C++
- Python
- Java
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
// Check if a character is operator or not.
int operators(char ch)
{
if (ch == '^' || ch == '/' || ch == '*' || ch == '+' || ch == '-' || ch == '(')
{
return 1;
}
return 0;
}
int evaluate(char op, int e1, int e2)
{
switch (op)
{
case '^':
return pow(e1, e2);
case '*':
return e1 * e2;
case '/':
return e1 / e2;
case '+':
return e1 + e2;
case '-':
return e1 - e2;
}
return 0;
}
int evalPostfix(string expression)
{
reverse(expression.begin(), expression.end());
stack<int> Stack;
istringstream stm(expression);
string expr;
while (stm >> expr)
{
if (operators(expr[0]))
{
int a = Stack.top();
Stack.pop();
int b = Stack.top();
Stack.pop();
int res = evaluate(expr[0], a, b);
Stack.push(res);
}
else
Stack.push(stoi(expr));
}
return Stack.top();
}
int main()
{
string expr = "* 3 / + 6 4 5";
cout << "Postfix: " << expr << endl;
cout << "Result: " << evalPostfix(expr);
}