转载

​ 谈起逆波兰式最好说一说波兰式，这两个都是为了纪念一位波兰数学家而得名。这位波兰数学家在很久以前它的著作中谈到：他发现了一种可以不使用括号的表达方法。

• 平时我们习惯将表达式写成 (1+2)*(3+4) ，加减乘除等运算符写在符号中间，因此称呼为中缀表达式 。
• 而波兰表达式的写法为 (*(+ 1 2)(+ 3 4)) ，将运算符写在前面，因此称为前缀表达式。
• 逆波兰表达式就是这种 ((1 2 +)(3 4 +)*），将运算符写在后面，所以逆波兰表达式也叫做后缀表达式。

使用波兰表达式和逆波兰表达式有个好处，就是前面提到的可以去掉括号，并且不引起歧义，而且不用考虑优先级。这一点极大的方便了栈式语言。比如

1+1*1 可以转换为 1 1 1 * +

（1+1）*1 可以转换为 1 1 + 1 *

通常我们看到的表达式只是人能够看得懂的表达式，比如1+1*1 ，而计算机看得懂的是这种表达式处理过后数据单元 1 1 + ，这种东西也叫做Tokenize，通常表达式还要经过parser处理。计算机处理表达式还是把他们当做字符串来处理，并且还是从左到右处理。

逆波兰表表达式操作步骤

• 读取中缀表达式，遇到操作数直接输出。
• 遇到操作符一次从栈中弹出优先级更高的操作符，同时输出括号外的操作符。
• 读取完毕，一次输出栈中的所有字符

计算机将中缀表达式转化成逆波兰表达式就是逆波兰表达式最为重要的应用之一。

题目描述：

根据 逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

示例:

输入: [“2”, “1”, “+”, “3”, “*”]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

思路分析:

该题目用栈求解的思路是：

首先，对于给定的字符串数组进行遍历，对每个元素进行考察。

然后，如果当前考察的元素不属于+、 -、、/ ，则将其入栈；如果当前考察的元素属于+、 -、、/，则将栈顶元素及其后面一个元素出栈。接着，将出栈的两个元素进行表达式求值运算，并将计算结果入栈。

最后，当字符串数组中的所有元素考察完毕时，将栈顶元素出栈，就是最终计算结果。

作者：hardcore-aryabhata
链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/solution/dong-hua-yan-shi-150-ni-bo-lan-biao-da-s-try7/