LeetCode 150. 逆波兰表达式求值

约 5 分钟
文章信息 15 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 面试经典 150 题 腾讯 字节 微软 美团 拼多多 京东 百度 小红书 快手
标签
数组 数学 栈

题目描述

✅ 150. 逆波兰表达式求值

image-20260928214522682

image-20260928214522683

题意分析

计算一个有效的后缀表达式：运算符出现在它的两个操作数之后，操作数既可以是整数，也可以是前面一段子表达式的结果。

数字可能为负数；整数除法向零截断。题目保证表达式有效、不含除零运算，并且答案和中间结果都在 32 位整数范围内。

解法：栈模拟表达式求值

核心思路

[!blue]

从左到右扫描，用栈保存已经算完、但还没有参与下一次合并的子表达式结果。遇到数字时，它本身就是一个完成的子表达式，直接入栈。

遇到运算符时，它的两个操作数已经出现在前面。如果某个操作数本身是一段表达式，这段表达式也已经被压缩成一个栈内结果。因此当前运算符要合并的，恰好就是栈顶的两个结果；弹出它们，算出新结果再压回，仍然保持栈的含义不变。

后缀表达式先给左操作数，再给右操作数，所以后入栈的右操作数会先弹出。应先取 right、再取 left，计算 left op right；减法和除法尤其不能交换顺序。每次就地合并已经确定的两个操作数，运算次序由输入决定，不需要另行比较乘除与加减的优先级。

运算符按完整字符串匹配，负数不会被误认成减号。Java、Go 的整数除法都向零截断，可以直接使用 /。表达式有效保证遇到运算符时至少有两个结果可取，并且扫描结束时恰好只剩整个表达式的一个结果。

解题步骤

  1. 建立整数栈，依次读取每个 token。
  2. 若它不等于 +、-、*、/ 中的任何一个，就解析成整数并入栈。
  3. 否则先取出栈顶作为 right，再取出新的栈顶作为 left，计算 left op right 后把结果压回栈。
  4. Go 用切片模拟栈时，先读出末尾两个数，再把切片长度缩短二，最后追加新结果。
  5. 遍历结束后，返回栈中唯一的整数。

代码实现

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();

        for (String token : tokens) {
            switch (token) {
                case "+":
                case "-":
                case "*":
                case "/":
                    // 先弹出右操作数，再弹出左操作数，减法和除法不能交换。
                    int right = stack.pop();
                    int left = stack.pop();
                    int value;

                    switch (token) {
                        case "+":
                            value = left + right;
                            break;
                        case "-":
                            value = left - right;
                            break;
                        case "*":
                            value = left * right;
                            break;
                        default:
                            value = left / right;
                    }

                    stack.push(value);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }
}

import "strconv"

func evalRPN(tokens []string) int {
    stack := make([]int, 0, len(tokens))

    for _, token := range tokens {
        switch token {
        case "+", "-", "*", "/":
            // 栈顶是右操作数，下面才是左操作数，减法和除法不能交换。
            right := stack[len(stack)-1]
            left := stack[len(stack)-2]
            stack = stack[:len(stack)-2]

            value := 0
            switch token {
            case "+":
                value = left + right
            case "-":
                value = left - right
            case "*":
                value = left * right
            case "/":
                value = left / right
            }
            stack = append(stack, value)
        default:
            value, _ := strconv.Atoi(token)
            stack = append(stack, value)
        }
    }
    return stack[len(stack)-1]
}

复杂度分析

设 n 为 token 数量，S 为所有 token 的字符总数。

  • 时间复杂度：$O(S)$，解析数字需要扫描其字符，每个 token 只产生常数次栈操作。题目中的整数长度有上限，因此也可记为 $O(n)$。
  • 空间复杂度：$O(n)$，在多个操作数尚未被运算符合并时，栈中可能保存线性数量的结果。

关键点总结

[!green]

  • 栈内保存的是已经完成的子表达式结果，运算符把栈顶两个结果合成一个。
  • 先弹出右操作数，再弹出左操作数，始终按 left op right 计算。
  • 每次合并都保持栈的含义不变，最后唯一的栈元素就是整个表达式的值。

易错点总结

[!yellow]

  • 交换左右操作数：加法、乘法可能碰巧正确，减法、除法会改变结果。
  • 按首字符识别运算符：负整数也以 - 开头，必须匹配完整 token。
  • 把向零截断理解为向下取整：商为负数时，两者不同；本题可以直接使用 Java、Go 的整数除法。
  • Go 取出两个数却只删除一个：两个旧操作数都已被新结果替代，切片长度必须先缩短二。
  • 再次套用中缀表达式的优先级：后缀顺序已经确定合并关系，遇到运算符就应立即计算。

相似题目

题目 难度 关联与区别
224. 基本计算器 困难 原题中缀表达式要处理括号和优先级，本题后缀顺序已确定，遇运算符直接弹出两个操作数。
227. 基本计算器 II 中等 同样用栈保存尚未合并的结果，原题仍需按乘除优先级决定计算时机。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/00551611
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！