Evaluate Reverse Polish Notation(逆波兰式的计算)
最后更新于:2022-04-01 22:56:30
**一. 题目描述**
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
`["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9`
`["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6`
**二. 题目分析**
该题考查逆波兰式,也叫后缀表达式(将运算符写在操作数之后)。假设有一个表达式E,其后缀形式定义如下:
1. 如果E是一个变量或常量,则E的后缀式是E本身;
2. 如果E是E1 operator E2形式的表达式,这里 operator 是如何二元操作符,则E的后缀式为E1, E2,
operator;
3. 如果E是 (E1) 形式的表达式,则 E1 的后缀式就是E的后缀式。
一个实际例子如下:
下面以`(a+b)*c`为例子进行说明:
`(a+b)*c`的逆波兰式为`ab+c*`,假设计算机把`ab+c*`按从左到右的顺序压入栈中,并且按照遇到运算符就把栈顶两个元素出栈,执行运算,得到的结果再入栈的原则来进行处理,那么`ab+c*`的执行结果如下:
1. a入栈(0位置);
2. b入栈(1位置);
3. 遇到运算符`“+”`,将`a`和`b`出栈,执行`a+b`的操作,得到结果`d=a+b`,再将`d`入栈(0位置);
4. c入栈(1位置);
5. 遇到运算符`“*”`,将`d`和`c`出栈,执行`d*c`的操作,得到结果`e`,再将`e`入栈(0位置)。
经过以上运算,计算机就可以得到`(a+b)*c`的运算结果`e`了。
逆波兰式计算等式的实现非常容易,使用堆栈即可完成。在程序中,需要实现整数与字符串之间的相互转换。
**三. 示例代码**
~~~
#include
#include
#include
using namespace std;
class Solution
{
public:
int str2int(string s) // string转int
{
int result = 0;
int base = 1;
int t = 1; // 正负号
if (s[0] == '-')
t = -1;
for (int i = s.size() - 1; i >= 0; --i)
{
if (s[i] >= '0' && s[i] <= '9')
{
result += base * (s[i] - '0');
base *= 10;
}
}
return result * t;
}
int evalRPN(vector &tokens)
{
stack k;
for (int i = 0; i < tokens.size(); ++i)
{
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
{
int Num2 = k.top(); // 第一个取出的是右操作数
k.pop();
int Num1 = k.top(); // 左操作数
k.pop();
if (tokens[i] == "+"){
k.push(Num1 + Num2);
}
else if (tokens[i] == "-"){
k.push(Num1 - Num2);
}
else if (tokens[i] == "*"){
k.push(Num1 * Num2);
}
else if (tokens[i] == "/"){
k.push(Num1 / Num2);
}
}
else
k.push(str2int(tokens[i]));
}
return k.top(); // 最后栈剩下一个元素,就是结果
}
};
~~~
![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5efaf931.jpg)
![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-01-05_568bb5efc4938.jpg)
**四. 小结**
虽然整个思路简单,但在编写程序时还是有一些细节的问题,如从栈弹出两个操作数,第一个弹出的是右操作数,第二个是左操作数;是否需要考虑string转int的问题;可能需要进一步考虑操作数是其他数据类型的情况,如浮点数;其他边界条件是否需要考虑等等。。。
参考链接:[http://baike.baidu.com/link?url=q-x6bMceggqTTRtvBPKuH69fVoEyi6C_ylbEe9lvIHhlruHZ8bdQ6vGuSibCxvw5DWEMWeR98EmWs0Ineo1OTq](http://baike.baidu.com/link?url=q-x6bMceggqTTRtvBPKuH69fVoEyi6C_ylbEe9lvIHhlruHZ8bdQ6vGuSibCxvw5DWEMWeR98EmWs0Ineo1OTq)
';