Vue.js

Appearance

On this page

实战：逆波兰表达式求值 ​

我们平时写的算术表达式是这样的：(2 + 1) * 3。这种形式叫做中缀表达式——运算符在操作数中间。

但还有另一种表示方式：2 1 + 3 *。这叫做后缀表达式，也叫逆波兰表达式——运算符在操作数后面。

后缀表达式有一个神奇的特性：不需要括号。计算机处理它也特别简单，用栈就能搞定。

问题描述 ​

LeetCode 150. Evaluate Reverse Polish Notation

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

请你计算该表达式，返回一个整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/'
  • 两个整数之间的除法总是向零截断

示例：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：((2 + 1) * 3) = 9
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：(4 + (13 / 5)) = 6

逆波兰表达式简介 ​

先理解什么是逆波兰表达式。

中缀 vs 后缀：

中缀表达式后缀表达式
2 + 32 3 +
(2 + 1) * 32 1 + 3 *
4 + 13 / 54 13 5 / +

后缀表达式的特点：

  1. 不需要括号：运算顺序由表达式本身决定
  2. 不需要优先级规则：从左到右处理即可
  3. 非常适合栈计算：遇到操作符就从栈中取操作数

解法：栈计算 ​

算法非常直接：

  1. 遍历 tokens
  2. 遇到数字：入栈
  3. 遇到操作符：弹出两个操作数，计算结果后入栈
  4. 最后栈中只剩一个数，就是结果
javascript
function evalRPN(tokens) {
  const stack = [];
  const operators = new Set(['+', '-', '*', '/']);
  
  for (const token of tokens) {
    if (operators.has(token)) {
      // 注意：先弹出的是第二个操作数！
      const b = stack.pop();
      const a = stack.pop();
      
      let result;
      switch (token) {
        case '+': result = a + b; break;
        case '-': result = a - b; break;
        case '*': result = a * b; break;
        case '/': result = Math.trunc(a / b); break;  // 向零截断
      }
      
      stack.push(result);
    } else {
      stack.push(parseInt(token));
    }
  }
  
  return stack[0];
}

执行过程可视化 ​

以 tokens = ["2","1","+","3","*"] 为例：

表达式：2 1 + 3 *
等价于：(2 + 1) * 3 = 9

遍历过程：

"2": 数字，入栈
     stack = [2]

"1": 数字，入栈
     stack = [2, 1]

"+": 操作符
     弹出 b = 1, a = 2
     计算 2 + 1 = 3
     入栈
     stack = [3]

"3": 数字，入栈
     stack = [3, 3]

"*": 操作符
     弹出 b = 3, a = 3
     计算 3 * 3 = 9
     入栈
     stack = [9]

结果：9

再看一个例子：tokens = ["4","13","5","/","+"]

表达式：4 13 5 / +
等价于：4 + (13 / 5) = 4 + 2 = 6

遍历过程：

"4": stack = [4]
"13": stack = [4, 13]
"5": stack = [4, 13, 5]
"/": 弹出 b=5, a=13, 计算 13/5=2（向零截断）
     stack = [4, 2]
"+": 弹出 b=2, a=4, 计算 4+2=6
     stack = [6]

结果：6

关键细节 ​

1. 操作数顺序 ​

这是最容易出错的地方！

对于 a - b 或 a / b：

  • a 是先入栈的（后弹出）
  • b 是后入栈的（先弹出）
javascript
// ✅ 正确顺序
const b = stack.pop();  // 先弹出的是第二个操作数
const a = stack.pop();  // 后弹出的是第一个操作数
result = a - b;  // 注意是 a - b，不是 b - a

// ❌ 错误顺序
const a = stack.pop();
const b = stack.pop();
result = a - b;  // 6 - 4 写成了 4 - 6

2. 除法向零截断 ​

JavaScript 的除法会得到小数，需要截断：

javascript
// 6 / -3 的正确结果是 -2（向零截断）
// 而不是 -3（向下取整）

Math.trunc(6 / -3)   // -2 ✅
Math.floor(6 / -3)   // -3 ❌

Math.trunc() 是向零截断，Math.floor() 是向下取整，对于负数结果不同。

3. 负数处理 ​

tokens 中的数字可能是负数，如 "-3"。我们用 parseInt() 可以正确处理。

复杂度分析 ​

  • 时间复杂度：O(n)，遍历一次 tokens
  • 空间复杂度：O(n)，栈的大小

边界情况 ​

  • 单个数字：["42"] → 42
  • 连续操作：["2","1","+","3","4","-","*"] = (2+1)*(3-4) = -3
  • 负数：["-3","2","+"] = -3+2 = -1

常见错误 ​

错误1：操作数顺序颠倒

javascript
// ❌ 减法和除法的结果会错
const a = stack.pop();
const b = stack.pop();
result = a - b;  // 应该是 b - a

// 表达式 "4 2 -" 应该是 4 - 2 = 2
// 但如果顺序错了，会算成 2 - 4 = -2

错误2：除法用错方法

javascript
// ❌ 向下取整
result = Math.floor(a / b);

// ✅ 向零截断
result = Math.trunc(a / b);

错误3：忘记将字符串转数字

javascript
// ❌ 字符串 "1" + "2" = "12"
stack.push(token);

// ✅ 转成数字
stack.push(parseInt(token));

为什么后缀表达式不需要括号？ ​

中缀表达式 2 + 3 * 4 需要知道乘法优先于加法。如果想先算加法，必须用括号：(2 + 3) * 4。

后缀表达式直接体现计算顺序：

  • 2 + 3 * 4 → 2 3 4 * +（先算 3*4）
  • (2 + 3) * 4 → 2 3 + 4 *（先算 2+3）

表达式本身就决定了计算顺序，不需要额外的优先级规则和括号。

技巧总结 ​

逆波兰表达式计算的核心：

  • 栈存操作数：遇到数字入栈，遇到操作符取出计算
  • 注意顺序：先弹出的是第二个操作数
  • 向零截断：除法用 Math.trunc()

这道题是栈应用的经典例题。理解后缀表达式后，你可以更好地理解编译器如何处理表达式。

关联题目 ​

  • LeetCode 224：基本计算器（中缀表达式）
  • LeetCode 227：基本计算器 II（带乘除）
  • LeetCode 772：基本计算器 III（带括号）

在 GitHub 上编辑此页