题目描述
思路解析动画文字版
能做对,但要扫两遍、还要原地改写字符串,代码又长又容易错。有没有一遍搞定的办法?
关键招:加减是「记账,先存着」,乘除是「马上和栈顶结算」。最后把栈里所有数一加,就是答案——优先级被栈自动摆平了。
下面用 "3+2*2" 一个字符一个字符地演。上排是输入流,下面是栈。盯住 op(待执行的符号) 和栈怎么变。
起步 · op = +：约定:把 op 初始设成 +,这样第一个数也能像「+num」一样被正常压栈。指针还没出发,栈是空的。
看 '3' · 是数字：第 1 个字符是数字 3,先把它攒进 num(num = 0×10+3 = 3)。数字只攒不结算,要等碰到符号才动手。
看 '+' · 用 op(=+) 结算：碰到符号 +!先用上一个 op(还是初始的 +)结算 num:op 是 + → 把 +3 压栈。然后把 op 更新成这个 +,num 清零。
看 '2' · 是数字：第 3 个字符是数字 2,攒进 num。栈不动,还是 [3]。继续往后看符号。
看 '*' · 用 op(=+) 结算 2：碰到 *!但要先用上一个 op(+)把刚攒的 num=2 结算掉:压 +2,栈变 [3, 2]。然后才把 op 更新成 *,num 清零。
看 '2' · 是数字(末尾)：op 此刻挂着 *(待办:下一个数和栈顶相乘)。最后一个字符数字 2 攒进 num。走到末尾了——即使后面没符号,也要触发一次结算,否则这个 num 漏掉。
末尾结算 · op 是 * → 乘栈顶：op 是 *!不是直接压,而是先弹出栈顶 2,算 2 × 2 = 4,再把 4 压回去。栈变 [3, 4]——乘法就地把栈顶替换成了乘积。
扫描结束 · 栈内求和：字符串走完。栈里全是带符号、且乘除已算完的数,直接相加:3 + 4 = 7。先乘后加的优先级,全程没专门判断,被栈悄悄摆平了。
换 14-3/2 走一遍。这次专盯减号怎么变成压负数,以及除法对栈顶动手。
起步 · op = +：同样把 op 初始设成 +。输入流是 1 4 − 3 / 2,栈空,准备开扫。
看 '1' · 是数字：第 1 个字符 1,num = 0×10+1 = 1。栈还空着。下一位若还是数字,就要拼成多位数。
看 '4' · 多位数拼接：第 2 个还是数字 4:num = 1×10+4 = 14。这就是多位数的拼法——每来一位就把已有的 ×10 再加上新位。
看 '-' · 用 op(=+) 结算 14：碰到 −:先用上一个 op(+)结算 num=14 → 压 +14。然后把 op 更新成 −。注意 − 本身不立刻减,它只是「挂起」,作用在下一个数上。
看 '3' · 是数字：数字 3 攒进 num。此刻 op 挂着 −:意味着这个 3 将来要以负数身份进栈。栈暂时还是 [14]。
看 '/' · 用 op(=−) 结算 3：碰到 /:先用上一个 op(−)结算 num=3 → 压 −3,栈变 [14, −3]。减法就是「压一个负数」,这样最后求和时它自然被减掉。然后 op 更新成 /。
看 '2' · 是数字(末尾)：op 此刻挂着 /,栈顶是带符号的 −3(影响取整方向)。最后字符 2 攒进 num,到末尾了,要触发末尾结算——别漏掉这个 2。
末尾结算 · op 是 / → 除栈顶：op 是 /:弹出栈顶 −3,算 (−3) / 2。题目要求向零取整:−1.5 朝 0 取整 = −1(不是 −2!),压回去。栈变 [14, −1]。
扫描结束 · 栈内求和：走完了!栈里 [14, −1] 直接相加 = 13。减号变负数、除法就地结算栈顶,加减乘除四则混合一遍扫完。
再看一例 · "2*3+4" · 乘法当头：再快走一遍乘法当头的 2*3+4:2 攒着→遇 * 先用初始 + 压 +2,栈 [2],op 转成 *。
"2*3+4" · 遇 + 触发 * 结算：3 攒着→遇 +:先用挂着的 * 结算——pop 2,压 2×3=6,栈 [6]。乘法又一次就地把栈顶替换成乘积。op 转 +。
"2*3+4" · 末尾压 +4 求和：4 攒着→末尾用 + 压 +4,栈 [6, 4],求和 = 10。三个例子都印证:加减记账、乘除即时改栈顶。
整条式子从左到右只走了一遍,优先级靠「加减压栈、乘除即时结算栈顶」自动处理,没有任何回头或重写——这就是栈的威力。
想透这点这题就通了:加减是「我先存着,回头一起算」,乘除是「我级别高,马上把栈顶改掉」。这套「延迟低优先、即时高优先」是表达式求值的通用骨架。
雷区实演 · 漏了末尾结算：若只在「碰到符号」时结算,最后那个 2 后面没符号,就永远不会触发结算:栈停在 [3,2],错算成 5(正解 7)。所以条件里必须带上 i == 末尾。
对照 · 加上末尾补刀就对了：把 i == 末尾 写进条件,末尾这个 2 就能触发一次 * 结算:弹 2、压 2×2=4,栈成 [3,4],求和 = 7,正确。
边界三连：先想乘法插队、负数除法取整、夹空格三种,代码就稳了。
面试追问：把「栈如何摆平优先级」「op 为何初始为 +」讲清楚,是这题面试的得分点。
参考代码
class Solution: def calculate(self, s): stack = [] num, op = 0, '+' # op: 上一个运算符,初始 + for i, ch in enumerate(s): if ch.isdigit(): num = num * 10 + int(ch) # 拼多位数 if (not ch.isdigit() and ch != ' ') or i == len(s) - 1: if op == '+': stack.append(num) elif op == '-': stack.append(-num) elif op == '*': stack.append(stack.pop() * num) elif op == '/': stack.append(int(stack.pop() / num)) op, num = ch, 0 # 更新 op,清零 num return sum(stack)复杂度
- 时间复杂度：O(n)，字符串只从左到右扫一遍,每个字符做常数次操作;每个数最多进栈一次、出栈一次 → O(n)
- 空间复杂度：O(n)，最坏全是加减(如 1+1+1+…),所有数都压进栈 → O(n)
易错点
面试追问把动画讲成自己的话
追问为什么栈能自动处理优先级?
追问若加上括号(LC224/772)怎么办?
追问为什么 op 要初始化成 +?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
去除重复字母
LeetCode 316 · 中等 · 沿着 栈套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题