括号匹配栈

栈、单调栈与单调队列 · HTML

数学 / 逻辑形态

扫描 token；开放符入栈。关闭符要求栈非空且 top=matching_open(close)，然后弹出。结束时栈空当且仅当全部定界符平衡。

识别信号

• 输入包含括号、标签、begin/end 等成对符号。
• 嵌套必须正确，交叉配对不允许。
• 要找未匹配位置或最大嵌套深度。
• 最近开放符决定当前关闭符是否合法。

容易误判的相似信号

核心不变量

扫描前缀后，栈按出现顺序保存且仅保存尚未匹配的开放符；栈顶是唯一允许被下一个关闭符匹配的开放符。

状态、转移与处理顺序

Python 骨架

def delimiters_balanced(text):
    match = {')': '(', ']': '[', '}': '{'}
    opening = set(match.values())
    stack = []
    for ch in text:
        if ch in opening:
            stack.append(ch)
        elif ch in match:
            if not stack or stack[-1] != match[ch]:
                return False
            stack.pop()
    return not stack

正确性思路

1. 每个开放符入栈且只在与正确关闭符配对时弹出，所以生成的配对类型正确。
2. LIFO 强制内层先闭合，排除交叉配对。
3. 遇到不匹配即无任何其他更早开放符可合法跨过栈顶；结束空栈恰表示无剩余开放符。

复杂度

边界条件

• 空串通常合法。
• 首字符为关闭符应立即失败。
• 结束时剩余开放符意味着不完整。
• 普通非定界字符是忽略、拒绝还是 token 内容须按协议决定。

错误模式

选择与排除规则

• 多类型或需位置：栈。
• 单类型且只验证、无需位置：计数器可能足够。
• 最长合法段通常在栈中保存索引而不是字符。

相关模板

原创微型例子

Recall prompts

• 为什么多种括号不能只用 balance 计数？
• 结束栈非空说明什么？
• 求最长合法段为何存索引？

我的补充