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。注意步骤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完整走一遍看栈的变化：

得到后缀表达式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，因为 (1+2)*(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 stack

4.2 表达式转换中的典型错误

中缀转后缀的算法，新手最容易犯的错误是优先级比较方向搞反。比如遇到*时，如果只比较栈顶优先级是否小于当前运算符就弹出，那就变成低优先级先出来了，完全错误。我的记忆技巧是：栈顶优先级越高，说明它越“急着”被处理，所以当新的运算符到来时，优先级不低于新运算符的旧运算符都应该先输出。

另一个高频错误是括号处理。有些同学在遇到(时没有把它压入栈，或者压入后遇到)时只弹出而不丢弃左括号，导致输出的表达式里混着括号。这里要反复确认：

• 左括号入栈，只是为了在遇到右括号时把栈里的运算符“挡”在里面；
• 遇到右括号时，是从栈里依次弹出运算符直到左括号，然后丢弃左括号；
• 左括号本身绝不会出现在后缀表达式中。

括号问题最好的调试方式就是打印每一步的栈和输出，对照我上面给过的表格。动手模拟几遍，比死记规则强太多。

4.3 负数和多位数处理：实际工程里的额外难度

上面给的实现都假设操作数是非负整数。实际解析表达式时，最常见的问题是负数。比如-3 + 5，扫描器看到-时，它可能是一元运算符（表示负数），也可能是二元运算符（减法）。如何区分？

一个常见的规则是：如果-出现在表达式开头，或者紧跟在左括号或运算符后面，它就是一元的负号，这种情况下可以把-3当成一个单独的数字，或者把一元负号当作一个特殊的运算符来处理。如果-出现在操作数后面，它就是二元减法。

处理多位数也有讲究。如果输入是完整字符串"10+20"而不是按空格分好的 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

这个函数把"10+20"切成['10', '+', '20']，顺便跳过空格。配合前面的转换和求值代码，就能处理完整的表达式输入了。

4.4 从两个问题到一类问题：栈还能做什么

括号匹配和表达式求值解决的不只是两道题。理解了这两个例子之后，你可以很容易迁移到更多场景，比如：

• HTML/XML 标签闭合检查。和括号匹配几乎一模一样，只是把括号换成了标签名。
• 函数调用栈的模拟。递归函数的执行过程本质上就是栈的压入和弹出。
• 撤销操作。编辑器里的 Ctrl+Z，就是不断弹出最近一次操作。
• 深度优先搜索。显式用栈模拟递归，可以避免系统栈溢出的风险。

队列这边也有对应的经典应用：广度优先搜索、循环队列、生产者消费者模型等。如果你在做算法题时遇到“需要按顺序处理一批任务，但任务之间有依赖关系”的题目，先想想能不能用队列做层次遍历，再用栈解决嵌套问题，往往方向就对了。

我自己的经验是，把栈和队列学扎实，不只是在应付考试。日常写代码时，很多看似复杂的字符处理、树形遍历、任务调度逻辑，拆解到最后用的都是这两张表。数据结构不是一堆孤立的知识点，而是一套“用什么结构解决什么形态问题”的思考工具。理解了这个，再看到新的算法题，你的第一反应就不再是“背不背得下来”，而是“这个问题对应的结构是什么”。

这两个经典应用，值得反复手写几遍，直到不用查资料、不调试就能一次通过。能做到这个程度，栈和队列这一章才算真正过关。