LC 150. 逆波兰表达式求值

题目描述

这是 LeetCode 上的 150. 逆波兰表达式求值 ，难度为 中等。

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

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

说明：

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

1
2
3
4
5
输入：tokens = ["2","1","+","3","*"]

输出：9

解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：
1
2
3
4
5
输入：tokens = ["4","13","5","/","+"]

输出：6

解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：
1
2
3
4
5
6
7
8
9
10
11
12
13
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

输出：22

解释：
该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

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

逆波兰表达式：

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

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

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

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

基本思路

这是一道关于「表达式计算」的题目。

所有的「表达式计算」问题都离不开「栈」。

对于本题，我们可以建立一个「数字栈」，存放所有的数字，当遇到运算符时，从栈中取出两个数进行运算，并将结果放回栈内，整个过程结束后，栈顶元素就是最终结果。

而栈的实现通常有两种：使用数组继续模拟 & 使用系统自带的栈结构

Java 代码（自带栈）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int evalRPN(String[] ts) {
        Deque<Integer> d = new ArrayDeque<>();
        for (String s : ts) {
            if ("+-*/".contains(s)) {
                int b = d.pollLast(), a = d.pollLast();
                d.addLast(calc(a, b, s));
            }  else {
                d.addLast(Integer.parseInt(s));
            }
        }
        return d.pollLast();
    }
    int calc(int a, int b, String op) {
        if (op.equals("+")) return a + b;
        else if (op.equals("-")) return a - b;
        else if (op.equals("*")) return a * b;
        else if (op.equals("/")) return a / b;
        else return -1;
    }
}

Java 代码（数组模拟栈）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int evalRPN(String[] ts) {
        int[] d = new int[ts.length];
        int tt = -1;
        for (String s : ts) {
            if ("+-*/".contains(s)) {
                int b = d[tt--], a = d[tt--];
                d[++tt] = calc(a, b, s);
            } else {
                d[++tt] = Integer.parseInt(s);
            }
        }
        return d[tt];
    }
    int calc(int a, int b, String op) {
        if (op.equals("+")) return a + b;
        else if (op.equals("-")) return a - b;
        else if (op.equals("*")) return a * b;
        else if (op.equals("/")) return a / b;
        else return -1;
    }
}

C++ 代码（数组模拟栈）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int evalRPN(vector<string>& ts) {
        vector<int> d(ts.size());
        int tt = -1;
        for (string& s : ts) {
            if (s.size() == 1 && (s[0] == '+' || s[0] == '-' || s[0] == '*' || s[0] == '/')) {
                int b = d[tt--], a = d[tt--];
                d[++tt] = calc(a, b, s);
            } else {
                d[++tt] = stoi(s);
            }
        }
        return d[tt];
    }
    int calc(int a, int b, const string& op) {
        if (op == "+") return a + b;
        if (op == "-") return a - b;
        if (op == "*") return a * b;
        if (op == "/") return a / b;
        return -1;
    }
};

Python 代码（数组模拟栈）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def evalRPN(self, ts):
        d = [0] * len(ts)
        tt = -1
        for s in ts:
            if s in "+-*/":
                b = d[tt]
                tt -= 1
                a = d[tt]
                tt -= 1
                d[tt + 1] = self.calc(a, b, s)
                tt += 1
            else:
                d[tt + 1] = int(s)
                tt += 1
        return d[tt]

    def calc(self, a, b, op):
        if op == '+': return a + b
        elif op == '-': return a - b
        elif op == '*': return a * b
        elif op == '/': return int(a / b)
        else: return -1

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

其他

关于「表达式计算」，类似的题目在上周的「每日一题」也出现过：

最后

这是我们「刷穿 LeetCode」系列文章的第 No.150 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

表达式计算

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！