数据结构与算法 / 系统课时
用栈处理成对匹配与回退
用栈处理成对匹配与回退
很多题的表面故事不同:括号要找配对,路径里的 .. 要撤销上一层,表达式里遇到结束符要回到最近的未完成状态。共同点是“最后进入、最先处理”。本节把这些问题统一成栈顶状态变化,并用可运行示例验证这一套路。
学习目标
- 判断一个问题何时适合用栈处理“最近未完成项”
- 写出入栈、匹配、回退与非法边界的判断顺序
- 分析栈解法的时间、空间复杂度,并迁移到路径和表达式题
把题意改写成栈顶操作
看到“成对匹配”时,不要先背括号模板,而是先问:当前元素只需要和最近一个尚未处理的元素发生关系吗?如果答案是肯定的,栈通常就是最直接的数据结构。
括号匹配中,左括号代表“尚未完成的任务”,因此入栈;右括号到来时,只允许和栈顶的左括号匹配。若栈为空,说明没有可配对对象;若类型不一致,说明顺序已经非法。扫描结束后栈仍非空,则表示还有未闭合项。
路径简化中的 .. 也是相同机制:普通目录名入栈,.. 删除栈顶目录,相当于撤销最近一次有效进入。表达式求值里的局部回退,则常把运算符、左括号或中间状态压栈,在遇到右括号或低优先级运算符时结算最近的一段。

用括号匹配验证判断顺序
下面的程序完整处理 ()[]{} 三类括号。关键不是 append 或 pop 本身,而是判断顺序:遇到右括号时先检查栈是否为空,再检查栈顶类型,最后才出栈。
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()预期输出
([]{}): True
([)]: False
((): False上例中第二个输入在读到 ) 时,栈顶是 [,因此立即失败;第三个输入直到扫描结束都没有发生类型冲突,但栈中还剩 (,所以仍然非法。这个“处理中失败 + 结束时清场”的双重检查,是成对匹配题最常见的边界。
回退题只是在改变出栈条件
路径简化时,栈里保存的不是左括号,而是已经确认的目录名。普通目录入栈;. 不改变状态;.. 在栈非空时弹出顶部目录。根目录已经没有上一层时继续遇到 ..,通常直接忽略,而不是报错。
表达式题则更灵活:栈中可能保存数字、运算符或括号。此时仍应先定义“什么状态算未完成”,再定义“什么 token 会触发结算”。一旦这两个问题明确,代码往往就是压栈、查看栈顶和出栈三类操作的组合。
复杂度与易错边界
对长度为 的输入,只要每个元素最多入栈一次、出栈一次,总时间复杂度就是 ,额外空间最坏为 。不要因为代码里出现 while 就直接判断为 ;关键要看同一个元素是否会被反复压入和弹出。
常见错误有三个:把“栈空”检查放在访问栈顶之后;匹配成功后忘记出栈;扫描结束后直接返回成功而没有确认栈已清空。路径题还要额外确认根目录上的 .. 如何处理,表达式题则要明确运算优先级和结算边界。
把题目压缩成一句话时,如果你能说出“栈里保存什么未完成状态,以及什么条件触发它被弹出”,通常已经完成了这类题最关键的建模。