第3章｜栈与队列

Unit 03 · 逆波兰表达式求值

← Unit 02
U03
Operand StackDelay · Pop Two · Reduce

数字先暂存，运算符到达时，
再把最近两个完整结果合并。

逆波兰表达式把运算符放在操作数之后。扫描过程中，数字本身不一定是最终操作数；栈保存的是已经完成求值、但尚未被更外层运算符合并的子表达式结果。

LeetCode #150 题目模型Evaluate Reverse Polish Notation

题目要求

给定字符串数组 tokens，它表示一个合法的逆波兰表达式。计算表达式并返回整数结果。合法运算符为 +、-、*、/，整数除法需要向零截断。

from typing import List class Solution: def evalRPN(self, tokens: List[str]) -> int: pass

数据约束与复杂度目标

  • 1 ≤ len(tokens) ≤ 10⁴；
  • 每个 token 是四种运算符之一，或范围为 [-200, 200] 的整数；
  • 输入表达式合法，且所有中间结果可由 32 位整数表示；
  • 目标实现：时间 O(n)，辅助空间 O(n)。

示例

输入：["2","1","+","3","*"]
输出：9
等价中缀：((2 + 1) * 3)
输入：["4","13","5","/","+"]
输出：6
等价中缀：(4 + (13 / 5))
输入：["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22

本页主模型

数字压栈；运算符到达时依次弹出 right 与 left，计算 left op right 后把结果重新压栈。

Postfix / RPN

运算符位于操作数之后，因此不依赖括号表达优先级；每个运算符消费前面最近的两个完整结果。

Operand Stack

栈中不是原始 token 的简单副本，而是已经求值、尚未被外层运算消费的子表达式结果。

Operand Order

第一次 pop 得到右操作数，第二次 pop 得到左操作数。减法与除法不能交换顺序。

Truncate Toward Zero

例如 -7 / 2 应得到 -3。Python 的 // 是向下取整，负数场景不能直接替代。

先连接上一单元：从“规约字符前缀”到“规约计算结果”Unit 02 → Unit 03
#1047：新字符与栈顶发生反应

栈保存已经消除稳定的字符前缀；相同字符到达时，当前字符与栈顶一起消失。

→
#150：新运算符与栈顶两个结果发生反应

栈保存已经求值的子表达式；运算符到达时，最近两个完整结果被合并成一个新结果。

共同模式不是“都用了 stack”，而是局部归约：输入到达后，只需要访问结果末端的少量对象；一次 pop 或 pop-pop-push，就把较小状态规约成新的稳定状态。
认知任务 1
读到数字 2 时，为什么还不能知道它最终参与哪一次运算？
在逆波兰表达式中，运算符稍后才到达。数字或已完成的子表达式结果必须先作为“待消费操作数”保存。
逆波兰表达式归约实验台概念预演

Token 流与当前局部计算

当前运算
left
op
right
→
value
等待运算符

待消费操作数栈

容器语义栈保存已经求值、尚未被后续运算符合并的结果。
读取 token
判断类型
弹出 right
弹出 left
执行运算
结果压栈
请选择右侧答案，画面将展示此时可确定的信息。
当前索引—
push 次数0
pop 次数0
当前结果—
把“操作数栈归约”编译为 Python填写关键表达式；顺序错误会直接改变减法与除法结果。
初始化容器：
识别数字：if
数字压栈：
弹出操作数：
除法向零截断：
返回结果：
from typing import List

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operators = {"+", "-", "*", "/"}

        for token in tokens:
            if token not in operators:
                stack.append(int(token))
                continue

            right = stack.pop()
            left = stack.pop()

            if token == "+":
                value = left + right
            elif token == "-":
                value = left - right
            elif token == "*":
                value = left * right
            else:
                value = int(left / right)

            stack.append(value)

        return stack[-1]

时间复杂度：O(n)
空间复杂度：O(n)
代码、token 与操作数栈逐行联动点击代码行可跳转到该行第一次执行的状态。
1class Solution:
2 def evalRPN(self, tokens):
3 stack = []
4 operators = {"+", "-", "*", "/"}
6 for token in tokens:
7 if token not in operators:
8 stack.append(int(token))
11 right = stack.pop()
12 left = stack.pop()
14 if token == "+":
15 value = left + right
16 elif token == "-":
18 elif token == "*":
19 value = left * right
22 value = int(left / right)
24 stack.append(value)
26 return stack[-1]

执行状态

tokens["2","1","+","3","*"]
index / token—
stack
left / right / value— / — / —
判断 / 返回进入函数
进入 Solution 类定义。
完成代码联动后进入 LeetCode #227 迁移练习代码正确、查看参考答案、一键填入或播放完整轨迹后解锁。

迁移题：LeetCode #227 基本计算器 II

先完整理解迁移题，再讨论算法复用。#227 把表达式从后缀形式改回中缀字符串：需要解析多位数字与空格，处理乘除优先级，并在恰当时机使用前一个运算符提交刚读完的数字。

1. 认识 #227 原题
2. 对照后缀与中缀归约
3. 映射四个语义变化
4. 拼装并运行官方样例
LeetCode #227 · Basic Calculator II｜基本计算器 IIMedium · Math · String · Stack

题目要求

给定一个表示有效算术表达式的字符串 s，计算并返回表达式的整数值。表达式包含非负整数、+、-、*、/ 和空格；乘除优先于加减。整数除法向零截断，且不能使用 eval() 等直接计算字符串表达式的内置函数。

class Solution: def calculate(self, s: str) -> int: # 返回整个中缀表达式的计算结果

输入、输出与约束

  • 1 ≤ len(s) ≤ 3 × 10⁵；
  • 表达式有效，由非负整数、四种运算符和若干空格组成；
  • 整数范围为 [0, 2³¹-1]，答案及中间结果适合 32 位有符号整数。

官方示例

s = "3+2*2"
输出：7
先计算 2*2，再与3相加
s = " 3/2 "
输出：1
整数除法截断小数部分
s = " 3+5 / 2 "
输出：5
5/2得到2，再计算3+2

解析提醒

12 是一个多位整数，不是字符 '1' 与 '2' 两个独立操作数；空格不结束计算，但运算符或字符串末尾会触发“提交当前数字”。

返回什么返回整个表达式的一个整数值，不返回 token、栈或中间步骤。
优先级乘除必须在同一个乘法项内立即归约；加减项可以延迟到最后求和。
除法规则向零截断，例如 -7/2 → -3，不能机械使用负数的 //。
触发提交读到新运算符或到达字符串末尾时，用旧 prev_op 处理刚读完的数字。

读题检查 A｜calculate 最终返回什么？

读题检查 B｜为什么 "3+2*2" 的结果是 7，而不是 10？

完成两道读题检查后，才能进入 #150 与 #227 的结构对照。

已经掌握：#150 逆波兰表达式

输入：离散 token 数组 运算符位置：两个操作数之后 数字：直接转 int 后压栈 运算符：立即 pop right、pop left 归约结果：重新压栈 优先级：已经由 token 顺序编码

准备迁移：#227 基本计算器 II

输入：包含空格和多位数字的字符串 运算符位置：两个操作数之间 数字：逐位累积 current_number 新运算符到达：旧 prev_op 才消费数字 乘除：立即归约栈顶 加减：保存为带符号项，最后求和
保持不变仍使用栈保存已经完成局部归约、未来可继续参与计算的整数结果；除法仍需向零截断。
需要改变中缀运算符早于右操作数出现，因此不能立刻计算；需要 current_number 和 prev_op 延迟提交。
为什么项栈能够表达优先级？+ 将正数项压栈，- 将负数项压栈；*// 立即与栈顶项合并。这样栈中始终保存已经处理完乘除的带符号加法项，最终只需 sum(stack)。

先判断迁移幅度：下面哪句话最准确？

槽位 A｜需要哪些初始状态？

槽位 B｜怎样读取多位整数？

槽位 C｜什么时候用 prev_op 提交当前数字？

槽位 D｜prev_op 应怎样归约 current_number？

“旧运算符消费新数字”是本题最容易错的时间关系：当扫描到 * 时，刚读完的数字应由此前的 + 处理；当前 * 只是被保存为新的 prev_op，等待下一个数字。
保留的栈思想栈中仍是已经完成局部求值的整数，而不是原始字符；乘除通过修改栈顶完成即时归约。
新增的解析状态current_number 负责多位数字，prev_op 负责延迟决定这个数字如何进入项栈。
新的最终不变量每次提交后，栈中都是已完成乘除的带符号项，因此最终答案等于所有项之和。

#150：运算符到达即可归约

for token in tokens:
    if token 是数字:
        stack.append(int(token))
    else:
        right = stack.pop()
        left = stack.pop()
        stack.append(left op right)
return stack[-1]

#227：旧运算符延迟消费当前数字

for index, char in enumerate(s):
    逐位构造 current_number
    if 遇到运算符或末尾:
        根据 prev_op 提交数字
        + / -：压入带符号项
        * /：立即归约栈顶
        prev_op = char
return sum(stack)
官方样例运行轨迹0/0
可选挑战：脱离槽位，独立重写完整代码

保留状态名称，但独立补全数字构造、提交触发、四种运算符分支和最终求和。

检查项：current_number、prev_op、四种运算符处理、重置状态与 sum(stack)。