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

用栈处理成对匹配与回退

用栈处理成对匹配与回退

很多题的表面故事不同:括号要找配对,路径里的 .. 要撤销上一层,表达式里遇到结束符要回到最近的未完成状态。共同点是“最后进入、最先处理”。本节把这些问题统一成栈顶状态变化,并用可运行示例验证这一套路。

学习目标

  • 判断一个问题何时适合用栈处理“最近未完成项”
  • 写出入栈、匹配、回退与非法边界的判断顺序
  • 分析栈解法的时间、空间复杂度,并迁移到路径和表达式题

把题意改写成栈顶操作

看到“成对匹配”时,不要先背括号模板,而是先问:当前元素只需要和最近一个尚未处理的元素发生关系吗?如果答案是肯定的,栈通常就是最直接的数据结构。

括号匹配中,左括号代表“尚未完成的任务”,因此入栈;右括号到来时,只允许和栈顶的左括号匹配。若栈为空,说明没有可配对对象;若类型不一致,说明顺序已经非法。扫描结束后栈仍非空,则表示还有未闭合项。

路径简化中的 .. 也是相同机制:普通目录名入栈,.. 删除栈顶目录,相当于撤销最近一次有效进入。表达式求值里的局部回退,则常把运算符、左括号或中间状态压栈,在遇到右括号或低优先级运算符时结算最近的一段。

栈处理匹配与回退的统一流程

用括号匹配验证判断顺序

下面的程序完整处理 ()[]{} 三类括号。关键不是 append 或 pop 本身,而是判断顺序:遇到右括号时先检查栈是否为空,再检查栈顶类型,最后才出栈。

python
def is_valid_brackets(text: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []

    for ch in text:
        if ch in "([{":
            stack.append(ch)
            continue

        if ch in pairs:
            # 先判断空栈,避免访问不存在的栈顶。
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()

    # 扫描结束后仍有左括号,说明存在未完成匹配。
    return not stack


def main() -> None:
    cases = ["([]{})", "([)]", "(()"]
    for case in cases:
        print(f"{case}: {is_valid_brackets(case)}")


if __name__ == "__main__":
    main()

预期输出

text
([]{}): True
([)]: False
((): False

上例中第二个输入在读到 ) 时,栈顶是 [,因此立即失败;第三个输入直到扫描结束都没有发生类型冲突,但栈中还剩 (,所以仍然非法。这个“处理中失败 + 结束时清场”的双重检查,是成对匹配题最常见的边界。

回退题只是在改变出栈条件

路径简化时,栈里保存的不是左括号,而是已经确认的目录名。普通目录入栈;. 不改变状态;.. 在栈非空时弹出顶部目录。根目录已经没有上一层时继续遇到 ..,通常直接忽略,而不是报错。

表达式题则更灵活:栈中可能保存数字、运算符或括号。此时仍应先定义“什么状态算未完成”,再定义“什么 token 会触发结算”。一旦这两个问题明确,代码往往就是压栈、查看栈顶和出栈三类操作的组合。

复杂度与易错边界

对长度为 nn 的输入,只要每个元素最多入栈一次、出栈一次,总时间复杂度就是 O(n)O(n),额外空间最坏为 O(n)O(n)。不要因为代码里出现 while 就直接判断为 O(n2)O(n^2);关键要看同一个元素是否会被反复压入和弹出。

常见错误有三个:把“栈空”检查放在访问栈顶之后;匹配成功后忘记出栈;扫描结束后直接返回成功而没有确认栈已清空。路径题还要额外确认根目录上的 .. 如何处理,表达式题则要明确运算优先级和结算边界。

把题目压缩成一句话时,如果你能说出“栈里保存什么未完成状态,以及什么条件触发它被弹出”,通常已经完成了这类题最关键的建模。

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

目录与阅读设置

阅读设置

17

记录一个想法

用栈处理成对匹配与回退

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

登录哪都通