1. 逆波兰表达式求值一道“送分题”怎么被写丢分这是栈与队列高频算法题精讲的第二篇。上一篇我们打好了栈和队列的基础底子这一篇把注意力集中在两道面试必刷原题上逆波兰表达式求值、栈的压入弹出序列。这两道题在各类算法面试中出现频率都非常高但很有意思的是低难度的逆波兰表达式经常有人写错中等难度的压入弹出序列又经常有人想复杂。原因在于这两道题考的不是“会不会用栈”而是“对栈的执行过程理解得到不到位”。如果你正准备技术面试或者正在刷题阶段被这两道题卡住这篇的内容正好对应你的需求如果你已经刷过也建议看看后面的易错点总结很多细节是题解里不会写但面试官喜欢追问的。1.1 题目到底在考什么题目描述通常是这样的给你一个字符串数组 tokens它表示一个后缀表达式也叫逆波兰表达式里面只包含整数和加、减、乘、除四种运算符要求计算出结果。后缀表达式的形式和平时写的中缀表达式不一样比如3 4 表示的就是3 4而2 3 5 * 等价于2 3 * 5。它的核心特征是不需要括号也不需要讨论运算符优先级只要从左到右扫描一遍就能利用栈把结果算出来。面试官喜欢出这道题是因为它能在很短的代码里考察三件事第一你知不知道遇到运算符要从栈中弹出两个操作数第二你能不能正确区分哪一个先弹出的是右操作数、哪一个后弹出的是左操作数第三你对除法的截断规则这类边界细节是否敏感。很多候选人第一种都知道挂在第二种和第三种。先看一个最基础的手推过程假设 tokens 是[2, 1, , 3, *]扫描到 2 入栈1 入栈遇到加号弹出 1 和 2计算 2 1 3 并入栈再扫描到 3 入栈遇到乘号弹出 3 和 3计算 3 * 3 9。整个过程就是对“后进先出”最直观的运用越晚进栈的数字越早被取出来参与运算。1.2 弹出顺序减法除法最容易写反先声明一个很容易踩的坑从栈里弹出两个数时第一个弹出的数字一定是右操作数第二个弹出的数字才是左操作数。比如 tokens 是[2, 1, -]入栈后栈底是 2、栈顶是 1遇到减号时先弹出的是 1后弹出的是 2正确计算是 2 - 1 1。如果你先弹出的数当成左操作数写出了 1 - 2 -1结果就正好反了。加法乘法不受操作数顺序影响所以很多人在写加法和乘法时完全没感觉一遇到减法和除法就暴露了。我把这个顺序错误称为“减法翻车点”它出现的概率比你想的高很多尤其是面试时紧张的情况下。建议写代码时不要省变量明确写成right和left而不是弹出一个数算一个数这样既让自己不容易乱也让面试官一眼看出你懂顺序。除法还有一个隐蔽细节题目通常要求向零截断也就是商的小数部分直接丢掉而不是向下取整。Java 里两个整数相除本来就是向零截断比如-3 / 2结果是-1所以 Java 代码通常不需要额外处理。但如果你在简历上写了 Python就要小心了Python 的/会得到浮点数//是向下取整-3 // 2结果是-2。正确的做法是写成int(a / b)这样才能和题目的要求一致。这种语言差异在面试现场是非常受欢迎的追问点提前想清楚能留下好印象。1.3 标准解法与复杂度清晰标准的解法是这样的遍历 tokens 数组遇到数字就压入栈中遇到运算符就弹出两个操作数按照运算符计算再把结果压回栈里。等所有 token 都处理完栈里剩下的唯一数字就是表达式的值。public int evalRPN(String[] tokens) { DequeInteger stack new ArrayDeque(); for (String token : tokens) { if (token.equals() || token.equals(-) || token.equals(*) || token.equals(/)) { int right stack.pop(); int left stack.pop(); if (token.equals()) { stack.push(left right); } else if (token.equals(-)) { stack.push(left - right); } else if (token.equals(*)) { stack.push(left * right); } else { stack.push(left / right); } } else { stack.push(Integer.parseInt(token)); } } return stack.peek(); }这段代码有几个值得展开说的地方。第一这里用的是Deque而不是Stack。Java 的Stack继承了Vector为了线程安全加了不必要的同步开销而且官方文档也建议优先使用Deque来实现栈的语义。第二Integer.parseInt(token)可以直接解析负数比如 token 是-2会被正确识别为 -2前提是题目给的输入确实把负数作为独立 token。第三时间复杂度是 O(n)因为每个 token 最多入栈一次、出栈一次空间复杂度最坏也是 O(n)因为如果全是数字栈里会累积所有还未参与运算的操作数。这里的 n 是 tokens 数组的长度。1.4 数组模拟栈面试中能加分的写法如果面试官顺口问一句“有没有什么优化空间”你可以提到一个很实用的变体直接用数组模拟栈。虽然复杂度完全相同但数组实现避免了对象装箱和扩容的开销在实际运行中会更稳定尤其在大量压栈弹栈的场景下。public int evalRPN(String[] tokens) { int[] stack new int[tokens.length]; int top -1; for (String token : tokens) { if (token.equals()) { int right stack[top--]; int left stack[top--]; stack[top] left right; } else if (token.equals(-)) { int right stack[top--]; int left stack[top--]; stack[top] left - right; } else if (token.equals(*)) { int right stack[top--]; int left stack[top--]; stack[top] left * right; } else if (token.equals(/)) { int right stack[top--]; int left stack[top--]; stack[top] left / right; } else { stack[top] Integer.parseInt(token); } } return stack[top]; }这个版本在思路上没有任何变化只是把抽象的栈容器换成了数组和栈顶指针。如果你平时没写过这种写法不建议在面试中强行秀万一写乱了反而扣分但如果你提前练过面试官看到你会主动对比不同数据结构的性能特点通常会有好感。2. 从中缀到后缀面试官喜欢顺着追问的知识点逆波兰表达式求值讲得差不多了面试官很可能会追问后缀表达式是怎么来的你能不能把一个中缀表达式转成后缀表达式。这个问题出现过太多次了它才是逆波兰表达式这道题真正的进阶点。2.1 为什么需要后缀表达式人是习惯中缀表达式的比如3 4 * 2我们一眼就能根据优先级看出要先乘后加。但计算机扫描字符串时是按字符从左到右进行的如果直接处理中缀表达式遇到一个数字后不知道后面还有没有更高优先级的运算符处理起来非常麻烦。后缀表达式就是为了解决这个问题而存在的它把运算符放到对应操作数的后面让整个表达式变成“按实际计算顺序展开”的形态。比如3 4 * 2对应的后缀形式是3 4 2 * 意思是先把 4 和 2 相乘再把结果和 3 相加。一个比较生活化的类比是中缀表达式的规则像一段有嵌套结构和特殊优先级的文字直接读容易读错后缀表达式像一份已经排好序的操作清单只需要照单执行。计算机在后缀表达式下不需要考虑优先级、不需要处理括号从左到右扫一遍遇到数字就压栈遇到运算符就弹两个数运算整个过程非常机械也因此非常稳定。2.2 转后缀的两个核心规则中缀转后缀需要借助一个运算符栈规则可以概括为两条再加一条括号处理。第一条遇到操作数直接输出到结果里。第二条遇到运算符时先把栈顶所有“优先级不低于当前运算符”的运算符弹出并输出再把当前运算符压入栈。这里的“不低于”值得展开讲中缀表达式里优先级高的先算当新到的运算符优先级不高于栈顶运算符时说明栈顶那个运算符该先参与计算了所以要弹出去。同级运算符本身是按从左到右的顺序计算的所以栈顶同级的也要弹。唯一的例外是右结合的运算符比如幂运算那样的话要改成“栈顶优先级大于当前优先级才弹出”面试能主动提一句会显得你理解得很深。括号的处理是第三条规则左括号直接入栈而且在栈里它相当于一道屏障其他运算符碰到它都不能把它弹出遇到右括号时持续弹出并输出直到碰到左括号然后把这个左括号丢弃。2.3 一个完整的手推例子用3 4 * 2 / (1 - 5)来走一遍完整的转换过程。扫描到数字 3直接输出扫描到加号栈为空直接入栈扫描到 4输出扫描到乘号栈顶是加号优先级低于乘号所以乘号入栈扫描到 2输出。接着扫描到除号当前栈顶是乘号乘号和除号优先级相同按照“不低于”的规则把乘号弹出并输出加号优先级低于除号先留在栈里然后除号入栈。接下来扫描到左括号直接入栈。扫描到 1输出扫描到减号栈顶是左括号左括号是屏障不作为普通运算符参与比较所以减号直接入栈扫描到 5输出。然后遇到右括号持续弹出栈顶并输出弹出减号后栈顶是左括号于是把左括号弹出并丢弃。扫描结束后把栈里剩余的除号和加号依次弹出就得到3 4 2 * 1 5 - / 。你把这个后缀表达式代入第一节的求值流程4 乘 2 得 81 减 5 得 -48 除以 -4 得 -23 加 -2 得 1正好等于原式结果。这个例子把同优先级处理、左括号屏障、右括号清栈三个要点全部覆盖了建议面试前亲手写一遍。2.4 转换代码骨架与最容易被写漏的地方如果面试官要求现场写中缀转后缀下面这个核心版本基本够用。为了篇幅这里假设输入是单字符数字实际项目中处理多位数字还要拼接字符串但栈的核心逻辑和表达式长度无关。public String infixToPostfix(String s) { MapCharacter, Integer priority new HashMap(); priority.put(, 1); priority.put(-, 1); priority.put(*, 2); priority.put(/, 2); DequeCharacter stack new ArrayDeque(); StringBuilder result new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isDigit(c)) { result.append(c); } else if (c () { stack.push(c); } else if (c )) { while (stack.peek() ! () { result.append(stack.pop()); } stack.pop(); } else { while (!stack.isEmpty() stack.peek() ! ( priority.get(stack.peek()) priority.get(c)) { result.append(stack.pop()); } stack.push(c); } } while (!stack.isEmpty()) { result.append(stack.pop()); } return result.toString(); }这段代码里最容易写漏的是运算符入栈前 while 循环里的第二个条件stack.peek() ! (。如果没有它左括号会被普通运算符误弹出去整个括号结构就乱了。左括号的“屏障”作用必须显式处理普通运算符能压过它但不能弹出它只有右括号能唤醒它出栈。3. 栈的压入弹出序列用一次完整模拟破解合法性判定如果说逆波兰表达式考的是“你会不会用栈”那栈的压入弹出序列这道题考的就是“你懂不懂栈的完整操作过程”。题目常见描述是给定两个数组pushed和popped分别表示入栈顺序和出栈顺序判断popped是否可能是某个合法操作过程得到的出栈序列。这是一道非常经典的栈模拟题也是面试必刷原题里最容易“想当然”的一道。3.1 为什么不能靠“找规律”硬猜很多人的第一反应是总结规律比如“某个元素后面的元素必须按某个相对顺序出现”然后写一堆特殊判断。这种做法最大的问题是你很难证明这个规律在所有情况下都成立而且题目稍微变一变规律就失效。栈的入栈和出栈是交替进行的不是先全部入栈再统一出栈的简单模型所以光看元素之间的相对位置很容易误判。这里可以做一个生活化类比栈就像一条只能从一头进出的窄巷子先进去的车停在里面后进去的车挡在巷口。你想要的出车顺序必须满足“当前巷口的车如果不走后面的车就出不来”。这个动态约束过程用文字描述很容易绕晕直接让程序把整个过程演一遍反而更靠谱。模拟算法不是猜它把“入栈、出栈交替进行”这件事完整复现如果某一步模拟不了那就说明这个序列不合法。3.2 模拟过程的确定性它为什么一定正确模拟的核心是维护一个辅助栈和一个指针。指针popIndex指向popped中下一个期望出栈的元素。外层循环从左到右遍历pushed每压入一个元素到辅助栈就立刻检查栈顶元素是否等于popped[popIndex]如果相等就弹出并让popIndex向后移动。弹出之后辅助栈的新栈顶可能又是下一个期望元素所以要用 while 循环连续弹直到栈顶不再匹配为止。整个过程的关键在于“确定性”如果栈顶元素等于当前期望出栈的元素那么这一步当前的操作只能也必须让它出栈。稍微展开一下正确性论证假设这个栈顶元素就是下一次应该出栈的元素而你选择不弹它而是继续往栈里压入后面的元素。新压入的元素会挡在它上面它只会变得更晚出栈而更晚出栈就会和popped的顺序冲突所以这种情况只可能把流程拖死。反过来在该弹的时候弹出它并不会影响后续元素的入栈和出栈后面的元素仍然可以按标准流程继续。因此“能弹就立刻弹”的策略不会遗漏任何合法序列的可能。拿一个非法序列来完整验证一遍。pushed [1, 2, 3, 4, 5]popped [4, 5, 3, 1, 2]。按模拟流程走压入 1、2、3、4 后栈顶是 4正好匹配popped[0]弹出 4压入 5栈顶是 5匹配popped[1]弹出 5此时栈内从栈底到栈顶是 1、2、3期望弹出 3弹出 3。接着期望弹出 1但栈顶是 22 挡在 1 前面而pushed已经全部处理完没有办法再入栈元素。循环结束辅助栈不为空所以返回 false。这个例子把“看似差一点就合法”的序列剖析得很清楚问题就出在最后 2 堵住了 1。3.3 手写实现与边界细节public boolean validateStackSequences(int[] pushed, int[] popped) { DequeInteger stack new ArrayDeque(); int popIndex 0; for (int num : pushed) { stack.push(num); while (!stack.isEmpty() popIndex popped.length stack.peek() popped[popIndex]) { stack.pop(); popIndex; } } return stack.isEmpty(); }边界条件里有几个很实际的点。第一如果pushed和popped都为空返回 true循环直接跳过。第二while里为什么要加popIndex popped.length因为如果不加当所有元素都已经匹配弹出后popIndex可能越界访问。第三如果pushed非空而popped为空遍历完pushed后栈不为空返回 false这很自然因为只要有入栈动作就必须有对应的出栈操作。还有一点值得在面试中主动确认题目是否保证pushed和popped内部的元素互不相同大多数经典版本是互不相同的此时上面的模拟非常牢靠。但如果元素重复比如pushed [1, 1, 2]同样的值无法区分是哪一次入栈的元素题目难度会明显上升。考场上如果看到这道题先问清楚这个前提会让面试官觉得你考虑问题很全面。3.4 面试现场的表达话术这道题的代码量不大难点其实在表达上。面试官问到时可以按这个顺序讲第一步举一个小例子说明什么是合法序列比如pushed [1, 2, 3, 4, 5]、popped [4, 5, 3, 2, 1]它合法因为先压入 1、2、3压入 4 后立刻弹出 4压入 5 后立刻弹出 5再把 3、2、1 依次弹出即可。第二步说自己的策略维护一个栈只要栈顶和当前期待弹出的数字相同就立刻弹不同就继续从pushed里往栈中压数据。第三步简单论证正确性栈的操作是有先后顺序的模拟中每一次弹出都是被当前状态逼迫的不会错过合法序列。这样讲完再落笔写代码比沉默着直接写要稳得多。4. 这两道题背后的通用思路与可以延伸的同类题栈类题目表面五花八门但核心就是“后进先出的顺序问题”。把逆波兰表达式和压入弹出序列这两道题真正吃透之后你对栈的理解会比单纯刷十道重复题目深刻得多。这里聊几个高频的延伸方向。4.1 最小栈把辅助信息同步进栈一个很常见的变形题是设计一个栈支持 push、pop、top并且能在 O(1) 时间内获取最小值。很多人的第一反应是维护一个全局变量但问题在于 pop 操作会把这个最小值弹出去而你不知道上一个最小值是什么。解决办法是引入辅助栈主栈 push 元素时辅助栈 push 当前栈里的最小值主栈 pop 时辅助栈也 pop。这样辅助栈的栈顶永远记录着当前主栈状态下出现过的最小值。这和压入弹出序列有一个共同点都要求你理解“栈顶状态”和“历史状态”之间的关系。压入弹出序列关注操作顺序是否合法最小栈关注在操作过程中如何同步维护额外信息。两者都在训练你对栈状态机的理解理解了这一层后续做单调栈题目会顺很多。4.2 括号匹配与表达式解析类问题另一类常考的题是括号匹配、字符串解码、公式求值。这些题本质上在做同一件事用栈暂存“还没有处理完的上下文”。遇到左括号入栈遇到右括号出栈并匹配和第二节里中缀转后缀的括号处理方式如出一辙。逆波兰表达式求值、中缀转后缀、括号匹配这三道题可以说是一根藤上的三个瓜会了其中一个另外两个基本就通了一半。括号匹配还有个很经典的判断方式扫描字符串时如果是左括号就入栈如果是右括号先检查栈是否为空为空说明没有左括号可以匹配不为空就弹出栈顶检查是否和当前右括号是一对。扫描结束后栈必须为空。这个思路在应对“有效括号”这类高频原题时非常直接还经常和字符串解析题组合出现。4.3 合法出栈序列的总数卡特兰数如果面试官想考得更深还会问n 个互不相同的元素按固定顺序全部入栈可能的出栈序列一共有多少种答案是卡特兰数。推导这个结论的关键点是把一个入栈动作看作左括号一个出栈动作看作右括号全程必须满足任意前缀里入栈次数不少于出栈次数这样才能保证栈不为空等价于合法括号序列的计数。卡特兰数的公式是 C(2n, n) / (n 1)n 3 时对应 5 种合法出栈序列你可以自己用三元素栈列一列验证。这个知识点多数面试不会要求现场推导但如果能在答完压入弹出序列后顺带说一句“合法序列总数符合卡特兰数”会明显体现出你的知识广度。4.4 我刷这两道题的真实感受坦白说栈这个专题最怕的就是背模板。我见过有人能把逆波兰表达式的代码完整默写出来但把数字换成负数、把除法改成取模运算就立刻卡壳。背题永远跟不上改题。我的建议是每做完一道栈类题目都在纸上亲手模拟一遍数据流把每一步栈的状态画出来然后问自己一句“为什么这一步非这样做不可”。尤其是压入弹出序列这种模拟题多画几组合法和非法的例子比多做十道重复题更有效。刷题顺序上先做逆波兰表达式求值、括号匹配这类基础题再做中缀转后缀、压入弹出序列最后去碰单调栈相关的高频题这条路线对面试来说性价比很高。如果你正在准备算法面试希望这篇能帮你把“栈与队列”这个专题稳住真正掌握这两道必刷原题背后的通用思维。