判断一个字符串里的括号写法是否合法这行字看着平平无奇但它是很多人第一次真正跟“栈”打照面的地方。题面不复杂给定字符串 s只考虑圆括号、方括号、花括号三种成对符号左括号必须以正确顺序被同类型右括号闭合合法返回真不合法返回假。可就是二十来行代码的题我见过太多版本在小样例上跑得欢一扔到交叉嵌套或者只剩半个括号的用例上就翻车。这篇东西想把它彻底拆开判定规则怎么划边界、为什么栈是天然适配的结构、代码怎么写才不漏判、这道题往外还能延伸出哪些更狠的变体。不管你是刚开始练手还是写业务代码时需要给表达式、配置串做一次语法预检里面的思路都能直接拿走用。1. 这道题到底在考什么判定规则与边界拆解1.1 题面三句话藏着一整套边界用例题面通常只有三行规则左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合空字符串视为合法。就这三行翻译成可执行的判定条件其实就是两条——每遇到一个右括号它必须和“最近一个还没闭合的左括号”同类型扫完整个串之后不能有任何左括号还挂着。第二条最容易被忽略我见过不少人写完循环就 return true结果输入一个孤零零的(也返回真。把所有边界摊到一张表里你就能看出题面的边界其实相当密输入期望结果判定理由()true最基础的一对()[]{}true三对并列互不干扰(]false类型不匹配([)]false交叉嵌套顺序被打断{[]}true标准嵌套空字符串true没有任何未闭合的左括号(false扫描结束栈里还剩一个]false一上来就是右括号栈是空的(((false三个都挂着([{}])true三层嵌套)(false第一个字符就失败这张表建议你直接存成单元测试的数据源。我自己的习惯是把它写成一个列表用参数化测试跑新增一个坑就往里加一行成本极低但回报很大——括号题的错误几乎全是从这几个边界里长出来的。1.2 为什么这道题被反复拿出来练很多人以为这题是在考“会不会用栈”这说法对一半。栈只是最终答案出题人真正想看的是三件事你能不能把一个口头规则翻译成严格的状态机你能不能意识到“最近未闭合”这个语义天然对应后进先出你能不能在写循环的时候同时照顾到“过程中可能失败”和“结束后可能失败”两种出口。第一件事最见功底。不少人描述规则时说得头头是道——“右括号要和前面最近的同类型左括号配对”但真写代码就写成遍历找配对、甚至用字符串替换反复消。这类写法在简单用例上确实能过但要么时间复杂度退化成平方级要么在交叉嵌套上直接失效。第二件事是结构选择的判断力。为什么不用队列因为队列是先进先出你先放进去的(会被最先弹出的元素影响而实际需要匹配的恰恰是最近那个。为什么不用数组从后往前扫因为括号的合法性由“读入顺序”决定倒着扫需要额外反转语义绕远路。这些“为什么不选别的”一旦想清楚栈的登场就不是背模板而是推出来的。第三件事藏在代码结构里。过程中失败遇到类型不匹配、遇到右括号但栈空可以直接提前返回结束后失败栈里还有残留必须在循环外再判一次。两处出口漏一处代码就是错的。这题小但“两个失败出口”的设计思路在真实工程里的价值远超括号本身——任何逐字符流式的校验器都长这个样子。1.3 三条常见路线的取舍栈、替换、计数我见过三种主流写法各自的适用边界差别很大值得摆在一起比方案核心做法时间复杂度能否处理交叉嵌套推荐度栈匹配左括号入栈右括号比对栈顶O(n)能首选反复替换不断删掉()、[]、{}直到无法删除每轮 O(n)最多 n/2 轮最坏 O(n²)能只适合教学演示计数法只统计数量是否相等O(n)不能只适合单一类型括号替换法的问题不光在复杂度。它的实现依赖字符串不可变特性Python、Java 里每轮替换都产生新串内存开销跟着涨而且“直到不能再删”这个循环条件的写法很微妙稍不留神就写成死循环。计数法是新手最容易误用的。它只看最终左括号数量和右括号数量是否相等遇到)(这种“数量相等但顺序颠倒”的输入会直接放过遇到([)]同样放过。它唯一站得住的场景是只有一种括号类型、且你只关心净数量比如统计一段文本里缩进层级是否平衡。三种括号同时出现时计数法就必须升级成三个计数器分别维护而三个计数器又解决不了交叉嵌套最终还是要回到栈。与其绕这一圈不如一开始就上栈。2. 核心原理栈为什么天然适配括号匹配2.1 用“叠盘子”理解后进先出我给人讲栈的时候最爱用的比喻是食堂叠盘子你往上放只能从最上面拿。括号匹配的语义跟这个动作严丝合缝——扫描字符串时每遇到一个左括号就相当于“放一个盘子”每遇到一个右括号就相当于“取最上面那个盘子看看是不是我要的型号”。取走的必须是刚刚放上去那个再往下的盘子你根本没资格动。这个“没资格动”正是交叉嵌套能被识破的原因。以([)]为例读到(放盘读到[再放一个此时栈顶是[读到)它要求栈顶必须是(可栈顶明明是[直接判假。如果换成“随便找个左括号配对”的思路(是存在的就会误判为真。栈的强约束恰好把“顺序”这一维度编码进去了。还有一个容易被忽略的性质栈里存的东西在同一时刻必须是“同一类待办”。合法的括号串在任意扫描位置栈里的内容必然是一个纯左括号序列且越靠栈底越早出现。你甚至可以用这个性质做断言调试——如果调试时发现栈里混进了右括号那一定是入栈条件写错了。2.2 映射方向用右括号查左括号别反过来写映射表只有两种方向用左括号查右括号或者用右括号查左括号。我强烈建议选后者原因很实际。扫描过程中遇到左括号的处理是无条件入栈不需要查任何表遇到右括号才需要“知道它期望什么”。所以映射表应该以右括号为键、左括号为值。这样做还有个附带好处判断一个字符是不是右括号直接ch in pairs一行搞定判断是不是左括号用ch in ([{或者检查它是否落在值集合里。两个分支互斥逻辑干净。反过来写也能跑但代码会变成“入栈前查一次表、出栈后再查一次表”多做一次查表不说还容易把比较方向写拧——我见过最典型的错误是比较pairs[stack[-1]] ch此时pairs的键是左括号、值是右括号看起来对称但一旦你在某个分支里手滑写成pairs[ch]就会在遇到左括号时抛键不存在异常。选一个方向从头到尾不改能省掉一半调试时间。另外提一句用 ASCII 差值判断的取巧写法(是 40、)是 41[是 91、]是 93{是 123、}是 125确实存在 1 或 2 的差值。有人就用abs(ord(a) - ord(b)) 2来判断配对。这写法能过题但在真实代码里是定时炸弹——任何字符集变动、任何扩展到别的配对符号比如尖括号、中文书名号的需求都会让它立刻失效而且失效方式是静默误判而不是报错。别用。2.3 复杂度推算为什么是 O(n) 时间和 O(n) 空间时间上很好算每个字符恰好被访问一次每次访问做常数次操作判类型、比较、入栈或出栈所以是 O(n)。这里有个细节值得说清楚——出栈操作pop在数组实现下是 O(1)因为只是移动一个指针在链表实现下也是 O(1)。所以整体不会出现隐藏的平方级。空间上最坏情况是整个字符串全是左括号比如((((((此时栈的深度等于 n空间 O(n)。最好情况是空串或者全是右括号虽然会立刻判假栈深度接近 0。平均空间取决于嵌套深度很多工程实现会关心这个值——比如你在做超长文本的括号校验深度上限决定了内存占用上限如果已知嵌套深度不会超过几十层完全可以用固定大小的环形缓冲替代动态扩容的栈省掉扩容开销。顺带说一下递归写法。用递归也能实现遇到左括号就递归处理内部返回时检查是否吃到对应的右括号。思路很优雅但有两个现实问题一是递归深度等于嵌套深度遇到深度上千的输入会栈溢出二是递归写法在处理“扫描到字符串末尾但还有未闭合”这种情况时返回值的约定容易搞混。真要写递归务必用“返回下一个待处理下标”的约定而不是靠全局游标否则调试起来很痛苦。3. 代码落地四种语言对照与逐行拆解3.1 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 or stack[-1] ! pairs[ch]: return False stack.pop() else: continue # 非括号字符按题意忽略 return not stack逐行说几个点。pairs用右括号做键前面讲过理由。if ch in ([{是在字符串里做子串查找字符级别下等价于集合判断可读性比写三个 or 强。elif ch in pairs依赖字典的键查找O(1)。最关键是if not stack or stack[-1] ! pairs[ch]这一行先判空再用短路求值避免越界。Python 里负索引stack[-1]在栈空时会抛 IndexError所以not stack必须放在前面靠 or 的短路特性挡住后半句。这个顺序如果写反输入]就会直接崩而不是返回 False——很多人在本地用()这种正常样例测压根发现不了。else: continue分支是我刻意加的。题面通常限定字符串只含括号但工程代码里输入往往混杂其他字符。明确写一个“忽略”分支比隐含地依赖“既不满足上面两个条件就什么都不做”要清晰得多因为读者一眼能看出这是有意为之还是漏了情况。如果你的业务要求“出现非括号字符就报错”把这个分支改成return False或者抛异常即可改一处就够。最后return not stack也是我特别想强调的写法。它同时覆盖了“栈空返回 True”和“栈非空返回 False”比return len(stack) 0简洁也比if stack: return False; return True少两行。3.2 JavaScript、Java、C 的差异点全在“空栈”上JavaScript 版本可以写得很短因为pop()在空数组上返回undefinedfunction isValid(s) { const pairs { ): (, ]: [, }: { }; const stack []; for (const ch of s) { if (ch ( || ch [ || ch {) { stack.push(ch); } else if (ch in pairs) { if (stack.pop() ! pairs[ch]) return false; } } return stack.length 0; }这里stack.pop()直接塞进比较表达式空数组时得到undefined而undefined ! (恒为真于是自然返回 false。这个技巧简洁但有点“隐形”团队协作时如果你的同事不熟悉 JS 的这个行为读代码会愣一下。追求可读性的话还是老老实实写if (!stack.length || stack.pop() ! pairs[ch]) return false;把空栈判断显式摆出来。注意ch in pairs在 JS 里会命中原型链上的属性名比如ch是toString就会误命中稳妥写法是Object.prototype.hasOwnProperty.call(pairs, ch)或者干脆用Map。括号题里字符集固定不会踩到但换成用户输入驱动的场景就要小心了。Java 版本要注意两点。第一Stack类现在是遗留类推荐用Deque配合ArrayDeque性能和线程语义都更合适。第二Deque.pop()在空栈时抛NoSuchElementException所以必须靠短路求值保护public boolean isValid(String s) { DequeCharacter stack new ArrayDeque(); for (char ch : s.toCharArray()) { switch (ch) { case (: case [: case {: stack.push(ch); break; case ): if (stack.isEmpty() || stack.pop() ! () return false; break; case ]: if (stack.isEmpty() || stack.pop() ! [) return false; break; case }: if (stack.isEmpty() || stack.pop() ! {) return false; break; default: break; } } return stack.isEmpty(); }stack.isEmpty() || stack.pop() ! (里isEmpty()为真时后半句不执行这就是 Java 里最常用的空栈保护写法。注意stack.pop() ! (是 char 与 char 比较不会踩到Character装箱的坑如果你写成stack.pop() ! Character.valueOf(()那比较的就变成对象引用了必错。C 版本和 Java 结构相近留意std::stack的top()在空栈时是未定义行为不会抛异常所以判断顺序更加不能错bool isValid(const std::string s) { std::stackchar st; for (char ch : s) { if (ch ( || ch [ || ch {) { st.push(ch); continue; } char need; switch (ch) { case ): need (; break; case ]: need [; break; case }: need {; break; default: continue; } if (st.empty() || st.top() ! need) return false; st.pop(); } return st.empty(); }C 这里多了一步“先算出 need 再比较”好处是st.pop()只在确认匹配之后调用不会出现“比对失败但元素已经被弹走”的副作用。这个顺序在 Python 版里是自然的但在 C 和 Java 里如果你图省事写成st.top() ! need之后立刻pop再包在某个条件里就容易写出“失败路径也弹了栈”的 bug。3.3 一张手工验算表把{[]}走一遍纸上推一遍状态变化比看十遍代码管用。以{[]}为例栈底在左步骤读入字符动作栈内容底→顶当前结论1{入栈{继续2[入栈{[继续3]栈顶[匹配出栈{继续4}栈顶{匹配出栈空继续5结束栈为空空返回 true再拿([)]走一遍卡点就一目了然步骤读入字符动作栈内容底→顶当前结论1(入栈(继续2[入栈([继续3)栈顶是[期望(—返回 false第 3 步就是全部答案。这种表格我在教别人的时候会要求自己动手填一遍尤其是栈内容那一列必须写出顺序写下“[(”和“([”看起来差不多但含义完全相反。4. 踩坑实录七个高频翻车点4.1 空栈取顶本地测不出来线上必崩这是出现频率最高的错误没有之一。写stack[-1]或者stack.peek()之前不判空遇到以右括号开头的输入就抛异常或者读脏数据。为什么很多人测不出来因为他们构造的测试用例都是“先有左括号再有右括号”的正常形状永远不会触发空栈分支。规避办法很土但有效把]、)、}这三个单字符用例作为第一组测试跑通再测别的。另外如果你用的是带断言的调试环境可以在取栈顶之前加一句assert len(stack) 0出错时直接定位到行比看异常栈快得多。4.2 循环结束就返回 true忘了收尾检查第二高频。代码结构是“循环里比对有问题就 return false”循环外顺手return true。这在处理()这类完全闭合的输入时是对的但输入((就错了——循环一次没失败可栈里还压着两个元素。正确的收尾是return not stackPython、stack.length 0JS、stack.isEmpty()Java、st.empty()C。这四个写法的语义完全一致只有栈被彻底清空才算合法。我自己的记忆口诀是“过程中看比对结束后看余量”。4.3 交叉嵌套识别不出来替换法与计数法的通病交叉嵌套是区分“真懂栈”和“背了模板”的分水岭。用计数法的人遇到([)]会数出两个左括号两个右括号判定合法用替换法的人如果替换逻辑写成“分别检查三种括号是否成对出现”同样会误判。判断你的实现有没有这个毛病一个用例就够([)]必须返回 false。如果它返回 true说明你的方案丢了“顺序”这个维度必须换栈。顺便说另一个刁钻用例是(){}}{——前四个字符构成合法对后面又冒出多余的右括号扫到第五个字符时栈是空的应该立刻失败。这个用例同时覆盖了“中途空栈”和“末尾残留”两个场景。4.4 映射表写反症状是“所有合法输入都返回假”映射方向写反的表现很有辨识度()这种最简单的输入也返回 false。原因通常是键值写反了却还在用同一套查表逻辑比如本该pairs[)] (写成了pairs[(] )然后代码里又拿右括号去查表查不到直接落进某个默认分支。排查这类问题有个笨办法在函数开头打印一次映射表内容肉眼看键值对不对。虽然土但比盯着代码想十分钟快。更根本的预防是固定映射方向全项目统一别在这个函数里用右括号做键在那个函数里用左括号做键。4.5 用错数据结构的三个变种第一个变种是用队列。想法是“先进来的括号先闭合”但这跟括号的嵌套语义正好相反——最内层才最先闭合是最晚进来的先走。用队列实现([)]会被误判为合法{[]}反而可能失败。第二个变种是用列表当栈但两头混用一会儿append、pop()一会儿insert(0, ...)、pop(0)。后者在 Python 里是 O(n) 操作整体复杂度退化成平方级。只要固定用尾部操作这个坑就不会踩。第三个变种是栈里存字符下标而不是字符本身。存下标不是不行某些变体题比如求最长有效括号就必须存下标但存下标之后比较逻辑要相应改成s[stack[-1]] ! pairs[ch]多一层间接访问容易写漏。4.6 非括号字符的处理策略不一致题面说只含括号实际输入经常夹杂空格、逗号、甚至中文标点。如果你的代码默认忽略所有非括号字符那(a)会返回 true这在某些业务场景下是错的——你可能希望它报错因为这意味着输入不纯净。这里没有标准答案只有一致性要求同一个项目里所有校验器对“非法字符”的态度必须统一。我倾向于在解析入口处先做一次字符集过滤或者直接拒绝把校验函数本身写纯——它只接受已确认合法的字符集这样函数内部的else: continue分支就显得多余代码更容易证明正确。4.7 全角与中文括号输入法给你埋的雷这是最常见的实战坑。用户在中文输入法下敲出来的、【】、和半角字符长得几乎一样但码点完全不同程序会当作非括号字符忽略掉于是]这种输入被判定为“只有右括号、栈空、返回 false”或者更糟——“全部忽略、栈空、返回 true”。处理办法是在比较之前做一次归一化把全角括号映射成半角或者把中文字符集里常见的成对符号统一成一套内部表示。我在写任何跟用户输入相关的语法检查时第一步永远是归一化这跟括号题本身没关系但括号题是最容易暴露这个问题的场景。5. 变体与扩展从一个题引出一整条链5.1 最长有效括号从“判断”变成“求解”判断合法只需要返回布尔值问“最长有效子串长度”就得记录位置了。主流做法还是栈但栈里存下标而不是字符并且栈底预先放一个-1作为哨兵def longest_valid(s: str) - int: stack [-1] best 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: stack.append(i) # 当前位置成了新的“未匹配起点” else: best max(best, i - stack[-1]) return best哨兵的作用是让“从下标 0 开始的有效串”也能用统一公式算长度不用单独判断。stack.pop()之后如果栈空了说明当前右括号没人配把这个位置重新压进去当新的分界点。这个思路如果只看代码很难想明白但用()和()()走一遍就通了。5.2 括号生成把判断逻辑反过来用给 n 对括号输出所有合法组合。这是把“合法性判断”转化为“构造时就不违反规则”用的是回溯剪枝条件直接来自判断规则的两条“已用的左括号数量不能超过 n”“右括号数量不能超过已用的左括号数量”。def generate(n): res [] def dfs(cur, left, right): if len(cur) 2 * n: res.append(cur) return if left n: dfs(cur (, left 1, right) if right left: dfs(cur ), left, right 1) dfs(, 0, 0) return resright left这个条件就是“不能有未闭合的左括号被跳过”的另一种表达。写这类构造题的时候我建议先把判断函数写好然后在构造过程中每加一个字符就调一次判断虽然慢跑通之后再换成剪枝条件——这样能保证构造逻辑和判断逻辑严格一致。5.3 最小添加次数与通配符问“至少添加多少个括号能让字符串合法”做法是一次扫描配平遇到左括号入栈遇到右括号时若栈非空则出栈配对否则计数一次扫完之后栈里剩多少就再加多少次。答案就是两个计数之和。如果引入通配符*可以当作左括号、右括号或者空字符问题立刻升级成记忆化搜索或双指针区间维护难度上了一个档。这类变体的共同点是判断规则没变变的是状态空间。5.4 真实场景里它长什么样括号校验在工程里的身影远比想象中多。配置文件里的数组嵌套、模板引擎在渲染前做的语法预检、命令行参数的表达式解析、代码编辑器里点击括号时的高亮匹配底层都是这一个算法。差异体现在几个工程维度上编辑器需要“找到一个括号的配对位置”而不只是布尔判断所以栈里存下标模板引擎需要报错位置和错误类型所以函数要返回结构化的错误信息而不只是真假。还有一个常见变体是只检查某一种括号。比如正则表达式里的圆括号嵌套校验方括号在这里有特殊含义字符组必须区别对待。这种场景直接套三括号版本会误判得先把语义分层——先把字符组当整体跳过再校验圆括号层级。6. 工程视角这类校验器该怎么写6.1 输入容错与返回值的重新设计面试写布尔函数没问题工程里我更推荐返回结构化结果。布尔值只告诉你“错了”但调用方往往想知道“错在第几位、期望什么、实际遇到什么”。一个实用的结构是包含三个字段是否合法、出错位置1-based方便对接编辑器光标、错误描述。这样设计的好处是排查成本低。用户反馈“配置文件打不开”日志里直接显示“第 37 位期望]实际遇到}”比“格式错误”有用一百倍。代价是函数内部要维护位置变量代码长几行完全值得。另一个容错点是长度上限。校验函数被用在字符串可能极大的场景时应该先判断长度超过阈值直接拒绝或者改用流式处理避免一次性把几 MB 内容读进内存再建栈。以及前面提到的全角字符归一化建议放在这个层做校验函数本身保持纯粹。6.2 一次扫描优于分层校验有人喜欢分层写先检查长度是否为偶数再检查首尾字符再统计数量最后才上栈。这些预处理在括号题里没什么收益——奇偶性检查确实能提前挡掉一半非法输入但代价是多一次 O(n) 遍历首尾字符检查只覆盖极小一部分情况数量统计在交叉嵌套场景下完全无效。真要做优化方向不是“加检查”而是“减少不必要的抽象”。比如不要为了通用性把栈封装成类直接用一个列表加几行内联操作就够了不要为三种括号写三套重复分支用映射表统一处理。我在实际项目里见过把括号校验抽成接口、抽象基类、策略工厂三层结构的最后代码量翻了十倍性能掉了两倍收益是零。6.3 测试用例的构造与随机对拍固定用例覆盖边界随机用例覆盖组合。固定的那批就是第 1 节表格里的那些再加上几个超长嵌套和超长并列。随机部分我推荐对拍写一个绝对正确但极慢的实现比如暴力递归或者反复替换法然后用随机生成的括号串去跑两个实现比较结果是否一致。随机生成器也有讲究。纯随机生成(、)、[、]、{、}六个字符绝大多数串会在一开始的几步就判假覆盖不到深层逻辑。更好的做法是先生成一棵合法的括号树再随机扰动随机删除一个字符、随机插入一个字符、交换两个相邻字符这样生成的用例既接近合法、又能精准打到边界出 bug 的概率高得多。我自己的用例集大概保持了三十条左右每次改逻辑全跑一遍几十毫秒的事但挡掉的回归问题至少五六次。写这类题久了我有个体会真正的分水岭不在能不能把栈用对而在能不能把“栈为什么必须在这里”讲清楚。我早期写括号题靠的是记住“左括号入栈、右括号比对、最后判空”这三步遇到变体就抓瞎后来逼着自己用反证法推——假设不用栈你需要随时知道最近一个未闭合的是谁那就必须维护一个只从一端增删的序列这个约束直接推出栈没有第二条路。想通这一层之后最长有效括号、括号生成、嵌套层级统计这些变体我都是自己推出来的没再背过模板。还有一个实操上的小建议随时准备一张纸遇到卡壳的输入就手动画栈的进出过程画三遍比盯着屏幕 debug 半小时管用尤其是那种“逻辑看起来没问题但结果就是不对”的情况九成是某个边界分支的判断顺序错了而顺序错误在纸上画一遍立刻现形。