栈与括号匹配：从合法判定到工程边界条件拆解

1. 先把“合法”两个字拆开看

帮朋友看代码的时候，他写的是一道入门题：给定一个字符串 s，判断里面括号的写法是否合法。他的代码我看两眼就发现了问题——他在数左括号和右括号的个数，相等就返回 true。这种写法在")("上会直接翻车。括号合法性判断这件事，看着像字符串处理，本质上是一次栈的扫描练习，也是我认为最能检验一个人有没有真正理解“后进先出”的题目。它不需要任何算法基础，但能把边界条件、判定顺序、数据结构选型这三件事一次性考完，所以值得认真拆一遍。

这篇文章面向两类人：一类是刚学完数组和循环、正在啃栈的同学，另一类是写了很久业务代码、但从来没系统整理过这类判定逻辑的从业者。我会从“合法”的定义讲起，把为什么不能计数、为什么栈是天然解、代码怎么写、坑在哪里，一层层拆开。所有代码都可以直接跑，用例我也会逐个手工推演，你可以对着抄，也可以看完思路自己重写一遍——后者效果更好。

题目本身通常会补一句：字符串里可能夹杂其他字符，比如字母、数字、标点，这些字符一律忽略，只看()、[]、{}三种括号。也有简化版本只考圆括号一种。这两种难度差一个量级，后面我会分开讲。先把通用版本吃透，单一括号的版本就是顺手的事。

1.1 合法的三条硬性标准

很多人对“合法”只有一个模糊感觉，落到代码上就写不严谨。我习惯把它拆成三条可以逐条验证的标准，写代码时一条一条对照，出错概率会低很多。

第一条是类型对应，左圆括号只能配右圆括号，左方括号只能配右方括号，不能交叉。第二条是顺序正确，任何一个位置往前看，右括号的数量都不能超过左括号——这个约束等价于“任何一个前缀里，未匹配的左括号数量不为负”。第三条是最终闭合，扫描完整个字符串后，不能有剩余的未匹配左括号。

这三条合起来才是完整的定义。少一条就会出现漏洞：只查第一条，")("会通过；只查第二条和第三条，"([)]"会通过。它们不是三个独立条件，而是同一件事从三个角度的描述，这也是为什么用“计数”这种降维手段一定做不对。

1.2 三个反例，看清计数法为什么必败

光说理论不够直观，我拿三个具体字符串走一遍，你就能感受到计数法的边界在哪里。

第一个是")("。左括号 1 个，右括号 1 个，数量相等，计数法判它合法。但读第一个字符时，栈里空着就来一个右括号，这在语义上等于“还没开门就进门了”，显然非法。这个反例打的是“顺序”这条标准。

第二个是"([)]"。四种括号各一个，数量完全对得上，甚至左右配型也能凑出来。但真实的嵌套关系是：左圆括号里面开了左方括号，然后先关了圆括号——方括号还开着呢。这个反例打的是“嵌套层级”这条标准，也是计数法最无解的漏洞，因为数量信息里根本不包含位置信息。

第三个是"((("。全是左括号，右括号 0 个，数量不相等，计数法能判对。但如果你的实现只比较了“左括号数 ≥ 右括号数”就返回 true，它又会漏掉。这个反例打的是“最终闭合”这条标准。

三个反例分别对应三条标准，你可以把它们记成一组自测用例。写完代码先拿这三个跑一遍，能全过再说别的。

1.3 栈为什么是天然解：从“最近的未闭合”说起

理解了三条标准，就能看出这道题真正的需求是什么：在任何时刻，我都需要知道“当前还没被闭合的、最近的那个左括号是什么类型”。注意两个关键词——最近和未闭合。最近，意味着后来者先处理；未闭合，意味着处理完就退出。这不就是后进先出吗？栈的所有特性都在这两个词里了。

打个生活里的比方：一摞盘子，你只能从最上面拿，也只能往最上面放。每次遇到左括号就是放一个盘子，遇到右括号就是拿走最上面那个盘子，并且要检查拿走的这个盘子是不是你要的那种。如果盘子摞是空的却要拿，说明右括号多了；如果顶上的盘子类型不对，说明嵌套交叉了；如果全部字符读完了盘子里还有剩，说明左括号多了。三种错误对应三个检查点，一一对应，不会有遗漏。

这就是为什么我说它是“天然解”——不是为了炫技才用栈，而是问题的语义本身就是一个栈结构。用数组模拟栈（append/pop）就够了，不需要引入任何标准库的容器，这也是面试和练习题里最常见的写法。

