第3章｜栈与队列
Unit 12 · 多层上下文栈综合实验
← Unit 11
U12
Decode StringFrame · Context · Merge
进入更深一层之前，
先把外层世界完整保存下来。
嵌套字符串不能只靠一个重复次数和一段局部文本完成。每遇到左括号，都要把“进入内层之前的字符串”和“本层重复次数”压入上下文栈；右括号到达时，再弹出最近一层并完成合并。
LeetCode #394 题目模型解析嵌套编码 · 恢复外层上下文 · 输出完整字符串
题目要求
给定编码字符串 s，返回解码后的字符串。规则 k[encoded_string] 表示方括号中的字符串恰好重复 k 次；输入始终合法，数字只用于表示重复次数。
class Solution:
def decodeString(self, s: str) -> str:
pass
输入、输出与复杂度
- 输入：由小写字母、数字和方括号组成的合法编码字符串；
- 输出：完全展开后的字符串；
- 主方法：单次扫描输入，额外状态与嵌套深度相关；生成字符的工作至少与输出长度相关。
示例
输入：s = "3[a]2[bc]"
输出："aaabcbc"
输出："aaabcbc"
输入：s = "3[a2[c]]"
输出："accaccacc"
输出："accaccacc"
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
输出："abcabccdcdcdef"
数据约束
1 ≤ s.length ≤ 30- 所有重复次数均在
[1, 300]； - 输入保证有效，解码后长度不超过
10⁵。
Context Frame
进入一个新括号层前保存的快照：外层已完成字符串与当前重复次数。
Local String
当前最内层尚未闭合区间已经解码的内容；它只属于当前递归深度。
Digit Accumulation
多位次数必须按 current_number × 10 + digit 累积，不能把“12”理解成 1 与 2 两次重复。
Frame Invariant
栈中从底到顶依次保存每个未闭合外层的前缀与重复次数，栈顶对应最近进入的一层。
Unit 11 → Unit 12｜容器保存的不是“数据”，而是尚未完成的决策状态
Unit 11 · 优先队列
候选留在堆中，是因为它仍有资格进入 Top-K；容量超限时，最弱候选离开。
→
Unit 12 · 上下文栈
外层状态留在栈中，是因为内层尚未闭合；匹配的右括号到达时，最近上下文恢复。
统一提问：容器中的每一项为何还不能结束？什么事件使它离开？离开时能够确定哪一部分结果？
认知任务 1
读到第一个左括号时，进入内层前必须保存什么？
当前已经读到重复次数 3，而 current_string 仍为空。点击动画观察状态，然后决定哪一份上下文必须压栈。
主动画区上下文栈实验
演示输入：3[a2[c]]读取 token 并更新局部状态
当前最内层状态 数字先累积，字母追加到局部字符串
current_number0
current_string
当前嵌套深度
Context Frame Stack 栈顶 = 最近未闭合外层
本步状态变换
current_number = 3
3[a2[c]]
扫描并找最内层
替换 2[c] → cc
再次扫描括号
替换 3[acc]
当前索引0
栈帧数量0
已完成合并0
局部长度0
Read Token
Build Number
Push Frame
Pop & Merge
Return
读取数字 3：current_number 从 0 变为 3，为接下来的括号层准备重复次数。
当前状态契约问题依赖当前动画状态
current token[
current_number3
current_string""
stack top—
depth0
current action准备压栈
核心不变量current_string 表示当前最内层已解码内容；stack 从底到顶保存所有未闭合外层的 previous_string 与 repeat。
为什么保存两个字段？
关闭内层后既要知道重复多少次，也要把结果接回进入内层前已经形成的外层前缀。
为什么栈适合嵌套？
最后进入的括号层最先闭合，恢复顺序天然满足后进先出。
读到第一个“[”时，哪一个栈帧应被保存？
更小一步：进入括号后 current_string 和 current_number 都要被清空，因此先保存它们当前的值。
代码补全：把上下文恢复编译为 PythonLeetCode 可直接提交格式
1class Solution:
2 def decodeString(self, s: str) -> str:
3 stack = []
4 current_number = 0
5 current_string = ""
6
7 for char in s:
8 if char.isdigit():
9 current_number =
10 elif char == "[":
11
12 current_string =
13 current_number =
14 elif char == "]":
15
16 current_string =
17 else:
18 current_string += char
19
20 return current_string
提示 1｜数字 多位重复次数不能覆盖旧值，应使用十进制累积：old × 10 + digit。 提示 2｜左括号 进入新层会清空两个局部变量，因此先把 previous_string 与 repeat 作为同一个栈帧保存。 提示 3｜右括号 先弹出最近栈帧，再按 previous_string + current_string × repeat 恢复父上下文。 查看提示不会解锁迁移；正确补全代码或走完整轨迹后才会解锁。
代码与图像逐行联动点击代码行可跳到该行第一次执行
3stack = []
4current_number = 0
5current_string = ""
7for char in s:
8if char.isdigit():
9current_number = current_number * 10 + int(char)
10elif char == "[":
11stack.append((current_string, current_number))
12current_string = ""
13current_number = 0
14elif char == "]":
15previous_string, repeat = stack.pop()
16current_string = previous_string + current_string * repeat
17else:
18current_string += char
20return current_string
初始化空栈。轨迹将完整解析 3[a2[c]]，并在两个右括号处依次恢复内层与外层上下文。
完成代码联动后进入 LeetCode #1190 迁移代码正确或播放完整轨迹后解锁；查看提示与填入骨架不会解锁。
迁移题：LeetCode #1190「反转每对括号间的子串」
保留“进入内层前保存父上下文、关闭时恢复最近父层”的栈帧模型，但删除重复次数字段，并把右括号的合并规则改为：previous_string + reverse(current_string)。
1 认识原题
2 对照结构
3 映射语义
4 官方样例
LeetCode 1190 · 反转每对括号间的子串
中等字符串栈
题目要求
给定只包含小写英文字母和括号的字符串 s，按照从内到外的顺序，逐层反转每对匹配括号中的字符串，返回不含任何括号的最终结果。
class Solution:
def reverseParentheses(self, s: str) -> str:
pass
约束
1 ≤ len(s) ≤ 2000- 只包含小写字母与圆括号
- 所有括号保证成对匹配
官方示例
输入：s = "(abcd)"
输出："dcba"
输入：s = "(u(love)i)"
输出："iloveu"
输入：s = "(ed(et(oc))el)"
输出："leetcode"
输出契约：结果中不得保留括号；每一层关闭时都只处理当前最内层。
题面依据：LeetCode 官方 #1190 页面
读题检查 1｜函数返回什么？
尚未作答
读题检查 2｜为什么 love 先反转？
尚未作答
完成两道读题检查后进入结构对照
#394 · 字符串解码
栈帧
(previous_string, repeat)左括号保存前缀与次数，清空局部状态
右括号
previous + current * repeat局部任务解码当前嵌套片段
#1190 · 括号内反转
栈帧只保存
previous_string左括号保存前缀，清空当前层字符串
右括号
previous + current[::-1]局部任务构造当前层，再在关闭时反转
迁移判断｜什么被保留，什么被替换？
尚未作答
槽位 1｜栈中保存什么？
进入括号后，哪份父层状态会被覆盖？
槽位 2｜左括号后如何进入新层？
父前缀保存后，当前层应从何处开始？
槽位 3｜右括号如何合并？
先处理当前最内层，再恢复父前缀。
槽位 4｜普通字母如何处理？
字母属于当前最内层，暂不触发恢复。
class Solution:
def reverseParentheses(self, s: str) -> str:
stack = []
current_string = ""
for char in s:
if char == "(":
stack.append(current_string)
current_string = ""
elif char == ")":
current_string = stack.pop() + current_string[::-1]
else:
current_string += char
return current_string
完成 0 / 4 个语义槽位
官方样例轨迹：s = "(u(love)i)"
父前缀栈
当前字符INIT
当前层""
栈深度0
动作初始化
准备解析官方样例。
当前结果：""
可选挑战｜脱离槽位独立重写
检查器验证三个结构语义：保存父前缀、进入新层时清空、右括号执行 previous + current[::-1]。不会自动填入完整答案。
完整轨迹最终应输出
"iloveu"Unit 12 Skill：把嵌套结构解析为上下文栈
看到括号嵌套、局部构造与关闭后恢复外层时，先问：进入内层前哪些变量会被覆盖？把这些变量组成栈帧；遇到关闭符号时弹出最近栈帧，并用题目规定的合并规则恢复父上下文。
主问题#394 字符串解码
迁移问题#1190 括号内反转
统一触发信号进入内层会覆盖父层局部状态
#394 栈帧(previous_string, repeat)
#1190 栈帧previous_string
关闭事件弹出最近栈帧并执行局部合并
关键不变量栈顶始终对应最近未闭合外层
常见错误漏存父前缀、合并顺序颠倒、保留括号
进一步方向递归下降、表达式解析、括号配对跳转
第三章完成：栈与队列你已经从 LIFO / FIFO 走到单调结构、优先队列与嵌套上下文恢复。