ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Given an expression in reverse polish notation, evaluate it and get the output in C++

prodevelopertutorial March 5, 2019

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

 

 

 

Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io