2. 核心实现：从思路到可运行代码

思路清楚了，接下来是把它变成代码。这一段我会把扫描过程的动作拆到最小粒度，然后给出 Python、C、JavaScript 三个版本。选这三个语言是因为它们分别代表了“动态类型 + 内置容器”“手动管理内存”“前端随手可跑”三种典型场景，其余语言照搬逻辑即可。

这里有一个前置约定要先讲清楚，否则代码写出来会有分歧：空字符串算不算合法？工程上通常算合法，因为没有未闭合的括号；但也有题目要求返回 false。我的建议是显式处理这一条，别依赖默认行为，注释写清楚“按题意，空串视为合法”。这种一句话注释，半年后你自己回头看会感谢当时的自己。

2.1 扫描过程中的四个动作

从左到右遍历字符串，每个字符只可能触发四种动作之一，这四步的顺序不能乱：

• 遇到左括号：压栈，继续下一个字符。
• 遇到右括号且栈为空：直接返回 false，不用再往下看了。
• 遇到右括号且栈非空：弹出栈顶，比对类型，不一致返回 false。
• 遇到其他字符：跳过，什么都不做。

第三和第二步的顺序是新手最容易写反的地方。如果你先pop再判空，栈空的时候就会抛异常或者越界；如果你先比对再判空，逻辑上也不对，因为栈空时根本没有“栈顶”可比对。正确的顺序永远是：先判空，再取栈顶，最后弹栈。

遍历结束后还有一个收尾动作：检查栈是否为空。空则合法，非空则说明有左括号没闭合。这一步漏掉，"((("这类输入就会被判成合法。我见过不少提交是死在这一行上的，包括我自己早年写的版本。

2.2 用映射表替代 if-else 链

判断类型对应关系，最直接的写法是三段if-else，但更清爽的做法是建一张映射表。这里有个小设计选择值得说一下：映射的方向应该是“右括号 → 左括号”，而不是反过来。

原因是我们的比对动作发生在遇到右括号的时候，此时手里拿的是右括号，栈顶是左括号。如果映射表是“右 → 左”，就可以写成“查表得到期望的左括号，和栈顶比较”，一行搞定，而且天然覆盖了“这个字符是不是右括号”的判断——查不到就不是右括号，直接跳过。如果反过来写成“左 → 右”，遇到右括号时你还得反向查找或者写两套逻辑，代码会立刻变丑。

这个小技巧在工程里很常见：让数据结构的方向匹配你使用它的方向。多花十秒钟想清楚这一点，能省掉后面一堆分支判断。

2.3 三种写法的落地代码

Python 版本最短，因为它有字典和列表，直接当栈用：

def is_valid(s: str) -> bool: pairs = {')': '(', ']': '[', '}': '{'} stack = [] for ch in s: if ch in '([{': stack.append(ch) elif ch in pairs: # 只有右括号会进这里 if not stack: # 先判空 return False if stack[-1] != pairs[ch]: # 再比对 return False stack.pop() # 最后弹栈 # 其他字符忽略 return not stack

C 版本需要自己维护一个数组当栈，重点在于指针含义要明确：top指向“下一个空位”，那么栈顶元素是stack[top - 1]，判空条件是top == 0。这种“指向空位”的约定比“指向栈顶元素”少一个初始值特判，我个人更推荐：

#include <stdbool.h> #include <string.h> bool isValid(const char *s) { char stack[10000]; int top = 0; /* top 指向下一个空位 */ for (int i = 0; s[i] != '\0'; i++) { char c = s[i]; if (c == '(' || c == '[' || c == '{') { stack[top++] = c; } else if (c == ')' || c == ']' || c == '}') { if (top == 0) return false; /* 先判空 */ char need = (c == ')') ? '(' : (c == ']') ? '[' : '{'; if (stack[top - 1] != need) return false; top--; /* 再弹栈 */ } } return top == 0; /* 收尾检查 */ }

JavaScript 版本和 Python 几乎同构，区别只在用Map还是普通对象。我倾向普通对象，够用且不需要额外构造：

function isValid(s) { const pairs = { ')': '(', ']': '[', '}': '{' }; const stack = []; for (const ch of s) { if ('([{'.includes(ch)) { stack.push(ch); } else if (ch in pairs) { if (stack.length === 0) return false; if (stack[stack.length - 1] !== pairs[ch]) return false; stack.pop(); } } return stack.length === 0; }

