Problem Statement:
You are given an postfix expression, you need to evaluate that expression.
Postfix expressions are in the form of a b op.
Example
Input:
2 3 1 * + 9 –
Output: -4
Solution
To solve this, we will make use of stacks.
Create a stack to store the values.
Then start scanning the given expression,
-> if the element is a number, push into stack
-> if it is a operator, then pop the values from stack and evaluate the result and push back to stack.
The last number stored in the stack is the final result.
Example:
Consider the expression “2 3 1 * + 9 -“
“2” push into the stack. Current stack elements “2”
“3” push into the stack. Current stack elements “2 3”
“1” push into the stack. Current stack elements “2 3 1”
“*” pop 2 elements from the stack. “3 1”. So “3 * 1 = 3”. Push 3 into stack. Current stack elements “2 3”
“+” pop 2 elements from the stack. “2 3”. So “3 + 2 = 5”. Push 5 into stack. Current stack elements “5”
“9” push into the stack. Current stack elements “5 9”
“-” pop 2 elements from the stack. “5 9”. So “5 – 9 = -4”. Push -4 into stack. Current stack elements “-4”
Hence the solution is -4
Solution in C++
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
int evaluate_postfix_exp(string exp)
{
stack<int> stack;
for (int i = 0; i < exp.length(); i++)
{
if (exp[i] >= '0' && exp[i] <= '9')
{
stack.push(exp[i] - '0');
}
else
{
int x = stack.top();
stack.pop();
int y = stack.top();
stack.pop();
if (exp[i] == '+') {
stack.push(y + x);
}
else if (exp[i] == '-') {
stack.push(y - x);
}
else if (exp[i] == '*') {
stack.push(y * x);
}
else if (exp[i] == '/') {
stack.push(y / x);
}
}
}
return stack.top();
}
int main()
{
string exp = "231*+9-";
cout << evaluate_postfix_exp(exp);
return 0;
}
Output:
-4