判断一个字符串里的括号写法是否合法，这行字看着平平无奇，但它是很多人第一次真正跟“栈”打照面的地方。题面不复杂：给定字符串 s，只考虑圆括号、方括号、花括号三种成对符号，左括号必须以正确顺序被同类型右括号闭合，合法返回真，不合法返回假。可就是二十来行代码的题，我见过太多版本在小样例上跑得欢，一扔到交叉嵌套或者只剩半个括号的用例上就翻车。这篇东西想把它彻底拆开：判定规则怎么划边界、为什么栈是天然适配的结构、代码怎么写才不漏判、这道题往外还能延伸出哪些更狠的变体。不管你是刚开始练手，还是写业务代码时需要给表达式、配置串做一次语法预检，里面的思路都能直接拿走用。

1. 这道题到底在考什么：判定规则与边界拆解

1.1 题面三句话，藏着一整套边界用例

题面通常只有三行规则：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合；空字符串视为合法。就这三行，翻译成可执行的判定条件，其实就是两条——每遇到一个右括号，它必须和“最近一个还没闭合的左括号”同类型；扫完整个串之后，不能有任何左括号还挂着。第二条最容易被忽略，我见过不少人写完循环就 return true，结果输入一个孤零零的(也返回真。

把所有边界摊到一张表里，你就能看出题面的边界其实相当密：

这张表建议你直接存成单元测试的数据源。我自己的习惯是把它写成一个列表，用参数化测试跑，新增一个坑就往里加一行，成本极低但回报很大——括号题的错误几乎全是从这几个边界里长出来的。

1.2 为什么这道题被反复拿出来练

很多人以为这题是在考“会不会用栈”，这说法对一半。栈只是最终答案，出题人真正想看的是三件事：你能不能把一个口头规则翻译成严格的状态机；你能不能意识到“最近未闭合”这个语义天然对应后进先出；你能不能在写循环的时候同时照顾到“过程中可能失败”和“结束后可能失败”两种出口。

第一件事最见功底。不少人描述规则时说得头头是道——“右括号要和前面最近的同类型左括号配对”，但真写代码就写成遍历找配对、甚至用字符串替换反复消。这类写法在简单用例上确实能过，但要么时间复杂度退化成平方级，要么在交叉嵌套上直接失效。

第二件事是结构选择的判断力。为什么不用队列？因为队列是先进先出，你先放进去的(会被最先弹出的元素影响，而实际需要匹配的恰恰是最近那个。为什么不用数组从后往前扫？因为括号的合法性由“读入顺序”决定，倒着扫需要额外反转语义，绕远路。这些“为什么不选别的”一旦想清楚，栈的登场就不是背模板，而是推出来的。

第三件事藏在代码结构里。过程中失败（遇到类型不匹配、遇到右括号但栈空）可以直接提前返回；结束后失败（栈里还有残留）必须在循环外再判一次。两处出口漏一处，代码就是错的。这题小，但“两个失败出口”的设计思路在真实工程里的价值远超括号本身——任何逐字符流式的校验器都长这个样子。

1.3 三条常见路线的取舍：栈、替换、计数

我见过三种主流写法，各自的适用边界差别很大，值得摆在一起比：

替换法的问题不光在复杂度。它的实现依赖字符串不可变特性，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()在空数组上返回undefined：

function 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) { Deque<Character> 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::stack<char> 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 一张手工验算表：把{[]}走一遍

纸上推一遍状态变化，比看十遍代码管用。以{[]}为例，栈底在左：

再拿([)]走一遍，卡点就一目了然：

第 3 步就是全部答案。这种表格我在教别人的时候会要求自己动手填一遍，尤其是栈内容那一列必须写出顺序，写下“[(”和“([”看起来差不多，但含义完全相反。

4. 踩坑实录：七个高频翻车点

4.1 空栈取顶：本地测不出来，线上必崩

这是出现频率最高的错误，没有之一。写stack[-1]或者stack.peek()之前不判空，遇到以右括号开头的输入就抛异常或者读脏数据。为什么很多人测不出来？因为他们构造的测试用例都是“先有左括号再有右括号”的正常形状，永远不会触发空栈分支。

规避办法很土但有效：把]、)、}这三个单字符用例作为第一组测试，跑通再测别的。另外，如果你用的是带断言的调试环境，可以在取栈顶之前加一句assert len(stack) > 0，出错时直接定位到行，比看异常栈快得多。

4.2 循环结束就返回 true：忘了收尾检查

第二高频。代码结构是“循环里比对，有问题就 return false”，循环外顺手return true。这在处理()这类完全闭合的输入时是对的，但输入((就错了——循环一次没失败，可栈里还压着两个元素。

正确的收尾是return not stack（Python）、stack.length === 0（JS）、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 res

right < left这个条件就是“不能有未闭合的左括号被跳过”的另一种表达。写这类构造题的时候，我建议先把判断函数写好，然后在构造过程中每加一个字符就调一次判断（虽然慢），跑通之后再换成剪枝条件——这样能保证构造逻辑和判断逻辑严格一致。

5.3 最小添加次数与通配符

问“至少添加多少个括号能让字符串合法”，做法是一次扫描配平：遇到左括号入栈，遇到右括号时若栈非空则出栈配对，否则计数一次；扫完之后栈里剩多少就再加多少次。答案就是两个计数之和。

如果引入通配符*，可以当作左括号、右括号或者空字符，问题立刻升级成记忆化搜索或双指针区间维护，难度上了一个档。这类变体的共同点是：判断规则没变，变的是状态空间。

5.4 真实场景里它长什么样

括号校验在工程里的身影远比想象中多。配置文件里的数组嵌套、模板引擎在渲染前做的语法预检、命令行参数的表达式解析、代码编辑器里点击括号时的高亮匹配，底层都是这一个算法。差异体现在几个工程维度上：编辑器需要“找到一个括号的配对位置”而不只是布尔判断，所以栈里存下标；模板引擎需要报错位置和错误类型，所以函数要返回结构化的错误信息而不只是真假。

还有一个常见变体是只检查某一种括号。比如正则表达式里的圆括号嵌套校验，方括号在这里有特殊含义（字符组），必须区别对待。这种场景直接套三括号版本会误判，得先把语义分层——先把字符组当整体跳过，再校验圆括号层级。

6. 工程视角：这类校验器该怎么写

6.1 输入容错与返回值的重新设计

面试写布尔函数没问题，工程里我更推荐返回结构化结果。布尔值只告诉你“错了”，但调用方往往想知道“错在第几位、期望什么、实际遇到什么”。一个实用的结构是包含三个字段：是否合法、出错位置（1-based，方便对接编辑器光标）、错误描述。

这样设计的好处是排查成本低。用户反馈“配置文件打不开”，日志里直接显示“第 37 位期望]，实际遇到}”，比“格式错误”有用一百倍。代价是函数内部要维护位置变量，代码长几行，完全值得。

另一个容错点是长度上限。校验函数被用在字符串可能极大的场景时，应该先判断长度，超过阈值直接拒绝或者改用流式处理，避免一次性把几 MB 内容读进内存再建栈。以及前面提到的全角字符归一化，建议放在这个层做，校验函数本身保持纯粹。

6.2 一次扫描优于分层校验

有人喜欢分层写：先检查长度是否为偶数，再检查首尾字符，再统计数量，最后才上栈。这些预处理在括号题里没什么收益——奇偶性检查确实能提前挡掉一半非法输入，但代价是多一次 O(n) 遍历；首尾字符检查只覆盖极小一部分情况；数量统计在交叉嵌套场景下完全无效。

真要做优化，方向不是“加检查”，而是“减少不必要的抽象”。比如不要为了通用性把栈封装成类，直接用一个列表加几行内联操作就够了；不要为三种括号写三套重复分支，用映射表统一处理。我在实际项目里见过把括号校验抽成接口、抽象基类、策略工厂三层结构的，最后代码量翻了十倍，性能掉了两倍，收益是零。

6.3 测试用例的构造与随机对拍

固定用例覆盖边界，随机用例覆盖组合。固定的那批就是第 1 节表格里的那些，再加上几个超长嵌套和超长并列。随机部分我推荐对拍：写一个绝对正确但极慢的实现（比如暴力递归或者反复替换法），然后用随机生成的括号串去跑两个实现，比较结果是否一致。

随机生成器也有讲究。纯随机生成(、)、[、]、{、}六个字符，绝大多数串会在一开始的几步就判假，覆盖不到深层逻辑。更好的做法是先生成一棵合法的括号树再随机扰动（随机删除一个字符、随机插入一个字符、交换两个相邻字符），这样生成的用例既接近合法、又能精准打到边界，出 bug 的概率高得多。

我自己的用例集大概保持了三十条左右，每次改逻辑全跑一遍，几十毫秒的事，但挡掉的回归问题至少五六次。

写这类题久了我有个体会：真正的分水岭不在能不能把栈用对，而在能不能把“栈为什么必须在这里”讲清楚。我早期写括号题，靠的是记住“左括号入栈、右括号比对、最后判空”这三步，遇到变体就抓瞎；后来逼着自己用反证法推——假设不用栈，你需要随时知道最近一个未闭合的是谁，那就必须维护一个只从一端增删的序列，这个约束直接推出栈，没有第二条路。想通这一层之后，最长有效括号、括号生成、嵌套层级统计这些变体我都是自己推出来的，没再背过模板。还有一个实操上的小建议：随时准备一张纸，遇到卡壳的输入就手动画栈的进出过程，画三遍比盯着屏幕 debug 半小时管用，尤其是那种“逻辑看起来没问题但结果就是不对”的情况，九成是某个边界分支的判断顺序错了，而顺序错误在纸上画一遍立刻现形。