数完左右括号各几个,为什么还是判不出嵌套是否合法

有效括号串不是左右数量相等,而是每个右括号都能闭合最近一个尚未匹配的左括号。这个后进先出的约束让栈成为天然结构:遇到左括号压栈,遇到右括号只与栈顶比对,扫完还必须栈空。最常见的误区是只数余额、用队列代替栈、忘了最后的空栈检查,以及在最长有效括号里只存字符不存下标。本文从"([)]"这个反例讲清不变量,说明单类型时计数器为何够用、多类型为何必须栈,并给出深度限制、错误定位与测试用例的落地建议。

是什么

有效括号串(valid parentheses)指这样一串括号:每个右括号都能与它左边、尚未被匹配的最近一个同类型左括号配成一对,并且扫描过程中不会出现"右括号找不到左括号"的情况。三种括号可以混用,但嵌套关系必须像套娃一样逐层闭合。

一句话直觉:它检查的不是"左右各几个",而是"最后打开的那一个,是否最先被关上"。

典型场景包括编译器与解释器的词法、语法分析,JSON 与配置文件的解析,模板引擎的标签配对,编辑器里的括号高亮与自动补全,以及面试里围绕 LeetCode 20(有效括号)、32(最长有效括号)、921(使括号有效的最少添加)、1249(移除无效括号)的一整族题。它们共享同一条不变量,只是问法从"是否合法"变成"最长合法子串有多长"或"最少改几个字符"。

核心原理

