如何判断括号字符串是否合法？为什么要用栈？

知识点详解：为什么栈能检查嵌套关系？

数量相同，不代表关闭顺序正确

假设输入是 ([)]。圆括号与方括号的数量都相同，但是方括号还没有关闭，就先出现圆括号的右半部分。

从嵌套关系看，最近打开的是 [，接下来必须先关闭 ]。这就是“后打开，先关闭”。栈的后进先出特征，恰好能维护这个顺序。

如果只有一种括号，并且只检查平衡，可以使用计数器；但存在多种括号时，计数器不能记住类型与嵌套顺序。

栈里只记录尚未关闭的左括号

每读到一个左括号，就把它放到栈顶。每读到一个右括号，就只检查最近那个左括号，而不是在整个栈里寻找任何能匹配的项。

如果栈为空，说明右括号没有对应的打开；如果栈顶类型不同，说明嵌套顺序错误。只有正好匹配，才能弹出。

全部读完仍有元素，说明还有左括号未关闭。规则对应 有效括号题目。

代码先处理输入边界

function validBrackets(text: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  for (const ch of text) {
    if ("([{".includes(ch)) stack.push(ch);
    else if (Object.hasOwn(pairs, ch)) {
      if (stack.pop() !== pairs[ch]) return false;
    } else return false;
  }
  return stack.length === 0;
}

def valid_brackets(text):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            return False
    return not stack

示例明确拒绝非括号字符。TypeScript 使用 Object.hasOwn，需要相应运行环境支持，不使用普通原型属性判断冒充键集合。

图：([)] 在哪一步出错？。

测试为什么不能只给一个正确例子？

应该分别检查空字符串、单独左括号、单独右括号、正确连续匹配、正确嵌套和交叉关闭。

例如 ()[]{} 检查连续片段，([{}]) 检查嵌套，([)] 检查类型顺序，(() 检查结束时是否还有剩余。

假设处理的是代码片段，字符串中的 ”(” 可能只是字符，注释里也可能出现括号。此时需要先做词法处理，不能把这道面试题的输入假设扩成完整语法分析器。

面试官继续追问

能提前判断长度为奇数一定不合法吗？

在只允许括号且每个括号都必须配对的前提下可以。但这个优化不是核心，仍要正确处理顺序和类型。

为什么额外空间不是 O(1)？

如果前半段都是左括号，栈里可能保留与输入长度成比例的元素。最坏空间是 O(n)。

能直接不断 replace 掉 ()、[]、{} 吗？

小输入可能得到结果，但反复扫描和创建新字符串可能增加复杂度，也不如栈明确。面试中应能解释算法的单次遍历保证。

面试速记卡

• 核心关系：最近打开的括号必须最先关闭。
• 左括号：入栈；右括号：只检查栈顶。
• 失败条件：栈空、类型不匹配或最终有剩余。
• 复杂度：O(n) 时间，最坏 O(n) 空间。
• 输入约定：括号串与完整代码文本不是同一问题。