数据结构与算法 / 系统课时

栈与括号匹配

栈与括号匹配

括号匹配不仅要求左右数量相同,还要求嵌套顺序正确。本课用栈保存尚未闭合的左括号,统一识别提前闭合、类型不匹配和遍历结束后仍未闭合三类错误。

学习目标

  • 使用栈完成圆括号、方括号和花括号匹配
  • 正确处理空栈、类型冲突和剩余左括号
  • 分析算法的时间与空间复杂度

匹配规则

扫描文本时,左括号表示一个尚未结束的结构,应压入栈中;右括号只能与最近压入的左括号配对,因此只需要检查栈顶。

栈处理括号匹配的状态变化

算法需要同时处理三种失败:

  • 右括号到达时栈为空,说明出现提前闭合
  • 栈顶左括号与当前右括号不对应,说明嵌套顺序错误
  • 遍历结束后栈非空,说明仍有左括号未关闭

本例忽略普通字符,因此可直接检查简单表达式。若业务要求输入只能包含括号,应改为在遇到其他字符时返回错误。

主示例

使用“右括号到左括号”的映射,可以在遇到右括号时直接得到期望的栈顶字符。

python
def is_balanced(text: str) -> bool:
    # 右括号映射到它期望看到的栈顶左括号
    matching = {
        ")": "(",
        "]": "[",
        "}": "{",
    }
    opening = set(matching.values())
    stack: list[str] = []

    for char in text:
        if char in opening:
            stack.append(char)
        elif char in matching:
            # 空栈或类型不一致都应立即失败
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()

    # 遍历结束后仍有左括号,同样属于不匹配
    return not stack

def main() -> None:
    samples = [
        "([]){}",
        "([)]",
        "function(a[0]) { return a[0]; }",
        "((())",
    ]
    for sample in samples:
        print(sample, "->", is_balanced(sample))

if __name__ == "__main__":
    main()

运行命令:

bash
python parentheses_matching.py

预期输出:

text
([]){} -> True
([)] -> False
function(a[0]) { return a[0]; } -> True
((()) -> False

([)] 中三类括号的数量看似都能配对,但关闭顺序错误。栈记录的是尚未完成结构的嵌套次序,而不是简单数量,因此能够发现这种交叉闭合。

最终的 return not stack 同样不可省略。只有左括号的输入不会在扫描过程中触发冲突,但结束时仍应判为不匹配。

复杂度与边界

每个括号最多入栈一次、出栈一次,时间复杂度为 O(n)。最坏情况下输入全是左括号,栈保存 n 个字符,空间复杂度为 O(n)。

空字符串没有未闭合结构,本实现返回 True。以右括号开头会在空栈检查处立即返回 False,不会发生下溢。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

栈与括号匹配

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通