三段代码结构完全一致，这说明思路是对的。如果你用其他语言，照这个骨架翻译就行，唯一要小心的是字符串遍历方式和栈的索引约定，这两处是语言差异最大的地方。

2.4 边界条件清单

代码写完不算完，边界用例才是真正筛人的地方。我整理了一份清单，每次写这类判定逻辑都会过一遍：

其中最容易漏的是空串和单字符。空串在很多实现里会被“遍历结束检查栈为空”这条自动判成 true，看似不用特判，但如果题目约定不同，这里就是隐性 bug。单字符则是最小可复现的失败用例，调试时先跑它，能快速定位是判空写错还是收尾写错。

注意：如果你的判题环境输入可能包含全角括号（（）、【】），一定要单独确认。这类字符在 UTF-8 里是多字节的，C 语言的按字节遍历会读到半个字符，判断逻辑直接失效。

3. 完整实现与逐步推演

逻辑和代码都有了，这一段我想做两件事：一是把提前剪枝这类小幅优化讲清楚，二是拿几个用例在纸面上走一遍，让你看到栈是怎么一步步变化的。很多人写完代码直接提交，靠判题结果反推对错，这种习惯在简单题上还行，题目一复杂就会卡死。能手工推演，才是真的掌握了。

3.1 主流程与提前剪枝

主流程就是前面那四步加收尾，没什么可说的，值得展开的是提前退出。这个思路在工程里叫 fail-fast：一旦发现不可能合法，立刻返回，不要浪费后面的计算。

最有效的剪枝是长度检查。如果只保留括号字符，剩下的长度一定是偶数——每个左括号都要有一个右括号配对。所以可以在扫描前先扫一遍过滤，或者更省事一点：直接判断原串长度的奇偶性，如果原串长度是奇数，那么过滤后必然也是奇数，直接返回 false。注意这个剪枝只在“字符串里全是括号”的版本里成立，如果允许夹杂其他字符，原串长度奇偶就失去意义了，得先过滤再判。

第二个提前退出点在循环内部，就是遇到右括号且栈空时直接返回。这个前面提过，但它作为剪枝的价值值得单独强调：对于")" + "a" * 1000000这种输入，好的实现是 1 次比较就返回，差的实现会照样遍历到底。输入规模一大，差距就出来了。

3.2 典型用例的手工推演

拿"{[()]}"走一遍，我把它记成表格：

再拿"([)]"走一遍，重点看第 4 步：

注意第 3 步的错误不是“少了括号”，而是“顺序错了”。如果只看数量，这个串完全合法；只有把栈顶摊开看，才能发现方括号被压在圆括号上面，而圆括号先要求闭合。这就是栈相比计数器提供的关键信息增量。

第三个例子"())"，问题出在最后一步：第 3 个字符是右括号，此时栈已经空了，直接返回 false。如果实现里把判空写在pop后面，这里就会越界。

3.3 变体改造：从单一括号到任意字符混排

原题有几种常见变体，改法都很小，但值得过一遍，因为它们是同一个思路的不同投影。

第一种是只考圆括号。这时候可以不用栈，用一个计数器：遇(加一，遇)减一，中途变负返回 false，结尾必须为零。空间从 O(n) 降到 O(1)，是很实用的优化。但要注意，这个技巧只对单一类型有效，一旦出现两种以上括号就不成立了，因为计数器无法区分类型。

第二种是只允许括号字符。如果题目保证输入只含六种括号，那就不需要else分支跳过，代码能再短两行。但我不建议为了短这两行牺牲通用性，多一个else什么都不做反而更稳——万一输入里混了个空格，你的代码不会挂。

第三种是要求返回出错位置而不是布尔值。改法是把return false换成return i，把收尾的return not stack换成return -1 if not stack else len(s)（表示末尾缺闭合）。位置信息在真实场景里更有用，比如编辑器做实时语法提示，你需要告诉用户“第 12 个字符这里的括号不对”。

第四种是把字母也当成一种括号，比如要求a与A配对。这种改法只需要扩展映射表，主流程一个字都不用动——这正是前面强调“用映射表而不是 if-else 链”的回报。

4. 踩坑记录与排查技巧

这一段是整篇里我最想写实的部分。下面这些坑，有的是我自己踩的，有的是帮别人看代码时反复见到的，共同点是它们都不会在“正常输入”下暴露，只会在特定用例上突然炸掉，然后你盯着代码半天看不出问题。

4.1 判定顺序写反，结果全错

