数据结构与算法 / 系统课时
栈与括号匹配
栈与括号匹配
括号匹配不仅要求左右数量相同,还要求嵌套顺序正确。本课用栈保存尚未闭合的左括号,统一识别提前闭合、类型不匹配和遍历结束后仍未闭合三类错误。
学习目标
- 使用栈完成圆括号、方括号和花括号匹配
- 正确处理空栈、类型冲突和剩余左括号
- 分析算法的时间与空间复杂度
匹配规则
扫描文本时,左括号表示一个尚未结束的结构,应压入栈中;右括号只能与最近压入的左括号配对,因此只需要检查栈顶。

算法需要同时处理三种失败:
- 右括号到达时栈为空,说明出现提前闭合
- 栈顶左括号与当前右括号不对应,说明嵌套顺序错误
- 遍历结束后栈非空,说明仍有左括号未关闭
本例忽略普通字符,因此可直接检查简单表达式。若业务要求输入只能包含括号,应改为在遇到其他字符时返回错误。
主示例
使用“右括号到左括号”的映射,可以在遇到右括号时直接得到期望的栈顶字符。
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,不会发生下溢。
按自己的节奏,确认真正理解。