Python使用栈实现括号匹配算法

在编写代码或解析表达式时，括号匹配是最基础也是最严格的语法检查之一。无论是圆括号 ()、方括号 [] 还是花括号 {}，只要遗漏、颠倒或发生交错，就会直接导致语法解析失败。解决括号匹配问题的核心路径是利用数据结构中的“栈”（Stack）：借助其后进先出（LIFO）的特性，每当遇到闭合括号时，恰好能将其与最近一次未闭合的开放括号进行校验。本文将完整介绍这一算法的设计思路、流程推导、Python 具体实现及常见边界问题的排查方法。

一、核心原理：为何后进先出（LIFO）契合括号嵌套

设想这样一个场景：在处理嵌套表达式如 {[()]} 时，最外层的花括号 { 最早出现，但它必须等待内部所有的嵌套括号闭合之后才能闭合；而最内层的圆括号 ( 最晚出现，却必须最先与 ) 配对。这种“后出现的先处理，先出现的后处理”的顺序，正是栈结构的典型特征。

在算法运行过程中，我们从左至右逐个读取字符：

• 遇到左括号（(、[、{）：代表一段新嵌套的开始，将其压入（Push）栈顶；
• 遇到右括号（)、]、}）：代表当前最内层嵌套应当闭合。此时检查栈顶元素是否与其对应：若对应则将栈顶弹出（Pop），表示配对成功；若栈已空或类型不匹配，则说明括号非法。

二、算法执行流程推导

在设计代码前，必须明确从开始读取到输出布尔值（True 或 False）的完整判断分支。整个处理流程包含三个关键校验点：

1. 空栈校验：读取到右括号时，如果栈为空，说明该右括号前面没有与之匹配的左括号，判定非法；
2. 类型校验：弹出栈顶元素后，通过映射关系比对两者类型。如果不相等，判定非法；
3. 残留校验：整个字符串遍历完成后，必须检查栈是否已彻底清空。如果栈非空，说明存在未闭合的左括号，判定非法。

三、Python 代码实现与解析

在 Python 中，原生列表（list）本身就具备高效的栈特性。调用 append() 向末尾添加元素对应“入栈”，调用 pop() 移除末尾元素对应“出栈”，这两种操作在平均情况下的时间复杂度都是 O(1)。

为使代码结构清晰并易于维护，我们使用一个字典维护右括号与对应左括号的关系：以右括号为键（Key），对应的左括号为值（Value）。

def is_valid_brackets(s: str) -> bool:
    """
    使用栈检查字符串中的括号匹配是否有效。
    
    参数:
        s: 待检查的输入字符串
    返回:
        布尔值: 括号完全有效闭合返回 True，否则返回 False
    """
    # 建立右括号到左括号的对应映射
    bracket_map = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    
    stack = []
    
    for char in s:
        # 如果是右括号
        if char in bracket_map:
            # 取出栈顶元素；若栈为空，赋予占位符 '#'
            top_element = stack.pop() if stack else '#'
            
            # 校验弹出的栈顶是否与当前右括号所需左括号一致
            if bracket_map[char] != top_element:
                return False
        # 如果是左括号，压入栈中
        elif char in bracket_map.values():
            stack.append(char)
        # 非括号字符忽略（若仅处理纯括号字符串，此分支可省略）
        
    # 遍历结束后，栈为空说明所有左括号均已配对完成
    return len(stack) == 0


# ================= 验证示例 =================
if __name__ == '__main__':
    test_cases = [
        ("()", True),
        ("()[]{}", True),
        ("(]", False),
        ("([)]", False),
        ("{[]}", True),
        ("(((", False),
        (")))", False),
        ("", True),
        ("def func(): arr = [1, {2: (3)}]", True)
    ]
    
    for expr, expected in test_cases:
        result = is_valid_brackets(expr)
        print(f"表达式: {expr:<35} 结果: {str(result):<6} 预期: {expected}")

四、三类典型失败场景排查

在实际运行和单元测试中，所有括号不匹配的情况都可以归纳为以下三种核心形态。理解这三种形态有助于针对性地定位语法解析器报错：

五、算法性能与工程应用总结

使用栈解决括号匹配在时间和空间效率上都具有优秀的表现：

• 时间复杂度为 O(N)：仅需对长度为 N 的输入字符串进行一次线性遍历。每次入栈与出栈操作的复杂度均为 O(1)，整体耗时随字符串长度线性增长。
• 空间复杂度为 O(N)：在最坏情况下（例如输入全部为左括号 "((((((("），栈内需要容纳全部字符，空间占用与字符串长度成正比。

括号匹配算法虽然逻辑精简，但它是栈这种数据结构在语法分析中最为经典的实际应用。无论在日常代码编写、算法面试，还是在构建模板引擎和词法分析器时，熟练掌握这一模式都是构建可靠解析逻辑的重要基础。