看到3[a2[bc]]这种字符串时，很多人第一反应是找对称括号，然后手算出结果。但字符串解码这道题，真正要训练的不是“肉眼观察对称”，而是让你像一台解析器一样，逐字消费输入，把数字、方括号、普通字母当作三类信号来处理。字符串解码可以说是算法题里的一棵常青树，也是从“会写栈”到“理解状态机”的一个分水岭：它看起来只是重复拼接，但一旦出现多层嵌套，没有清晰的“保存现场/恢复现场”思维，代码很快就会乱成一团。
这篇文章会把字符串解码的两种主流解法——双栈迭代法和递归DFS法——完整拆开，包括为什么需要两个栈、递归函数里的索引为什么要用返回值传递、多位数字怎么累加、拼接顺序为什么不能反，以及我实际调试时踩过的几个坑。无论你是刚开始刷题的新手，还是想把这题讲给别人听的面试准备者，这篇文章都值得看完。我会把每一步的“为什么”也解释清楚，而不是丢一个能过的代码就完事。
1. 不要急着写代码，先把题目规则和嵌套直觉建立起来
1.1 编码规则到底在说什么
题目给出的规则用一个模式就能概括：k[encoded_string]，表示方括号内部的字符串重复 k 次，其中 k 是一个正整数。这里的encoded_string不一定是普通字母串，它还可以继续包含新的k[encoded_string]，也就是可以嵌套。
举几个最直观的例子：
3[a]2[bc]解码成aaabcbc3[a2[c]]解码成accaccacc2[abc]3[cd]ef解码成abcabccdcdcdefabc3[cd]xyz解码成abccdcdcdxyz
注意最后两个例子：方括号前面或后面可以有普通字母。这些“光秃秃”的字母不属于任何重复块，它们必须原样保留，并且位置的先后顺序不能变。也就是说，真正被“解码”的单元是k[...]这个整体，其他字符都是普通字面量。
还有一个容易忽略的点：题目一般会保证所有括号都是合法配对的，也就是不会出现[a]b[c这种残缺输入。但是如果实际项目里要解析用户生成的模板，括号配对这个假设就不一定成立了。因此，写代码前确认输入约束是一件很重要的事，后面我会专门讲。
1.2 方括号嵌套天然对应“栈”和“递归”
3[a2[c]]这种结构，如果用手工展开，你会不自觉地先处理内层：
先看最内层
2[c]，得到cc然后把结果放回上一层：
a + cc，变成3[acc]最后再乘以 3，得到
accaccacc
这个“从内向外”的处理顺序，和栈的后进先出特性完全一致。最内层的括号最后进入，却最先被解析；外层括号先进入，最后才被结算。换句话说，方括号的嵌套深度有多少层，解析时就需要记住多少层“尚未完成的上下文”。
这里可以用俄罗斯套娃来类比：最外层的套娃要先打开，但最里层的小套娃是最先被看见的。当你打开一个套娃时，你暂时放下了外面的那一层；等你把里面的套娃处理完，又会回来继续组装外层的部分。在代码里，这个“暂时放下”就是入栈，“回来组装”就是出栈。
同样地，递归也很自然地匹配这个结构：每当遇到[，就调用一个新函数去解析更内层的块；内层解析完返回结果，外层再继续。函数调用栈本身就是替你保存上下文的容器，所以递归解法可以不用手写栈。理解这两种思路，是吃透字符串解码的关键。
2. 双栈迭代解法：分开放置“重复次数”和“上层字符串”
2.1 为什么一个栈不够
很多人刚开始会想：这不就是括号匹配吗？我只要用一个栈，遇到]就弹出来拼接。
但这道题和纯括号匹配有一个重要区别：每个括号块除了需要弹出一段字符串，还必须知道自己被重复了多少次。如果你只用一个栈，那栈里既要放字符串，又要放数字。pop 出来的时候，你怎么知道弹出来的是数字还是字符串？虽然可以用元组把两者打包放进去，但手动维护起来变数很多，出错的概率也更高。
更合理的做法是用两个栈：
数字栈
count_stack：保存每一层方括号前面的重复次数。字符串栈
str_stack：保存进入当前方括号之前，已经拼好的那一部分结果。
为什么要这么拆？本质原因是，处理嵌套时有两个独立维度的状态需要保存：一个是“这一层当前重复多少次”，另一个是“外层之前已经构造到什么程度”。它们会同时变化，也同时被需要，所以干脆分开存，让每个栈的职责单一。
我的理解方式是：每当遇到一个[，就等于对当前的解析过程喊了一声“暂停”，把当前的重复次数和字符串前缀保存起来，然后去处理内部的内容；每当遇到一个]，就是从最内层返回上一层，弹出之前保存的上下文，把这一层的结果合并进去。
2.2 遍历过程中每个字符的三种处理逻辑
双栈解法的核心就是维护两个变量：cur_num表示当前连续读到的数字，cur_str表示当前层已经累积的字符串。扫描字符串的每一个字符，分四种情况处理：
数字：累加到
cur_num上。注意数字可能是多位，比如12[a]，所以要用cur_num = cur_num * 10 + int(ch)。字母：追加到
cur_str。这里不用管它属于哪一层，因为在当前扫描状态下，我们本来就是在“当前层”累积字符。[：准备进入新的一层。先把cur_num压入数字栈，把cur_str压入字符串栈，然后重置cur_num = 0、cur_str = ""。]：当前层结束。从数字栈弹出重复次数count，从字符串栈弹出上一层的字符串prev_str，然后拼接：cur_str = prev_str + cur_str * count。
这个逻辑写成 Python 代码非常短：
def decode_string(s: str) -> str: count_stack = [] str_stack = [] cur_num = 0 cur_str = "" for ch in s: if ch.isdigit(): cur_num = cur_num * 10 + int(ch) elif ch == "[": count_stack.append(cur_num) str_stack.append(cur_str) cur_num = 0 cur_str = "" elif ch == "]": repeat_count = count_stack.pop() prev_str = str_stack.pop() cur_str = prev_str + cur_str * repeat_count else: cur_str += ch return cur_str很多初学者看不懂为什么遇到[要把cur_str重置为空。其实这不是丢掉已有结果，而是因为字符串栈已经把之前的cur_str保存好了。重置为空是为了让这个变量能用来累积“当前这一层”的内容。等遇到]时，再把它和之前的cur_str拼接起来。
cur_str = prev_str + cur_str * repeat_count这一行的顺序也很关键。prev_str是外层已经构造好的内容，它必须在前；cur_str是刚刚解析完的括号块内容，它在后。如果顺序反了，比如先拼接cur_str * count再加prev_str，那整个字符串的顺序就全错了。
2.3 手动走一遍2[a3[bc]]，建立“保存现场”的直觉
拿一个带嵌套的例子来手推，这样比只看代码更有体感。输入2[a3[bc]]，期望输出是abcbcabcbc，过程如下：
| 当前字符 | cur_num | cur_str | 数字栈 | 字符串栈 | 动作说明 |
|---|---|---|---|---|---|
| 初始 | 0 | "" | [] | [] | 开始 |
2 | 2 | "" | [] | [] | 累积数字 |
[ | 0 | "" | [2] | [""] | 保存外层状态并清零 |
a | 0 | "a" | [2] | [""] | 普通字母，拼入当前层 |
3 | 3 | "a" | [2] | [""] | 累积数字 |
[ | 0 | "" | [2, 3] | ["", "a"] | 再次保存当前状态并清零 |
b | 0 | "b" | [2, 3] | ["", "a"] | 拼入内层 |
c | 0 | "bc" | [2, 3] | ["", "a"] | 拼入内层 |
] | 0 | "abcbc" | [2] | [""] | 弹出次数3和前缀"a"，"a" + "bc"*3 |
] | 0 | "abcbcabcbc" | [] | [] | 弹出次数2和空串，空串 +"abcbc"*2 |
这个表格值得自己走一遍感受一下。每次出现[，cur_num和cur_str都被重置，但重置前的最外层状态已经被妥善保存在栈里。等遇到]，再从栈里取回来。这样循环往复，嵌套多少层都不怕。
如果只看最终代码，这题很短很优雅；但实际面试或实践中，最容易出问题的恰恰是“重置”这一步。之所以要把这两个变量压进栈再清零，是因为解析器的本质是一个“逐层推进”的过程：每一层的状态之间互不干扰，只有在层结束的那一刻才需要合并。
3. 递归DFS解法：让函数调用栈替你想事情
3.1 递归与嵌套结构的天然对应
双栈解法需要你手动管理“暂停/恢复”，而递归解法把这个负担交给了函数调用栈。思路非常直接：写一个递归函数dfs(s, i)，它从位置i开始解析一个编码块，返回两个值——解析出来的字符串，以及解析结束后下一个要处理的下标。
为什么需要返回下标？因为字符串是一个顺序结构，递归进入内层解析后，必须知道内层主体结束的]在哪里，外层才能从正确的位置继续往下读。如果用全局变量保存下标，一旦递归嵌套，全局变量在层层调用之间互相覆盖，结果会非常混乱。用返回值传递下标是教科书里处理字符串递归解析的标准做法，这里也一样。
3.2 递归函数的三个分支
代码可以这样写：
def decode_string_recursive(s: str): def dfs(i: int): res = [] num = 0 while i < len(s): ch = s[i] if ch.isdigit(): num = num * 10 + int(ch) i += 1 elif ch == "[": i += 1 sub_str, i = dfs(i) res.append(sub_str * num) num = 0 elif ch == "]": i += 1 return "".join(res), i else: res.append(ch) i += 1 return "".join(res), i return dfs(0)[0]这个函数内部分三个关键分支：
数字分支：和双栈解法一样，用
num = num * 10 + int(ch)处理多位数字。[分支：这是递归的核心。先让下标加 1，跳过左括号，然后递归调用dfs(i)。递归返回时，我们得到了内层解析出的字符串sub_str和新的下标i。此时把sub_str * num加到结果列表里。这里有个重要的细节：num需要重置为 0，否则下一个数字块会继续使用上一个块的重复次数。]分支：说明当前这一层已经结束，直接返回当前拼接好的字符串和i + 1，跳过右括号。
为什么这里把字符收集在res列表里，而不是直接拼接字符串？因为 Python 字符串是不可变对象，频繁+=在深层循环里会有额外开销。用列表收集，最后"".join(res)一次成型，是一个更稳的习惯。当然，对于这道题的规模，直接拼字符串也能过，只是代码洁癖问题。
3.3 双栈和递归的对比：什么时候选哪个
两种解法都能做到时间复杂度和空间复杂度相近，但实际使用时有很多微妙差异。用一个表格对比更清晰：
| 维度 | 双栈迭代 | 递归DFS |
|---|---|---|
| 上下文保存方式 | 显式数字栈 + 字符串栈 | 函数调用栈隐式保存 |
| 理解门槛 | 需要理解“保存现场/恢复现场” | 更贴近手工展开的直觉 |
| 嵌套深度风险 | 无栈溢出风险，迭代可控 | 递归深度受语言限制，嵌套过深可能爆栈 |
| 代码长度 | 较短，但状态变量多 | 较短，但需要理解返回值传递下标 |
| 推荐场景 | 面试实现、工程代码、解析器 | 思路讲解、原型验证、口头描述 |
我个人在面试里讲这道题时，会先用递归解释嵌套逻辑，因为它的思路最贴近人脑；然后实现时写成双栈迭代，因为它在极端输入下更稳定，也不会被递归深度卡住。两者的代码量其实差不多，掌握一个另一个也能顺手写出来。
4. 最容易踩的坑与一套可复现的自测用例
4.1 多位数字的累积与重置：一对孪生陷阱
第一个常见的坑是数字累加起来不对。比如输入12[a]，如果只写cur_num = int(ch)而不是cur_num = cur_num * 10 + int(ch)，那12会被读成1和2两个独立的数字，结果变成a重复 2 次而不是 12 次。
第二个常见的坑是重置时机不对。有人会在遇到[时压栈，但不把cur_num清零。这样处理完一个嵌套块后，cur_num还保留着上一个块的重复次数，遇到下一个[时，新的次数会在这个陈旧值基础上继续累加，导致结果完全错乱。
这两个坑往往同时出现。建议在写代码时自查一遍：cur_num什么时候清零？答案是有且只有两个时机——遇到[压栈后、遇到]弹栈结算后。其他时候，cur_num要么在累积数字，要么保持不动。
4.2 拼接顺序：为什么prev_str必须在左边
还有一类错误是把拼接写反。错误版本长这样：
cur_str = cur_str * repeat_count + prev_str这行代码会把括号块的内容放到外层内容的前面。比如输入"a2[b]"，正确结果是abb，但这个错误版本会算出bba。原因很直接：我们在解析过程中，prev_str代表的是“进入当前括号之前已经存在的内容”，它一定是当前块的前缀，不可能出现在后面。
另外，cur_str * repeat_count和repeat_count * cur_str在 Python 里结果一致，因为乘法满足交换律，所以这一部分顺序写反不影响结果。真正影响结果的是prev_str和cur_str * repeat_count两者的左右位置。这个顺序问题在递归解法里同样存在，递归拼接时也要注意把内层解析结果追加在外层结果的右边。
4.3 自测用例清单：覆盖空串、多位数字、嵌套、前后缀
一道题写完提交前，我会习惯性跑一组用例，覆盖这几个最容易出事的边界。下面是我会用的清单：
| 输入 | 期望输出 | 用来验证什么 |
|---|---|---|
"" | "" | 空字符串边界 |
"abc" | "abc" | 无括号，原样返回 |
"3[a]" | "aaa" | 最基础的重复 |
"3[a2[c]]" | "accaccacc" | 多层嵌套 |
"2[abc]3[cd]ef" | "abcabccdcdcdef" | 多个块 + 普通前缀/后缀 |
"12[a]" | "aaaaaaaaaaaa" | 多位数字 |
"a[b]c" | "abc"（次数是1？） | 需要结合具体题目确认 |
"100[a]" | "a" * 100 | 大重复次数 |
最后一个用例顺便能测出语言字符串乘法的性能表现，尤其是 Python 里"a" * 100是很自然的写法，不用担心。但如果某个语言对大次数乘法有特殊语义，务必先测试。
5. 从字符串解码到真正的解析器：一种可迁移的思维模型
5.1 把题目理解为“带状态的字符流扫描”
字符串解码并不只是一个独立的算法题。当你把它拆开看，它其实是一个极简的文本解析器：输入是字符流，输出是展开后的字符串；中间靠cur_num和cur_str两个状态变量来记录解析进度，遇到[暂停当前状态，遇到]恢复并结算。
这种“状态变量 + 栈”的组合，在真实工程中非常常见：
模板引擎解析
{{ variable }}时需要找到变量边界。JSON 解析器遇到
{[时需要维护对象嵌套层级。配置文件解析器处理
key = value时需要记录当前段名。文件系统路径解析要处理
.、..和符号链接。
所有这些场景的核心逻辑，都和字符串解码一样：逐字符扫描，遇到某种边界符号就改变状态或压栈，结束边界就弹栈合并。理解这道题，相当于理解了这一类解析问题的最小范式。
5.2 同类变体：从单层重复到笛卡尔积展开
字符串解码还有不少变体，掌握基础解法后可以顺带想一想。
比如有的变体会把方括号里的内容变成"2[a,b]"，要求展开成a,ba,b，也就是每个元素都要重复 2 次，中间保留分隔符。这种题的双栈解法骨架完全一样，差别只在于弹栈后不是简单拼接字符串，而是要对一组元素做循环展开。
再比如有的变体和计算器结合，像"3[a]+2[b]"，要求先按加法规则分段，每段分别解码再合并。这种题的本质是给字符串解码叠加一层运算优先级，而优先级本身又可以用栈或递归来解决。
思路都是一脉相承的：识别嵌套边界，用栈保存上下文，在合适的时机合并结果。遇到变体题时，先想清楚“栈里存什么、什么时候压栈、什么时候弹栈、弹出来怎么合并”这四个问题，答案就基本出来了。
6. 面试和实战中的几个实操心得
6.1 写代码前先确认三件事
字符串解码的题目描述通常默认了几个条件，但实际场景或面试追问时不一定完全一致。我会在写代码前主动确认：
k 是否一定是正整数？如果是 0，
0[a]应该输出空串，代码要额外处理吗？数字是否可能为多位？如果题目没说明，按照常规理解写成多位累积一定更安全。
输入是否保证所有括号匹配且不交叉？如果不保证，要不要加异常检测？
其实在大多数在线评测里，这些约束都是给定的。但如果是设计一个真实功能，用户输入什么都有可能。提前确认一遍，能避免写出“只能过题但经不起真实数据”的脆弱代码。
六点二：把双栈解法翻译成“保存现场/恢复现场”
如果让我用一句话总结双栈解法，那就是：
遇到
[保存现场，遇到]恢复现场。
这句话不仅适用于这道题，还适用于一大批“嵌套结构解析”的题。每次处理左括号，就把当前上下文压栈，重置当前状态；每次处理右括号，就弹出上下文，把当前层的结果合并进去。这样的思维模型比死记代码更容易迁移，遇到类似题目时也能快速搭出框架。
6.3 我第一次写这套代码时踩的坑
最后分享一点实际经历。我最初写这道题时，用的是一个单一的列表，试图通过判断元素类型来区分数字和字符串。结果嵌套多了之后，pop 出来的元素既要判断isinstance，还要处理各种边界顺序，代码变得又长又丑，而且 debug 起来非常痛苦。后来改成双栈，思路一下清晰了，代码也短了一半。
另一次让我印象比较深的失误发生在重置上：我把cur_str的重置写成了cur_num的重置，结果输入2[a]时，第一次]正常输出，第二次处理却直接用上了上一次残留的cur_str。那次 debug 花了不少时间，最后才发现是重置错了变量。从那以后，我再写这类代码都会刻意检查“压栈后的清零”和“弹栈前的取值”是否一一对应。
字符串解码本身不难，但它背后的解析思维在真实场景里复现率很高。双栈迭代法和递归DFS法，一个偏工程、一个偏原理，两个都掌握之后，再看各种带括号嵌套的题目都会有一种“不过如此”的感觉。如果你现在写这道题还不顺手，不用急，先按这篇文章里的表格手动走一遍2[a3[bc]]的过程，再把代码自己敲一遍，很快就能建立起手感。