先看一个反例:([)]。左括号两个、右括号两个,余额从头到尾没有变成负数,按"数量相等"判断完全合格;但它并不合法——) 出现时,最近打开的是 [,类型对不上,而 ( 还被压在下面。等 ] 到来,它想闭合的又是已经"错过"的 (。数量对了,顺序错了。

这说明判断合法性需要回答一个具体问题:当前这个右括号,应该和哪个左括号配对?答案永远是"最近一个还没匹配的左括号"。于是我们需要一个容器,支持"放入最新的、取出最新的",也就是后进先出(LIFO)。栈正好只有一端:压栈把新元素放到栈顶,弹栈取走的也是栈顶。

用一个类比:单车道死胡同。车只能从同一个口进出,最后开进去的车挡在最外面,必须最先倒出来;想取里面那辆,得先把外面的一辆辆挪走。括号的嵌套就是这条死胡同,栈顶就是最外面那辆车。相比之下,队列是"两头开"的通道,先进的先出,会强迫最早打开的括号先闭合,恰好与嵌套相反。拿队列跑 ([)]:( 和 [ 依次入队,) 与队首 ( 比对上、出队,] 再与队首 [ 比对上,于是一个非法串被误判为合法。这就是面试里"为什么不能用队列"的标准反例。

算法只有三步,但每一步都有容易漏的边界:

  1. 遇到左括号,压栈,表示"欠一个同类型的右括号"。
  2. 遇到右括号,先看栈是否为空;空则说明它没有可配对的左括号,直接失败。非空则只比对栈顶:类型不符失败,类型相符则弹出,表示这笔"欠账"还清。
  3. 扫描结束后,栈必须为空;否则还有左括号没被闭合,例如 ((。
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:
            return False          # 非括号字符按题目约定判错
    return not stack

正确性来自一条不变量:扫描到任意位置时,栈里存的是"已经出现、尚未匹配的左括号",且从栈底到栈顶就是它们在原串中的出现顺序,所以栈顶必然是最近的那个。每次弹栈都消掉一对在嵌套意义上相邻的括号,消不掉就说明顺序或类型出错。时间复杂度 O(n),每个字符最多进出栈一次;空间复杂度 O(n),但更准确地说,是 O(嵌套深度)——全是左括号时达到最坏情况,而 ()()() 这种平铺结构深度只有 1。

这里有一个值得讲透的压缩:如果只有一种括号,栈里所有元素都长得一样,"是谁"不再重要,重要的只是"还有几层没关"。此时可以用一个整数余额代替整个栈:遇左加一,遇右减一,中途为负或最终不为零就失败。栈保存的是类型信息,计数器只保存深度;单类型时类型信息是冗余的,所以 O(n) 空间可以压到 O(1)。但一旦混入第二种括号,余额就分不清 ( 和 [,([)] 立刻击穿它。这个"什么时候能降维"的判断,比背下模板更能说明你是否真的理解栈在存什么。

同一套不变量还能变形出更多问题。最长有效括号(LeetCode 32)把栈里存的东西从字符换成下标:先压一个哨兵 -1 当"上一个未匹配右括号的位置",遇到左括号压下标,遇到右括号先弹;弹完若栈空,说明当前右括号无法匹配,把它的下标压回去当新基准;否则用 i - stack[-1] 更新答案。哨兵的作用是让第一段合法串也能用同一个减法算长度。最少添加(921)在单类型下用余额即可:中途每出现一次负余额就补一个左括号并把余额归零,最后再加上剩余的正余额。最少删除(1249)要在多类型下指出哪些位置非法,又得回到存下标的栈。题目在变,"最近未匹配"这条主线没变。

常见考点与误区

  • 误区一:左右数量相等就合法。 )( 数量相等却第一个字符就失败;([)] 余额始终非负却因类型错配失败。正确说法是"每个前缀里右括号不超过左括号,且每个右括号闭合最近一个未匹配的同类型左括号",前者只是必要条件。
  • 误区二:用队列或双端队列也能做。 只要按先进先出配对,([)] 就会被判合法,因为队列让最早打开的括号先闭合,方向与嵌套相反。栈不是"顺手选的数据结构",而是由 LIFO 语义决定的。
  • 误区三:忘了判空栈和最后的栈空。 遇到 ] 直接 stack.pop() 会抛异常;只在中途比对、结束时不再检查,会把 (( 判成合法。这两个边界是这道题最高频的出错来源。
  • 误区四:最长有效括号只存左括号字符。 不存下标就无法计算长度;不设哨兵或不在栈空时更新基准,会漏掉从下标 0 开始的答案。栈空时应当把当前右括号下标压入作为新基准,而不是简单清空。
  • 误区五:以为任何场景都得上栈。 单类型判断和单类型最少添加用计数器就够,最长有效括号也有左右各扫一遍的 O(1) 空间做法。反过来,多类型、需要报错位置时必须存下标和类型。
  • 误区六:括号配平等于语法正确。 {"a"} 括号完全配平,却不是合法 JSON;() 配平,也不代表表达式有操作数。括号匹配只是语法分析的一个子步骤,字符串字面量、转义、注释里的括号不能计入,真正写解析器要交给词法分析器先切 token。
  • 考点:正则能不能判嵌套? 经典正则表达式描述的是正则语言,无法表达"任意深度、需要计数"的嵌套;PCRE 的递归与平衡组是扩展语法,已经超出正则模型。面试里答"写个正则"通常直接扣分。
  • 考点:复杂度。 时间 O(n);空间说 O(n) 可以,但更准确是 O(深度)。面试官追问"能不能 O(1) 空间"时,要先确认是不是单类型,别直接答"不能"。

实践建议

  • 先把契约写清楚:空串算合法还是非法、非括号字符是报错还是跳过、是否只接受 ASCII 三种括号。不同约定会让同一段代码在单测和线上表现相反。
  • 用映射表而不是一长串 if-else 判断类型,新增括号种类时只改表;遇到未知字符走显式分支,不要静默忽略,否则用户输入里的全角括号会被当成合法而悄悄放过。
  • 生产解析要返回"第一个错误的位置和原因",而不只是一个布尔值。把字符和下标一起压栈,失败时就能告诉用户"第 17 个字符的 ) 试图闭合第 9 个字符的 [",这比 false 有用得多。
  • 对不可信输入限制嵌套深度。栈深等于嵌套层数,攻击者用几十万个左括号就能让内存和后续递归解析爆掉;在词法层设一个上限并返回明确错误,比在上层超时后补救便宜。
  • 单类型的大流量校验优先用计数器,省掉每个请求的栈分配;多类型或需要定位时再上栈。不要为了"统一风格"把简单场景复杂化。
  • 测试用例固定下来:""、"("、")"、"([)]"、"{[]}"、"((("、"()[]{}",再补一个十万级左括号的深度用例。前六个管正确性,最后一个管最坏复杂度。

一句话总结:栈能判括号,不是因为它叫栈,而是因为它恰好只暴露最近一个未匹配的左括号。

相关阅读

← 返回文章志