最典型的一种：先pop再判空。看起来只差一行顺序，后果是两条错误路径全乱。栈空时pop要么抛异常（Python、JS 的pop()在空数组上返回 undefined，后续比对也不报错，反而更隐蔽），要么读到脏数据（C 语言里stack[top-1]在top==0时读到的是数组外或旧值）。Python 和 JS 的“不报错”特性让这个 bug 极难发现，因为它会静默地拿undefined去比对，结果恰好是 false，在多数用例上表现正确，只在个别地方翻车。

排查方法很简单：拿")"单独测一次。如果程序抛异常、或者返回了意料之外的值，就是顺序问题。修法只有一条：判空永远在取栈顶之前，取栈顶永远在弹栈之前。

4.2 遍历结束忘记检查栈

第二种高频错误是循环结束后直接return true。这样"((("会被判合法。更隐蔽的情况是输入末尾有未闭合的左括号，前面所有配对都对，最后一个没关——只看循环内部逻辑完全正确，就是收尾漏了一行。

这个 bug 的排查成本很低，但要养成习惯：写完循环就问自己一句“循环正常结束后，还有什么状态没检查”。在这里答案是“栈里可能还有残留”。类似的思路可以迁移到很多题上，比如深度优先搜索结束后要检查是否所有节点都访问过。

4.3 常见问题速查表

我把实际遇到过的现象和原因整理成下面这张表，调试时可以直接对照：

最后一行值得展开说一下。有人为了“过滤掉非括号字符”，在循环里写s = s.replace(ch, '')之类的操作，这会让整体复杂度从 O(n) 退化成 O(n²)。正确做法是一次遍历完成过滤，或者干脆不预处理，在扫描时直接跳过。这类“看起来更简洁、实际更慢”的写法在很多题里都有，判别方法就是看循环内部有没有对整串做操作。

提示：调试这类题时，把栈内容打印出来比单步跟踪高效得多。每次入栈出栈打一行，出错的那一步会非常显眼。

5. 复杂度分析与进阶延伸

题目做对了，还可以再往下走一步，看看这个解法的边界在哪，以及它能延伸出哪些更有意思的问题。这一步不做也不影响正确性，但做了之后，你对这类问题的理解会从“会写”变成“会用”。

5.1 时间与空间的上界在哪

时间复杂度是 O(n)，因为每个字符最多被处理一次，入栈出栈各一次，都是常数操作。这里没有嵌套循环，也没有回溯，是最优的一档。空间复杂度是 O(n)，最坏情况出现在"((((((("这种全左括号的输入上，栈会撑到和字符串一样长。平均来看要小很多，因为配对会及时弹出。

如果要抠空间，单一括号版本可以用计数器做到 O(1)，但多种括号版本做不到——你没法用一个数字表示“三种括号各自的未闭合层数”，那本质上还是一个栈。有人尝试用三个计数器分别统计，这在"([)]"上会失效，因为计数器丢失了层级顺序信息。所以 O(n) 空间在这里是有必要的，不是实现不够聪明。

5.2 三个值得顺手练的变体

第一个是最长有效括号长度。给定一个可能不合法的字符串，求其中最长的合法子串长度。这题用栈可以做，但需要往栈里先压一个哨兵下标-1，然后靠下标差算长度，思路会绕一个弯。我第一次写的时候卡了很久，因为习惯了只存字符，没想到栈里可以存下标。

第二个是括号生成。给定 n 对括号，列出所有合法组合。这是回溯的经典题，约束条件是“已用左括号数 ≥ 已用右括号数”，和本文的判定标准第二条同源。做完这道题再回头看判断合法性，你会发现两者其实是一枚硬币的两面。

第三个是删除最少的括号使其合法。这题的关键是把“判定”和“修复”分开：先扫一遍标记出哪些字符是非法的，再一次性删除。用栈记录未匹配的左括号下标，同时用一个集合记录需要删除的右括号下标，最后拼接。这类“先标记后处理”的模式在文本编辑、格式化工具里非常常见。

我在实际项目里遇到过类似的需求：解析一段配置文件时，需要检查花括号是否配对，并给出精确的错误行号。当时用的就是本文这个栈的骨架，只是把位置信息一起压栈了。所以别觉得这是道纯粹的练习题，它的骨架在真实代码里出现的频率比你想的高。

最后分享一个我自己的习惯：每写完一个判定类函数，我都会在脑子里准备三个用例——一个最小合法、一个最小非法、一个“看起来合法其实非法”。第三个最难想，但往往能抓到真正的 bug。这道题里，它就是"([)]"。