栈与队列经典应用：括号匹配与表达式求值详解

1. 栈与队列的底层逻辑为什么这两个问题是经典入门题先聊点背景。刚接触数据结构时很多人会有一个困惑栈和队列不就是两个很简单的线性结构吗一个后进先出一个先进先出规则几句话就讲完了有什么好学的恰恰因为简单它们才是研究算法思想最好的载体。括号匹配和表达式求值这两个问题把“后进先出”这个抽象规则落地成了两个具体场景一个教你用栈处理嵌套关系一个教你用栈管理运算优先级。可以说这两个题目不是拿来背答案的而是拿来理解“数据结构到底是怎么解决问题的”。先说栈。你可以把栈想象成一叠盘子你总是从最上面拿盘子放盘子也放在最上面。浏览器里的“后退”按钮就是栈的典型应用——你访问的页面按顺序被压进栈里点一次后退就弹出最近访问的那一页。栈的操作只有两个核心动作push压入和 pop弹出再加上一个 peek 操作看栈顶元素而不弹出。就这点东西却能解决很多看起来颇为复杂的算法问题。队列则正好相反像食堂打饭排队先到的人先打到饭。先进先出。它在后面的应用里更多出现在任务调度、消息队列、广度优先搜索这类场景中。括号匹配和表达式求值本身只需要栈但学习过程中把队列放在一起对比着理解能帮你建立“不同结构解决不同问题”的直觉。这两个问题为什么适合放在一起讲因为它们会反复用到同一个技术点“栈顶是当前最近的未决状态”。括号匹配时栈顶是最近一个还未闭合的左括号表达式求值时栈顶是当前优先级最高的待处理运算符。抓住“最近”这两个字就抓住了栈的灵魂。我见过很多初学者把代码背下来却不懂原理换一道题就完全不会了。所以这篇文章不准备只给结论每一个步骤我都会解释“为什么这样做”每个关键操作都会说明背后的逻辑。你看完之后应该能做到不仅会写这两道题还能理解这类问题的通用解法套路。2. 括号匹配问题朴素解法的困境与栈的破局2.1 问题定义与常规思路括号匹配问题描述起来非常直白给定一个只包含括号字符的字符串判断其中的括号是否合法闭合。例如()[]{}是合法的([)]是不合法的((()))是合法的(()是不合法的。这里的“合法”包含两层含义第一左右括号数量要相等第二括号的嵌套顺序要正确。第二点往往是被初学者忽略的关键。先别急着用栈。你也许会想用计数器行不行维护一个计数器遇到左括号加一遇到右括号减一最后判断是否为0这个思路能解决只有一种括号的情况。比如只有圆括号时(()计数最终是1确实能判断非法(())计数是0判断合法。但一旦引入多种括号计数器就完全失效了。看一个例子([)]如果用三种计数器分别计数左括号和右括号的数量是匹配的但这个字符串明显不合法——交叉嵌套了正确的写法应该是([])或者()[]。那问题就变成了如何判断括号的“交叉”情况这里要抓住一个核心观察在任意时刻最近出现的那个未匹配左括号必须匹配接下来出现的第一个右括号。换句话说右括号应该和它左边最近的左括号配对。这种“最近匹配”关系和“后进先出”形成了精确的对应——栈顶就是那个“最近的未决状态”。2.2 栈解法的一步步推导理解了“最近匹配”原则算法就水到渠成了遍历字符串的每一个字符。如果是左括号(、[、{把它压入栈中。如果是右括号)、]、}先看栈顶。如果栈顶是对应的左括号说明这左右两个括号匹配弹出栈顶如果栈顶不是对应的左括号说明交叉了直接判定不合法。遍历完所有字符后如果栈是空的说明所有括号都正确闭合了如果栈里还有剩余的左括号说明有左括号没被闭合不合法。等一下为什么“栈顶不是对应的左括号”就能断定交叉你可以这样想栈里保存的都是还没匹配的左括号。最晚压入的那个左括号在嵌套顺序上处于最内层它必须最先被匹配。如果遍历到的右括号和栈顶的左括号不是一套比如栈顶是[来了个)那这个右括号想和栈里更底层的某个左括号匹配但中间隔着一个更内层的[还没闭合。这就形成了([)这种交叉结构自然是非法的。还有一个边界情况需要注意遍历到右括号时如果栈本身是空的说明出现了孤立的右括号比如())这种情况也要判定非法。2.3 代码实现与细节分析用 Python 写代码非常简洁def is_valid_brackets(s: str) - bool: stack [] # 建立右括号到对应左括号的映射方便配对判断 mapping {): (, ]: [, }: {} for char in s: if char in mapping: # 当前字符是右括号 # 栈为空或者栈顶不是对应的左括号说明不匹配 if not stack or stack[-1] ! mapping[char]: return False stack.pop() # 匹配成功弹出栈顶 else: # 当前字符是左括号 stack.append(char) # 遍历结束后栈为空才是合法表达式 return not stack这里有三个实现细节值得展开讲讲。第一为什么用字典做映射因为把“右括号到左括号的对应关系”显式声明出来配对判断的逻辑就变成了一次查表操作清晰且不易出错。换用 if-else 当然也可以但代码会显得冗长。第二stack[-1]取栈顶的操作。Python 列表的-1索引直接访问最后一个元素时间复杂度是 O(1)不会额外增加开销。这里我刻意没有用 pop 直接取出来而是先 peek 再 pop分两步写这样在判断失败时没有副作用逻辑更清晰。第三判断完成的标志是stack为空而不仅仅是有没有返回过 False。因为前面只是在中途检查了非法情况如果所有括号都正常嵌套但最后栈里剩下了多余的左括号比如((()遍历结束后的return not stack会正确返回 False。2.4 边界条件与变体问题括号匹配看起来简单但面试和考试中经常出现的变体才是真正拉开差距的地方。整理几个我实际见过的出题方向。变体一字符串里混有普通字符。比如要判断一段代码文件里的括号是否正确。解法很简单遍历时忽略非括号字符即可。上面代码只对括号字符做了判断混入字母、数字、空格都不影响正确性因为非括号字符根本不会进入任何分支。变体二找出第一个非法位置。有些题目不让你直接返回 True/False而是要你报告“在第几个字符上出了问题”。做法是在遍历时维护一个当前位置计数遇到孤立右括号时返回当前索引遍历结束后栈里还有左括号时返回第一个未匹配左括号的索引。这需要栈里不仅存括号字符还要存字符位置def first_invalid_pos(s: str) - int: stack [] # 栈里存 (字符, 索引) mapping {): (, ]: [, }: {} for idx, char in enumerate(s): if char in mapping: if not stack or stack[-1][0] ! mapping[char]: return idx stack.pop() elif char in ([{: stack.append((char, idx)) # 栈不为空返回第一个未匹配左括号的位置 return stack[0][1] if stack else -1变体三最少要添加几个括号才能让字符串合法。这是一道经典的动态规划题但也有用栈的解法。思路是遍历时遇到左括号入栈遇到右括号时如果栈空说明需要一个左括号来匹配它答案加一否则弹出栈顶。遍历结束后栈里剩余的左括号个数就是需要补充的右括号数量。两者相加就是最少添加次数。def min_add_to_make_valid(s: str) - int: stack [] ans 0 for char in s: if char (: stack.append(char) else: if stack: stack.pop() else: ans 1 # 缺少左括号 return ans len(stack) # 剩余左括号需要右括号匹配这个思路在 LeetCode 上有对应的原题可以拿来验证一下。做一个提示处理括号匹配时如果可以用栈尽量别用计数器。计数器只能在单一括号类型下工作一旦引入嵌套或多种括号就会出错。3. 表达式求值问题两个阶段拆解中缀、后缀的转换3.1 从“人类习惯”到“计算机习惯”的思维切换表达式求值是栈的另一个经典战场。我们日常写作的表达式比如3 5 * 2 - 8 / 4叫中缀表达式。运算符在两个操作数中间。这种写法对人类很友好因为有括号和运算符优先级规则配合读起来很自然。但对计算机来说中缀表达式反而是最难处理的一个表达式里可能既有括号又有不同优先级的运算符你必须在运算过程中不断回看、调整顺序。举个例子3 5 * 2你不能从左到右直接算因为乘法优先级大于加法得先算5 * 2再把结果加给3。这个过程在代码里怎么实现如果只按从左到右的顺序扫描那到号时根本不知道是否应该先执行它。有没有一种表达方式让运算顺序完全线性化不需要优先级规则也不需要括号有。这就是后缀表达式也叫逆波兰表达式。它的特点是运算符写在操作数后面比如3 5 * 2写成后缀是3 5 2 * 。还有一个配套的是前缀表达式波兰表达式运算符写在操作数前面3 5 * 2写成 3 * 5 2。后缀表达式的优势在于完全没有优先级和括号的困扰从左到右扫描一遍就能算出来。这正好和计算机的线性扫描处理方式相契合。3.2 后缀表达式求值先学会这半部分先讲求值因为后缀表达式求值是理解“为什么要转换”的最好入口。算法规则只有三条遇到操作数数字压入栈。遇到运算符从栈中弹出两个操作数先弹出的在右边注意这个顺序后面会细说后弹出的在左边执行运算把结果压回栈。扫描结束后栈顶就是整个表达式的值。以3 5 2 * 为例逐步走一遍步骤扫描到操作栈内容栈底→栈顶13数字入栈325数字入栈3, 532数字入栈3, 5, 24*弹出2和5计算5 * 2 10入栈3, 105弹出10和3计算3 10 13入栈13最终结果是 13。注意步骤4里弹出的第一个操作数是2也就是右操作数后弹出来的是5即左操作数。因为没有交换律的运算符比如减法和除法顺序尤其重要。比如后缀表达式6 2 /正确的计算是6 / 2 3如果搞反了就会得到2 / 6小数除法还算不出整数结果直接出错。代码实现也非常直观def eval_postfix(tokens): stack [] for token in tokens: if token.isdigit(): stack.append(int(token)) else: right stack.pop() # 先弹出的是右操作数 left stack.pop() # 后弹出的是左操作数 if token : stack.append(left right) elif token -: stack.append(left - right) elif token *: stack.append(left * right) elif token /: stack.append(int(left / right)) # 处理整除注意 C 语言风格 return stack[-1]这里关于除法的处理在部分语言如 Python 3里/是浮点除法在另一些环境如 C、Java 整数除法里是整除。如果题目约定输入都是整数并且要求整数结果建议用int(left / right)做显式转换如果想保留精度就得统一用浮点数处理。3.3 中缀转后缀算法流程与优先级表现在到了重头戏也是整个表达式求值中最容易出错的一步中缀表达式转后缀表达式。算法依然用栈而且栈的作用是存放“暂时无法确定执行顺序的运算符”。具体流程遇到操作数时直接输出加入到后缀表达式的列表中。遇到左括号(时压入栈。遇到右括号)时不断弹出栈顶运算符并输出直到弹出左括号(为止。这个左括号本身不输出只是被丢弃。遇到运算符、-、*、/时比较它和栈顶运算符的优先级如果栈为空或者栈顶是左括号当前运算符直接入栈否则弹出栈中所有优先级大于等于当前运算符的运算符并输出然后把当前运算符入栈。扫描结束后将栈中剩余的所有运算符依次弹出并输出。优先级表用字典维护最方便precedence {: 1, -: 1, *: 2, /: 2}这里需要仔细解释一下“弹出栈中所有优先级大于等于当前运算符的运算符”这条规则。为什么是“大于等于”而不是“大于”考虑表达式3 - 5 2。从左到右扫描3输出。-入栈。5输出。要入栈了。此时栈顶是-优先级和相同。如果只弹出优先级大于当前运算符的那-不会被弹出直接入栈栈里变成-, 。2输出。结束依次弹出栈中运算符得到-、。最终后缀表达式是3 5 - 2 。计算一下3 - 5 -2-2 2 0结果是 0。而原式3 - 5 2从左到右算也确实是 0。再看如果改成用“大于”即只有严格高优先级才弹出同样步骤栈顶-还在入栈生成的后缀表达式还是3 5 - 2 。看起来结果一样那为什么还需要“等于”看一个不同例子8 / 4 / 2。如果只弹出优先级高于当前运算符的那么遇到第二个/时栈顶/优先级等于当前运算符不弹出后缀表达式为8 4 / 2 /计算是(8/4)/2 1。但注意原式8 / 4 / 2从左到右也是(8/4)/2 1好像也没问题。换个角度8 / 2 / 4。遇到第二个/时栈顶还是/不弹出的话后缀是8 2 / 4 /计算(8/2)/4 1原式也是 1。似乎同优先级不弹出也不出错再试减法8 - 3 - 2。遇到第二个-时栈顶是-不弹出后缀是8 3 - 2 -计算(8-3)-2 3原式也是 3。试到这里好像没发现区别别急因为都是同优先级运算符连续且左结合性天然匹配。但如果是3 - (2 - 1)这种带括号的表达式呢括号本身会强制改变顺序跟这个规则无关。真正体现“等于”必要性的场景是当两个同优先级运算符中间隔着一个更低优先级的运算符时。不过表达式里运算符是线性的低优先级运算符本身会留在栈中挡住高优先级所以一般不会产生问题。其实严格来说对于左结合的运算符加减乘除都是左结合弹出“大于等于”是为了保证同优先级运算符从左到右的运算顺序如果只弹出“大于”某些特殊情况下会产生右结合的效果导致错误。为了保险和统一业内标准做法就是“大于等于”或简化为“大于等于当前优先级就弹出”。这也是很多参考书给出的规则直接按这个写不会错。再看一个例子3 4 * 2 (1 - 5)这里不用比较运算只是展示括号逻辑。拿经典表达式3 5 * 2 - 8 / 4完整走一遍看栈的变化步骤扫描到操作栈内容输出序列13数字直接输出空32栈空入栈335数字直接输出3 54*栈顶优先级低于*入栈, *3 552数字直接输出, *3 5 26-弹出*、它们优先级都大于等于-然后-入栈-3 5 2 * 78数字直接输出-3 5 2 * 88/栈顶-优先级低于/入栈-, /3 5 2 * 894数字直接输出-, /3 5 2 * 8 410结束依次弹出栈中运算符空3 5 2 * 8 4 / -得到后缀表达式3 5 2 * 8 4 / -求值(3 5×2) - (8÷4) 13 - 2 11和原式结果一致。3.4 中缀转后缀的完整代码实现写代码时要注意几个细节操作数可能是多位数比如10 20操作符可能是字符串形式的表达式。以下实现针对“以空格分隔的 token 列表”输入这对调试最友好def infix_to_postfix(tokens): precedence {: 1, -: 1, *: 2, /: 2} stack [] output [] for token in tokens: if token.isdigit(): # 操作数直接输出 output.append(token) elif token (: stack.append(token) elif token ): while stack and stack[-1] ! (: output.append(stack.pop()) stack.pop() # 丢弃左括号 else: # 运算符 # 弹出所有优先级大于等于当前运算符的栈顶运算符 while (stack and stack[-1] ! ( and precedence.get(stack[-1], 0) precedence[token]): output.append(stack.pop()) stack.append(token) while stack: output.append(stack.pop()) return output如果你是初学者有一个容易犯的错precedence.get(stack[-1], 0)这里为什么返回0因为栈顶可能是左括号而左括号不该参与优先级比较。括号在栈中的唯一作用就是与右括号配对配对时直接弹出在运算符入栈步骤如果栈顶是左括号则当前运算符应该直接入栈不能弹出括号。所以用一个 get 默认值 0 可以处理这类情况。不过上面的代码已经用stack[-1] ! (做了显式检查get 的默认值只是保险两种写法都行。实际项目中我建议保留显式检查更清晰。3.5 完整流程串联从输入到结果有了两步之后整个表达式求值的流程就拼起来了def evaluate_infix(tokens): postfix infix_to_postfix(tokens) return eval_postfix(postfix) # 测试 expr [(, 1, , 2, ), *, (, 3, -, 4, )] print(evaluate_infix(expr)) # 输出 -3因为 (12)*(3-4) 3*(-1) -3这个流程把问题拆成了两个独立的子问题每个子问题都能单独测试。这是一种非常实用的工程思路复杂问题先拆成多个简单环节每个环节分别验证再拼装。在实际开发中遇到表达式解析需求时这个思路也适用。另一种思路是直接在扫描中缀表达式的同时进行求值即“边解析边算”只需要一个操作数栈和一个运算符栈但逻辑会复杂不少。手写表达式求值代码时我建议先走“中缀转后缀再求值”这条清晰的路虽然多了一次遍历但代码好维护、好排查问题。4. 常见错误、调试技巧与扩展应用4.1 括号匹配中容易踩的坑我见过不少同学在遇到()[{]这种混杂交错的例子时出错根本原因是忽略了“最近配对”原则。这里有一个很好的自测方法用一个简单的模拟人脑算法——每看到一个右括号就往前找最近的且未匹配的左括号如果它和当前右括号不匹配那字符串就是非法的。栈的 pop 顺序恰好复现了这个过程。另一个常见错误是扫描结束后忘记检查栈是否为空。比如字符串((())遍历过程中没有出现任何栈顶不匹配的情况但如果遍历结束后不看栈里还剩一个左括号就会错误地返回 True。很多代码之所以在简单测试用例上通过、在复杂用例上失败往往就是这个原因。排查这个问题最快的方法是把return not stack这行加打印看看扫描结束后的栈def is_valid_brackets_debug(s: str) - bool: stack [] mapping {): (, ]: [, }: {} for char in s: if char in mapping: if not stack or stack[-1] ! mapping[char]: print(f非法遇到孤立或不匹配的右括号 {char}) return False stack.pop() else: stack.append(char) print(f遍历结束栈中剩余 {len(stack)} 个左括号) return not stack4.2 表达式转换中的典型错误中缀转后缀的算法新手最容易犯的错误是优先级比较方向搞反。比如遇到*时如果只比较栈顶优先级是否小于当前运算符就弹出那就变成低优先级先出来了完全错误。我的记忆技巧是栈顶优先级越高说明它越“急着”被处理所以当新的运算符到来时优先级不低于新运算符的旧运算符都应该先输出。另一个高频错误是括号处理。有些同学在遇到(时没有把它压入栈或者压入后遇到)时只弹出而不丢弃左括号导致输出的表达式里混着括号。这里要反复确认左括号入栈只是为了在遇到右括号时把栈里的运算符“挡”在里面遇到右括号时是从栈里依次弹出运算符直到左括号然后丢弃左括号左括号本身绝不会出现在后缀表达式中。括号问题最好的调试方式就是打印每一步的栈和输出对照我上面给过的表格。动手模拟几遍比死记规则强太多。4.3 负数和多位数处理实际工程里的额外难度上面给的实现都假设操作数是非负整数。实际解析表达式时最常见的问题是负数。比如-3 5扫描器看到-时它可能是一元运算符表示负数也可能是二元运算符减法。如何区分一个常见的规则是如果-出现在表达式开头或者紧跟在左括号或运算符后面它就是一元的负号这种情况下可以把-3当成一个单独的数字或者把一元负号当作一个特殊的运算符来处理。如果-出现在操作数后面它就是二元减法。处理多位数也有讲究。如果输入是完整字符串1020而不是按空格分好的 token 列表就需要一边扫描一边累积数字def tokenize(expr: str): tokens [] i 0 while i len(expr): ch expr[i] if ch.isdigit(): num 0 while i len(expr) and expr[i].isdigit(): num num * 10 int(expr[i]) i 1 tokens.append(str(num)) else: if ch ! : tokens.append(ch) i 1 return tokens这个函数把1020切成[10, , 20]顺便跳过空格。配合前面的转换和求值代码就能处理完整的表达式输入了。4.4 从两个问题到一类问题栈还能做什么括号匹配和表达式求值解决的不只是两道题。理解了这两个例子之后你可以很容易迁移到更多场景比如HTML/XML 标签闭合检查。和括号匹配几乎一模一样只是把括号换成了标签名。函数调用栈的模拟。递归函数的执行过程本质上就是栈的压入和弹出。撤销操作。编辑器里的 CtrlZ就是不断弹出最近一次操作。深度优先搜索。显式用栈模拟递归可以避免系统栈溢出的风险。队列这边也有对应的经典应用广度优先搜索、循环队列、生产者消费者模型等。如果你在做算法题时遇到“需要按顺序处理一批任务但任务之间有依赖关系”的题目先想想能不能用队列做层次遍历再用栈解决嵌套问题往往方向就对了。我自己的经验是把栈和队列学扎实不只是在应付考试。日常写代码时很多看似复杂的字符处理、树形遍历、任务调度逻辑拆解到最后用的都是这两张表。数据结构不是一堆孤立的知识点而是一套“用什么结构解决什么形态问题”的思考工具。理解了这个再看到新的算法题你的第一反应就不再是“背不背得下来”而是“这个问题对应的结构是什么”。这两个经典应用值得反复手写几遍直到不用查资料、不调试就能一次通过。能做到这个程度栈和队列这一章才算真正过关。