LeetCode 150. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

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

示例 2：

1输入： tokens = ["4","13","5","/","+"]
2输出： 6
3解释： 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
4

示例 3：

1输入： tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
2输出： 22
3解释： 该算式转化为常见的中缀算术表达式为：
4  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
5= ((10 * (6 / (12 * -11))) + 17) + 5
6= ((10 * (6 / -132)) + 17) + 5
7= ((10 * 0) + 17) + 5
8= (0 + 17) + 5
9= 17 + 5
10= 22
11

提示：

1 <= tokens.length <= 104
tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

其实逆波兰表达式相当于是二叉树中的后序遍历。大家可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。

但我们没有必要从二叉树的角度去解决这个问题，只要知道逆波兰表达式是用后序遍历的方式把二叉树序列化了，就可以了。

在进一步看，本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，那么这岂不就是一个相邻字符串消除的过程，和1047.删除字符串中的所有相邻重复项 (opens new window)中的对对碰游戏是不是就非常像了。

如动画所示：

相信看完动画大家应该知道，这和1047. 删除字符串中的所有相邻重复项 (opens new window)是差不多的，只不过本题不要相邻元素做消除了，而是做运算！

1class Solution {
2    fun evalRPN(tokens: Array<String>): Int {
3        val result: Int
4        val stack = Stack<Int>()
5        var tempNum: Int
6        for ((index, string) in tokens.withIndex()) {
7            if (string == "+" || string == "-" || string == "*" || string == "/") {
8                val num2 = stack.pop()
9                val num1 = stack.pop()
10                if (string == "+") {
11                    tempNum = num1 + num2
12                    stack.push(tempNum)
13                } else if (string == "-") {
14                    tempNum = num1 - num2
15                    stack.push(tempNum)
16                } else if (string == "*") {
17                    tempNum = num1 * num2
18                    stack.push(tempNum)
19                } else if (string == "/") {
20                    tempNum = num1 / num2
21                    stack.push(tempNum)
22                }
23            } else {
24                stack.push(string.toInt())
25            }
26        }
27        return stack.pop()
28    }
29}
30

《LeetCode 150. 逆波兰表达式求值》是转载文章，点击查看原文。