使用Stack处理括号匹配表达式时求栈内元素的最大数量
2026-10-7
括号匹配栈最大深度问题解答
栈处理括号匹配的核心规则
- 遍历表达式的每一个字符：
- 遇到左括号（
(/[/{）时，将该左括号压入栈中，栈长度+1 - 遇到右括号（
)/]/}）时，弹出栈顶对应的匹配左括号，栈长度-1
- 遇到左括号（
- 任意时刻的栈长度就是当前嵌套的括号层数，统计遍历过程中栈长度的最大值即可得到答案。
逐字符遍历计算过程
待处理表达式：( [ ( { [ ] [ ] } ( ( ( ) ) ) ) { } ] )
按顺序逐个处理字符，记录每一步栈的长度：
| 序号 | 当前字符 | 操作 | 栈长度 |
|---|---|---|---|
| 1 | ( | 压栈 | 1 |
| 2 | [ | 压栈 | 2 |
| 3 | ( | 压栈 | 3 |
| 4 | { | 压栈 | 4 |
| 5 | [ | 压栈 | 5 |
| 6 | ] | 弹栈 | 4 |
| 7 | [ | 压栈 | 5 |
| 8 | ] | 弹栈 | 4 |
| 9 | } | 弹栈 | 3 |
| 10 | ( | 压栈 | 4 |
| 11 | ( | 压栈 | 5 |
| 12 | ( | 压栈 | 6 |
| 13 | ) | 弹栈 | 5 |
| 14 | ) | 弹栈 | 4 |
| 15 | ) | 弹栈 | 3 |
| 16 | ) | 弹栈 | 2 |
| 17 | { | 压栈 | 3 |
| 18 | } | 弹栈 | 2 |
| 19 | ] | 弹栈 | 1 |
| 20 | ) | 弹栈 | 0 |
结果说明
遍历过程中栈的最大长度为6，为正确答案。你之前计算得到9，大概率是只统计了所有左括号的总数，没有扣除遇到右括号时弹出的左括号数量，忽略了栈在匹配右括号时会缩短的规则。
内容的提问来源于stack exchange，提问作者Avv
相关产品推荐
相关产品推荐
