给定一个反波兰表示法的表达式，对其进行求值并获得C ++的输出

以反波兰表示法，操作数将紧随运算符之后。

例如，

2 – 3 以相反的波兰语表示将是 2 3 –

4 + 5–6将被写为4 5 + 6–

解决方案说明：

我们可以通过使用堆栈来解决。考虑下面的示例：

5 4 + 6 *

可以如下评估：

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

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;
}

输出：

The solution is = 54