逆波兰表达式和栈的压入弹出序列这两道题是我在实际面试中特别喜欢拿来当“暖场题”的。说它简单吧能一次写对的人真不多说它难吧核心代码基本不超过十行。它们恰好是栈这个数据结构最经典的两类考法一个是用栈“正向求值”一个是判断一组出入栈动作“是否合法”。LeetCode 150 和 946、剑指 Offer 31 原题都属于面试必刷那一档。这篇文章就把两道题串起来讲透从原理到代码从坑点到面试表达一次性解决。1. 为什么这组题是面试常客1.1 两道题到底在考什么先说逆波兰表达式。它也叫后缀表达式题目会给你一个字符串数组比如[2,1,,3,*]让你按后缀表达式的规则求值。表面上考的是“用栈模拟计算”实际上考察的是你有没有建立“操作数顺序不可乱”的意识——减法、除法里先弹出来的是右操作数后弹出来的是左操作数这个细节一错全盘皆输。再说栈的压入弹出序列。题目给你pushed和popped两个序列问能不能通过一个栈的合法操作让出栈序列等于popped。它考察的则是你对栈“后进先出”物理约束的理解以及把过程用程序模拟出来的能力。这两道题都不是那种需要背复杂模板的难题但它们对“边界感”的要求非常高面试官很容易通过测试用例区分出你是真懂还是背题。还有一点容易被忽略这两道题在算法体系里属于“解法很固定但细节很多”的题型。你很难在思路上有什么创新但可以在代码的稳健性和沟通表达上拉开差距。所以我带新人的时候常拿这两道题做第一轮筛选效果相当好。1.2 从面试官视角看两道题的关联很多人把这两道题当独立的题刷其实它们是一组很好的“对照实验”。逆波兰表达式是“给定操作序列你按规则执行”压入弹出序列是“给定操作结果你判断操作过程是否合法”。一个正向操作一个反向验证本质上都在测试你对栈的 LIFO 规则有没有形成肌肉记忆。我把栈比作一条只能从一头进出车的窄巷子。逆波兰表达式就像巷子里停着几辆车你接到指令让某辆车开出来因为只能从巷口倒出来所以你必须先把挡在后面的车全部倒出来压入弹出序列则像有人给你一份“车进巷子和出巷子”的流水账你要判断这个流水账在物理上是否真的可实现。这种统一视角非常有助于记忆面试时你甚至可以主动提一句“这两题本质是同一个模型的正反两面”会让面试官觉得你对数据结构有体系化理解。顺便提一句队列的对照如果同样的问题发生在队列里由于只能队尾进、队首出出队顺序受的限制比栈更大。理解这一点你在回答“栈和队列的区别”这类基础问题时也能更从容。2. 逆波兰表达式后缀表达式的工程价值2.1 为什么表达式要转成后缀中缀表达式是人类习惯的写法比如1 2 * 3里面有运算符优先级、有括号、有结合性解析起来要考虑的东西很多。但计算机本质上是一步步顺序执行的机器后缀表达式的好处就是把优先级和括号全部“折叠”进排列顺序里让计算过程彻底线性化。你从左到右扫描后缀表达式遇到数字就压栈遇到运算符就弹出栈顶两个元素计算再把结果压回去。整个过程不需要回头不需要查优先级表也没有括号。所以编译器在生成中间代码、计算器在内部求值时普遍采用这种形式。你可能听过 HP 的老式计算器使用 RPN 输入就是因为它实现简单、没有歧义。面试的时候如果面试官追问“为什么计算机更擅长后缀表达式”你可以从“减少状态回溯”这个角度答。后缀表达式的每一步操作都是确定性的系统只需要维护一个栈不需要维护多层递归状态这对硬件和编译器都非常友好。这也解释了为什么逆波兰表达式能在 LeetCode 上成为经典题。2.2 手算中缀转后缀的规则虽然 LeetCode 150 直接给你后缀表达式但很多面试题会进一步要求“自己实现中缀转后缀再求值”比如表达式求值系列题目基本都能用这个套路统一解决。所以中缀转后缀的规则一定要能徒手推出来。规则可以总结成四句话操作数直接输出不用进栈。左括号直接入栈。右括号不断弹出栈顶并输出直到遇到左括号左括号弹出但不输出。普通运算符入栈前先把栈中所有优先级不低于它的运算符弹出并输出再将自己入栈扫描结束后再把栈里剩余运算符全部弹出输出。举一个具体的例子(1 2) * (3 - 4)。扫描时1输出入栈2输出遇到右括号后弹出得到1 2 然后*入栈遇到左括号入栈3输出-入栈4输出右括号弹出-最后弹出*。最终结果是1 2 3 4 - *。这里有个很多新手不理解的点为什么“同优先级运算符”也要弹出因为运算结合性是从左到右。比如1 - 2 - 3正确的计算顺序是(1 - 2) - 3。如果遇到第二个减号时你不弹出第一个减号后面求值时符号顺序就会错。记住栈顶运算符优先级不低于当前运算符时都要弹出这是左结合规则的自然推论。2.3 求值的代码实现与边界处理核心代码很短但写法上有几个值得抠的细节。Python 版本大概是这样的def evalRPN(tokens): stack [] op_set {, -, *, /} for token in tokens: if token in op_set: b stack.pop() a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) else: stack.append(int(a / b)) else: stack.append(int(token)) return stack[-1]第一个细节是弹出顺序。假设表达式是a b -那么第一次弹出的b是右操作数第二次弹出的a是左操作数。减法除法必须写成a - b、a / b反过来就错了。我见过太多次把减法写成stack.pop() - stack.pop()的翻车现场虽然这种写法对加法乘法没影响但减法和除法立刻出错。第二个细节是除法取整方向。LeetCode 原题要求除法向零截断也就是3 / 2 1、-3 / 2 -1。C 里整数除法天然向零截断直接用a / b就行但 Python 的//是向下取整-3 // 2会得到-2这是经典大坑。所以 Python 里要写成int(a / b)或者用math.trunc(a / b)也可以写int(b and a / b)之类的技巧但可读性太差不推荐。第三个细节是判断运算符时不要用单个字符判断。比如token[0] -这种写法会把负数-2误判成运算符。最稳妥的方式是判断整个字符串是否属于运算符集合因为负数 token 的长度大于 1永远不会等于-。这些边界处理在面试里非常加印象分。你主动说出“Python 的整数除法向负无穷取整需要转成向零截断”面试官基本就知道你是踩过坑的真路人而不是背答案。2.4 变式题与拓展方向逆波兰表达式这题做完后我建议立刻做一遍中缀转后缀的完整实现也就是把字符串1 2 * 3转成[1,2,3,*,]再求值。这个扩展题是 LeetCode 224、227、772 一类计算器题目的统一底层方案。中缀转后缀的代码并不复杂用一个操作符栈即可规则就是我上面讲的四句话。唯一要注意的是处理多位数和带符号数字时的解析逻辑。我通常会在扫描时用 while 循环把连续数字拼成一个整数再把空格跳过。实际写起来大概二十行左右但很能检验基本功。另外波兰表达式还有一种“前缀表达式”写法也就是运算符放前面比如 1 * 2 3。它本质上和后缀是对称的只不过扫描时需要从右往左。理解了这一点你对表达式树的理解也会更深入一层。如果面试官问到编译原理相关背景你可以提一句“后缀表达式对应表达式树的后续遍历”这属于很自然的延伸。3. 栈的压入弹出序列模拟还是数学3.1 问题描述与核心直觉题目给两个数组pushed和popped长度相同。你有一个初始为空的栈按pushed的顺序依次把元素压入栈压入操作和弹出操作的时机完全由你决定问最终弹出的序列能不能恰好等于popped。比如pushed [1,2,3,4,5]popped [4,5,3,2,1]是合法的popped [4,3,5,1,2]则不合法。这道题的核心直觉其实非常朴素看一眼popped当前需要弹出的元素如果它已经在栈顶那就立刻弹出如果它还没有入栈那就继续按pushed的顺序入栈直到它成为栈顶如果它既不在栈顶又不在还没入栈的剩余序列里那这个出栈序列就是非法的。这个直觉背后的道理是栈是 LIFO 结构你不可能跳过栈顶元素去弹更底下的元素。所以“能弹就弹不能弹就继续入栈”就是唯一可能的操作方式。理解了这一点solution 几乎是顺水推舟的事。3.2 双指针模拟法最经典的解法是双指针加辅助栈。指针j指向popped中下一个要验证的元素然后遍历pushed每压入一个元素就立刻检查栈顶是否匹配popped[j]如果匹配就一直弹到不匹配为止。最后如果j走到了popped的末尾说明序列合法。def validateStackSequences(pushed, popped): stack [] j 0 for x in pushed: stack.append(x) while stack and j len(popped) and stack[-1] popped[j]: stack.pop() j 1 return j len(popped)C 版本也很直接bool validateStackSequences(vectorint pushed, vectorint popped) { vectorint st; int j 0; for (int x : pushed) { st.push_back(x); while (!st.empty() j popped.size() st.back() popped[j]) { st.pop_back(); j; } } return j popped.size(); }为什么需要那个while循环而不是if因为连续弹栈是常见情况。比如pushed [1,2]popped [2,1]当2入栈后栈顶是2先弹出弹出后栈顶变成1而popped下一个要弹的也是1所以必须继续弹出。用while正是为了让这个过程持续发生。这段代码里还有一个循环不变量值得在面试时主动讲每次外部for循环结束的时候栈中剩下的元素都是“已经入栈但还没找到自己输出时机”的元素。栈顶只要能匹配popped[j]就说明下一个出栈元素恰好在它该在的位置。想清楚这个不变量代码基本不会写错。3.3 为什么不能靠“找规律”代替模拟有的读者可能会想能不能总结一个数学条件直接判断序列是否合法比如看逆序对、看某个元素左右两边的关系。这种思路可以理解但栈的合法性是一个“过程正确性”问题很难用静态序列特征完全刻画而且即使能找到某种判据也大概率比直接模拟更复杂、更容易出错。看一个反例就够了。pushed [1,2,3,4,5]popped [4,5,3,2,1]合法操作过程是 1、2、3、4 依次入栈弹出 45 入栈弹出 5再依次弹出 3、2、1。popped [4,3,5,1,2]则不合法先按顺序压入 1、2、3、4弹出 4、3再压入 5 并弹出 5此时栈中自顶向下是 2、1可下一个要弹出的是 1它被 2 压住了无法跳过于是非法。这个例子说明栈的合法性取决于“每一步当前的栈顶是否等于期望弹出的元素”这是一个动态模拟问题。与其去找各种易错的“性质”不如老老实实按 O(n) 模拟。而且 O(n) 已经是线性下界——每个元素至少要被压入一次所以这个模拟方案在理论上也是最优的。3.4 复杂度分析与面试追问时间复杂度 O(n)每个元素最多被压栈一次、弹出一次内部while循环的总执行次数不超过pushed长度所以整体是线性。空间复杂度 O(n)因为辅助栈最坏情况下可能存下所有元素。面试官常在这个基础上问几个问题。第一个问题如果pushed是1..n的排列合法的popped序列有多少种答案是卡塔兰数数学上有很多等价定义比如进出栈路径问题。这个属于进阶内容能说出名字就已经不错了。第二个问题如果元素有重复模拟法还成立吗LeetCode 946 的测试用例里就允许重复。模拟法依然成立因为“能弹就弹”的贪心策略不会破坏合法性判断。你可以这样想假设当前栈顶等于popped[j]如果你不弹它它就会一直堵住栈顶影响后续所有弹出操作所以必须立刻弹掉如果继续入栈可能遇到另一个相同元素产生另一种操作序列但任何一种合法序列都能被“能弹就弹”的贪心策略复制出来这也是这类题背后的贪心正确性直觉。4. 面试高频扩展用栈和队列互相实现4.1 用两个栈实现队列LeetCode 232 是一道和“压入弹出序列”强相关的姊妹题。它要求用两个栈模拟队列的 push、pop、peek、empty。核心思想是设置两个栈inStack负责接收新元素outStack负责输出元素。push 时直接压入inStackpop 时如果outStack为空就把inStack里的元素全部倒进outStack再从outStack弹出。为什么这个操作是对的因为inStack的栈顶是最后入队的元素全部倒进outStack后outStack的栈顶就变成了最先入队的元素正好满足 FIFO。每个元素最多被“倒”一次所以均摊时间复杂度是 O(1)。面试官让你实现队列时经常顺手问一句“为什么均摊是 O(1)”你可以答每个元素从inStack移动到outStack只发生一次之后 pop 就是 O(1)。这道题和压入弹出序列放在一起刷特别有意思一个关注“如何用栈实现更复杂的语义”一个关注“如何验证给定语义是否可实现”。理解其中一个另一个会变得非常自然。4.2 用两个队列实现栈LeetCode 225 则是反向操作用队列实现栈。这里有个非常经典且代码极短的做法只用一个队列入栈时先把元素放进队尾然后把队列里前面的元素依次出队再入队让新元素“旋转”到队首。这样队首始终对应栈顶。from collections import deque class MyStack: def __init__(self): self.q deque() def push(self, x: int) - None: self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self) - int: return self.q.popleft() def top(self) - int: return self.q[0] def empty(self) - bool: return not self.qpush 的复杂度是 O(n)因为要旋转队列pop 是 O(1)。用两个队列的常规做法本质也是这个思路只是把旋转过程拆成“把非空队列的元素搬进另一个队列”。这个“旋转”技巧在很多队列相关题目里都有变体比如循环队列、滑动窗口值得记在脑子里。4.3 最小栈与单调栈方向栈相关的必刷题还有最小栈和单调栈。最小栈 LeetCode 155 要求能在 O(1) 时间拿到栈内最小值常规做法是维护一个辅助栈每次 push 时把“当前最小值”同步压进去pop 时一起弹出。注意判断条件要用这样才能处理连续相同最小值的情况。单调栈则是把“栈内元素保持单调性”这一招用到极致。经典的“下一个更大元素”、“每日温度”、“柱状图中最大的矩形”都是单调栈的典型应用。它可以理解为当新元素破坏了栈的单调性时就不断弹出旧元素弹出去的元素往往就意味着“它的答案已经确定”。这套思路和逆波兰表达式里的“弹栈时机”其实有相似之处——都是在一系列操作中确定最优解只是不需要在代码上强行联系。如果你时间充裕建议把最小栈和单调栈题组放在本篇的两道题之后一周内刷完。它们共用同一个底层模型但思考角度不同对建立“栈题感”很有帮助。5. 常见误区与排查实录5.1 逆波兰表达式的经典失误我整理了一张自己实际见过的错误清单基本都是高频翻车点误区现象原因与正确做法弹栈顺序颠倒减法除法结果全错第一次弹出的是右操作数 b第二次是左操作数 a必须写成a - bPython 除法用//负数结果差 1//向下取整用int(a / b)实现向零截断用首字符判断负数 token-2被当成运算符判断整个字符串是否在运算符集合中空栈直接 pop运行时报错题目虽保证合法但防御性代码应判空我在给代码做 code review 时还见过一种隐蔽错误有人先把所有 token 转成整数再单独用一个布尔数组标记是否为运算符。这会导致带符号数字和减号运算符在形态上完全一致处理起来非常别扭。正确做法就是保留字符串数组遇到运算符字符串才弹栈否则转换为整数压栈。5.2 压入弹出序列的边界细节这道题代码看着短但边界条件比大多数人想象的多。第一个是长度问题如果两个序列长度不等直接返回 false不需要进入模拟。第二个是while循环里的j len(popped)条件不能省否则在特殊用例下可能出现越界访问。第三个是重复元素。LeetCode 946 明确允许元素重复这坑倒了一批人。有人会担心“能弹就弹”会不会把一个本该留着的元素提前弹掉导致后面没法凑出合法序列。实际上不会因为栈顶一旦被弹出它就不可能再成为后面某个时刻的栈顶而如果它后面还需要被弹出逻辑上只会更不自由。这里可以稍微想深一点模拟法本质是对“所有可能操作序列”的贪心剪枝你每次选择最早可做的弹出操作等价于在所有可行方案里选了一条最“激进”的路径这条路径不会破坏可行性。第四个容易出问题的是返回值判断。有人最后检查“栈是否为空”这其实不对。正确的判断标准是j len(popped)也就是所有期望弹出的元素都已经被匹配。如果序列非法栈可能有残留也可能没有所以不要用栈空不空来判断。5.3 调试技巧与面试表达我在带人刷题时强烈推荐一个笨办法手画栈状态图。每压一个元素画一格每弹一个就划掉一格然后把popped指针的位置标在旁边。画完一个用例你对题目的理解会比打印十行日志都深刻。面试表达上也有套路可循。先说思路“我维护一个辅助栈用一个指针指向popped当前要弹出的元素每遍历一个pushed元素就入栈然后循环检查栈顶能弹就弹最后看指针是否走完。”十秒钟把方案讲清楚面试官基本就能判断你思路对不对。然后写代码写完立刻主动跑一个简单例子比如pushed [1,2,3]、popped [1,3,2]。这个例子合法过程是一入一出再压 2、3弹 3、2。手动跑一遍既能自查也能展示严谨。5.4 一点个人体会我面过不少人也被不少人面过。栈和队列的题最大的坑不是不会而是“觉得自己会”。逆波兰表达式人人能背出“数字压栈符号弹两个”可一到负数除法就挂压入弹出序列有人五分钟写完有人盯着屏幕十分钟不敢动手区别就在于有没有形成“能弹就弹”这个贪心直觉。把两道题当作基本功来练不要背代码每次刷都重新推导一遍。另一个小技巧用 Python 刷题时list是最顺手的栈但如果面试写 C我更推荐用std::vector配合push_back/pop_back而不是std::stack。原因很简单——调试时vector可以直接看内部元素这对排查压入弹出序列这类需要观察栈内容的问题太有用了。