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 stackC 版本需要自己维护一个数组当栈重点在于指针含义要明确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按约定空串是否单独处理(false遍历结束栈非空)false栈空时遇右括号()true最基本配对([{}])true多层嵌套([)]false交叉嵌套()[]{}true并列平铺a(b)ctrue夹杂其他字符(((((((false深嵌套且未闭合其中最容易漏的是空串和单字符。空串在很多实现里会被“遍历结束检查栈为空”这条自动判成 true看似不用特判但如果题目约定不同这里就是隐性 bug。单字符则是最小可复现的失败用例调试时先跑它能快速定位是判空写错还是收尾写错。注意如果你的判题环境输入可能包含全角括号、【】一定要单独确认。这类字符在 UTF-8 里是多字节的C 语言的按字节遍历会读到半个字符判断逻辑直接失效。3. 完整实现与逐步推演逻辑和代码都有了这一段我想做两件事一是把提前剪枝这类小幅优化讲清楚二是拿几个用例在纸面上走一遍让你看到栈是怎么一步步变化的。很多人写完代码直接提交靠判题结果反推对错这种习惯在简单题上还行题目一复杂就会卡死。能手工推演才是真的掌握了。3.1 主流程与提前剪枝主流程就是前面那四步加收尾没什么可说的值得展开的是提前退出。这个思路在工程里叫 fail-fast一旦发现不可能合法立刻返回不要浪费后面的计算。最有效的剪枝是长度检查。如果只保留括号字符剩下的长度一定是偶数——每个左括号都要有一个右括号配对。所以可以在扫描前先扫一遍过滤或者更省事一点直接判断原串长度的奇偶性如果原串长度是奇数那么过滤后必然也是奇数直接返回 false。注意这个剪枝只在“字符串里全是括号”的版本里成立如果允许夹杂其他字符原串长度奇偶就失去意义了得先过滤再判。第二个提前退出点在循环内部就是遇到右括号且栈空时直接返回。这个前面提过但它作为剪枝的价值值得单独强调对于) a * 1000000这种输入好的实现是 1 次比较就返回差的实现会照样遍历到底。输入规模一大差距就出来了。3.2 典型用例的手工推演拿{[()]}走一遍我把它记成表格步骤字符动作栈内容底→顶1{左括号入栈{2[左括号入栈{ [3(左括号入栈{ [ (4)查表期望(栈顶(弹出{ [5]查表期望[栈顶[弹出{6}查表期望{栈顶{弹出空结束—栈为空true再拿([)]走一遍重点看第 4 步步骤字符动作栈内容1(入栈(2[入栈( [3)期望(栈顶是[不匹配返回 false注意第 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]在top0时读到的是数组外或旧值。Python 和 JS 的“不报错”特性让这个 bug 极难发现因为它会静默地拿undefined去比对结果恰好是 false在多数用例上表现正确只在个别地方翻车。排查方法很简单拿)单独测一次。如果程序抛异常、或者返回了意料之外的值就是顺序问题。修法只有一条判空永远在取栈顶之前取栈顶永远在弹栈之前。4.2 遍历结束忘记检查栈第二种高频错误是循环结束后直接return true。这样(((会被判合法。更隐蔽的情况是输入末尾有未闭合的左括号前面所有配对都对最后一个没关——只看循环内部逻辑完全正确就是收尾漏了一行。这个 bug 的排查成本很低但要养成习惯写完循环就问自己一句“循环正常结束后还有什么状态没检查”。在这里答案是“栈里可能还有残留”。类似的思路可以迁移到很多题上比如深度优先搜索结束后要检查是否所有节点都访问过。4.3 常见问题速查表我把实际遇到过的现象和原因整理成下面这张表调试时可以直接对照现象大概率原因修法空栈时程序崩溃先 pop 后判空调整判定顺序(((判为合法漏了收尾检查返回not stack([)]判为合法只比对数量没比对栈顶加栈顶类型比对映射表查不到就报错用了dict[key]而非.get()改为.get()或先判成员夹杂字母时判错把非括号字符也当成右括号处理加显式elif限定范围全角括号判错字节级遍历撕裂多字节字符按字符遍历或先做规范化长度超长时超时每次循环都做字符串拼接或查找预处理字符集避免 O(n²)最后一行值得展开说一下。有人为了“过滤掉非括号字符”在循环里写s s.replace(ch, )之类的操作这会让整体复杂度从 O(n) 退化成 O(n²)。正确做法是一次遍历完成过滤或者干脆不预处理在扫描时直接跳过。这类“看起来更简洁、实际更慢”的写法在很多题里都有判别方法就是看循环内部有没有对整串做操作。提示调试这类题时把栈内容打印出来比单步跟踪高效得多。每次入栈出栈打一行出错的那一步会非常显眼。5. 复杂度分析与进阶延伸题目做对了还可以再往下走一步看看这个解法的边界在哪以及它能延伸出哪些更有意思的问题。这一步不做也不影响正确性但做了之后你对这类问题的理解会从“会写”变成“会用”。5.1 时间与空间的上界在哪时间复杂度是 O(n)因为每个字符最多被处理一次入栈出栈各一次都是常数操作。这里没有嵌套循环也没有回溯是最优的一档。空间复杂度是 O(n)最坏情况出现在(((((((这种全左括号的输入上栈会撑到和字符串一样长。平均来看要小很多因为配对会及时弹出。如果要抠空间单一括号版本可以用计数器做到 O(1)但多种括号版本做不到——你没法用一个数字表示“三种括号各自的未闭合层数”那本质上还是一个栈。有人尝试用三个计数器分别统计这在([)]上会失效因为计数器丢失了层级顺序信息。所以 O(n) 空间在这里是有必要的不是实现不够聪明。5.2 三个值得顺手练的变体第一个是最长有效括号长度。给定一个可能不合法的字符串求其中最长的合法子串长度。这题用栈可以做但需要往栈里先压一个哨兵下标-1然后靠下标差算长度思路会绕一个弯。我第一次写的时候卡了很久因为习惯了只存字符没想到栈里可以存下标。第二个是括号生成。给定 n 对括号列出所有合法组合。这是回溯的经典题约束条件是“已用左括号数 ≥ 已用右括号数”和本文的判定标准第二条同源。做完这道题再回头看判断合法性你会发现两者其实是一枚硬币的两面。第三个是删除最少的括号使其合法。这题的关键是把“判定”和“修复”分开先扫一遍标记出哪些字符是非法的再一次性删除。用栈记录未匹配的左括号下标同时用一个集合记录需要删除的右括号下标最后拼接。这类“先标记后处理”的模式在文本编辑、格式化工具里非常常见。我在实际项目里遇到过类似的需求解析一段配置文件时需要检查花括号是否配对并给出精确的错误行号。当时用的就是本文这个栈的骨架只是把位置信息一起压栈了。所以别觉得这是道纯粹的练习题它的骨架在真实代码里出现的频率比你想的高。最后分享一个我自己的习惯每写完一个判定类函数我都会在脑子里准备三个用例——一个最小合法、一个最小非法、一个“看起来合法其实非法”。第三个最难想但往往能抓到真正的 bug。这道题里它就是([)]。 
长河君 · 2026/11/3 21:24:03 · 阅读 1.2k 栈与括号匹配：从合法判定到工程边界条件拆解
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 stackC 版本需要自己维护一个数组当栈重点在于指针含义要明确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按约定空串是否单独处理(false遍历结束栈非空)false栈空时遇右括号()true最基本配对([{}])true多层嵌套([)]false交叉嵌套()[]{}true并列平铺a(b)ctrue夹杂其他字符(((((((false深嵌套且未闭合其中最容易漏的是空串和单字符。空串在很多实现里会被“遍历结束检查栈为空”这条自动判成 true看似不用特判但如果题目约定不同这里就是隐性 bug。单字符则是最小可复现的失败用例调试时先跑它能快速定位是判空写错还是收尾写错。注意如果你的判题环境输入可能包含全角括号、【】一定要单独确认。这类字符在 UTF-8 里是多字节的C 语言的按字节遍历会读到半个字符判断逻辑直接失效。3. 完整实现与逐步推演逻辑和代码都有了这一段我想做两件事一是把提前剪枝这类小幅优化讲清楚二是拿几个用例在纸面上走一遍让你看到栈是怎么一步步变化的。很多人写完代码直接提交靠判题结果反推对错这种习惯在简单题上还行题目一复杂就会卡死。能手工推演才是真的掌握了。3.1 主流程与提前剪枝主流程就是前面那四步加收尾没什么可说的值得展开的是提前退出。这个思路在工程里叫 fail-fast一旦发现不可能合法立刻返回不要浪费后面的计算。最有效的剪枝是长度检查。如果只保留括号字符剩下的长度一定是偶数——每个左括号都要有一个右括号配对。所以可以在扫描前先扫一遍过滤或者更省事一点直接判断原串长度的奇偶性如果原串长度是奇数那么过滤后必然也是奇数直接返回 false。注意这个剪枝只在“字符串里全是括号”的版本里成立如果允许夹杂其他字符原串长度奇偶就失去意义了得先过滤再判。第二个提前退出点在循环内部就是遇到右括号且栈空时直接返回。这个前面提过但它作为剪枝的价值值得单独强调对于) a * 1000000这种输入好的实现是 1 次比较就返回差的实现会照样遍历到底。输入规模一大差距就出来了。3.2 典型用例的手工推演拿{[()]}走一遍我把它记成表格步骤字符动作栈内容底→顶1{左括号入栈{2[左括号入栈{ [3(左括号入栈{ [ (4)查表期望(栈顶(弹出{ [5]查表期望[栈顶[弹出{6}查表期望{栈顶{弹出空结束—栈为空true再拿([)]走一遍重点看第 4 步步骤字符动作栈内容1(入栈(2[入栈( [3)期望(栈顶是[不匹配返回 false注意第 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]在top0时读到的是数组外或旧值。Python 和 JS 的“不报错”特性让这个 bug 极难发现因为它会静默地拿undefined去比对结果恰好是 false在多数用例上表现正确只在个别地方翻车。排查方法很简单拿)单独测一次。如果程序抛异常、或者返回了意料之外的值就是顺序问题。修法只有一条判空永远在取栈顶之前取栈顶永远在弹栈之前。4.2 遍历结束忘记检查栈第二种高频错误是循环结束后直接return true。这样(((会被判合法。更隐蔽的情况是输入末尾有未闭合的左括号前面所有配对都对最后一个没关——只看循环内部逻辑完全正确就是收尾漏了一行。这个 bug 的排查成本很低但要养成习惯写完循环就问自己一句“循环正常结束后还有什么状态没检查”。在这里答案是“栈里可能还有残留”。类似的思路可以迁移到很多题上比如深度优先搜索结束后要检查是否所有节点都访问过。4.3 常见问题速查表我把实际遇到过的现象和原因整理成下面这张表调试时可以直接对照现象大概率原因修法空栈时程序崩溃先 pop 后判空调整判定顺序(((判为合法漏了收尾检查返回not stack([)]判为合法只比对数量没比对栈顶加栈顶类型比对映射表查不到就报错用了dict[key]而非.get()改为.get()或先判成员夹杂字母时判错把非括号字符也当成右括号处理加显式elif限定范围全角括号判错字节级遍历撕裂多字节字符按字符遍历或先做规范化长度超长时超时每次循环都做字符串拼接或查找预处理字符集避免 O(n²)最后一行值得展开说一下。有人为了“过滤掉非括号字符”在循环里写s s.replace(ch, )之类的操作这会让整体复杂度从 O(n) 退化成 O(n²)。正确做法是一次遍历完成过滤或者干脆不预处理在扫描时直接跳过。这类“看起来更简洁、实际更慢”的写法在很多题里都有判别方法就是看循环内部有没有对整串做操作。提示调试这类题时把栈内容打印出来比单步跟踪高效得多。每次入栈出栈打一行出错的那一步会非常显眼。5. 复杂度分析与进阶延伸题目做对了还可以再往下走一步看看这个解法的边界在哪以及它能延伸出哪些更有意思的问题。这一步不做也不影响正确性但做了之后你对这类问题的理解会从“会写”变成“会用”。5.1 时间与空间的上界在哪时间复杂度是 O(n)因为每个字符最多被处理一次入栈出栈各一次都是常数操作。这里没有嵌套循环也没有回溯是最优的一档。空间复杂度是 O(n)最坏情况出现在(((((((这种全左括号的输入上栈会撑到和字符串一样长。平均来看要小很多因为配对会及时弹出。如果要抠空间单一括号版本可以用计数器做到 O(1)但多种括号版本做不到——你没法用一个数字表示“三种括号各自的未闭合层数”那本质上还是一个栈。有人尝试用三个计数器分别统计这在([)]上会失效因为计数器丢失了层级顺序信息。所以 O(n) 空间在这里是有必要的不是实现不够聪明。5.2 三个值得顺手练的变体第一个是最长有效括号长度。给定一个可能不合法的字符串求其中最长的合法子串长度。这题用栈可以做但需要往栈里先压一个哨兵下标-1然后靠下标差算长度思路会绕一个弯。我第一次写的时候卡了很久因为习惯了只存字符没想到栈里可以存下标。第二个是括号生成。给定 n 对括号列出所有合法组合。这是回溯的经典题约束条件是“已用左括号数 ≥ 已用右括号数”和本文的判定标准第二条同源。做完这道题再回头看判断合法性你会发现两者其实是一枚硬币的两面。第三个是删除最少的括号使其合法。这题的关键是把“判定”和“修复”分开先扫一遍标记出哪些字符是非法的再一次性删除。用栈记录未匹配的左括号下标同时用一个集合记录需要删除的右括号下标最后拼接。这类“先标记后处理”的模式在文本编辑、格式化工具里非常常见。我在实际项目里遇到过类似的需求解析一段配置文件时需要检查花括号是否配对并给出精确的错误行号。当时用的就是本文这个栈的骨架只是把位置信息一起压栈了。所以别觉得这是道纯粹的练习题它的骨架在真实代码里出现的频率比你想的高。最后分享一个我自己的习惯每写完一个判定类函数我都会在脑子里准备三个用例——一个最小合法、一个最小非法、一个“看起来合法其实非法”。第三个最难想但往往能抓到真正的 bug。这道题里它就是([)]。