In reverse polish notation, operands will be first followed by operators.
For example,
2 – 3 in reverse polish notation will be 2 3 –
4 + 5 – 6 will be written as 4 5 + 6 –
Solution explanation:
We can solve this by using stacks. Consider example below:
5 4 + 6 *
It can be evaluated as below:
Token Type Stack Action 5 Operand 5 Add 5 to stack 4 Operand 4 Add 4 to stack + Operator 9 Pop 2 numbers and add them [5 + 4] = 9 6 Operand 9 6 Add 6 to stack * Operator 54 Pop 2 numbers and multiply [9 * 6] = 54
Solution in C++
#include<iostream> #include<vector> #include<string> #include<stack> using namespace std; int evaluate_reverse_polish_notation_using_stacks(vector<string>& notation) { stack<int> s; for (auto a : notation) { // check if it is an operator if (a.size() == 1 && !isdigit(a[0])) { // if it is operator, pop 2 times, then perform appropriate operation int num2 = s.top(); s.pop(); int num1 = s.top(); s.pop(); switch (a[0]) { // note switch use char or integer case '+': s.push(num1 + num2); break; case '-': s.push(num1 - num2); break; case '*': s.push(num1 * num2); break; case '/': s.push(num1 / num2); break; } } else { // if it number, push it to stack s.push(atoi(a.c_str())); } } return s.top(); } int main() { vector<string> notation; notation.push_back("5"); notation.push_back("4"); notation.push_back("+"); notation.push_back("6"); notation.push_back("*"); cout<<"The solution is = "<<evaluate_reverse_polish_notation_using_stacks(notation)<<endl; }
Output:
The solution is = 54