递归、显式栈与嵌套字符串解码

以 LeetCode 394「字符串解码」为例：输入由字母与 k[encoded_string] 构成，k 是可多位的重复次数，方括号允许嵌套。例如：

2[abc]       → abcabc
2[3[ab]]     → abababababab
ab2[cd]e     → abcdcde
2[ab]3[xy]   → ababxyxyxy

它既是递归解析的典型题，也是“用一个显式栈模拟递归调用栈”的典型题。

先定义语法和状态

可将输入看作由两类片段连续拼接而成：

表达式 := { 字母 | 次数 '[' 表达式 ']' }
次数   := 一位或多位十进制数字

从左到右解析时维护：

• current：当前层已经解码出的字符串；
• count：当前正在读取的重复次数；
• 遇到 '['：进入下一层；
• 遇到 ']'：当前层结束，得到一个内层字符串并返回上层。

多位数必须累积，而不是只读取一个字符：

count = count * 10 + (ch - '0');

递归思路：函数参数中的下标就是解析游标

递归函数 parse() 的职责可以定义为：

从当前游标开始解析连续片段，遇到当前层对应的 ']' 或输入结束时返回已解码字符串。

每次读入一个字符后推进游标：

1. 字母：直接追加到当前答案；
2. 数字：更新 count；
3. '['：递归解析内层，得到 inner，追加 inner 重复 count 次，并把 count 重置为 0；
4. ']'：结束当前函数，将 current 返回给上一层。

这里的核心不是“记住递归代码”，而是递归调用保存了上一层的局部变量 current 和 count，待内层返回后继续使用它们。count 不重置会使 2[a]3[b] 错误地把后一个次数解析为 23。

递归版本清晰，但嵌套深度极大时可能耗尽调用栈。此时可以直接保存这些局部变量，改写为显式栈。

单栈模拟递归

每个栈帧只需保存“进入下一层之前”的两个局部变量：

using Frame = std::pair<std::string, std::size_t>;
// first: 上一层已经累积的前缀；second: 该层的重复次数

因此不需要一个字符串栈加一个数字栈；一个 std::vector<Frame> 或 std::stack<Frame> 就足够。

#include <cctype>
#include <limits>
#include <stdexcept>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

namespace detail {

void append_repeated(std::string& out, const std::string& part,
                     std::size_t times) {
    if (part.empty() || times == 0) return;

    // 避免 part.size() * times 或 reserve 的长度溢出。
    if (times > (out.max_size() - out.size()) / part.size()) {
        throw std::length_error("decoded string is too large");
    }

    out.reserve(out.size() + part.size() * times);
    while (times-- > 0) out += part;
}

bool is_ascii_letter(char ch) {
    return ('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z');
}

} // namespace detail

std::string decode_string(std::string_view text) {
    using Frame = std::pair<std::string, std::size_t>;

    std::vector<Frame> frames; // 一个栈，每项就是一个递归调用现场
    std::string current;
    std::size_t count = 0;
    bool reading_count = false;

    for (char ch : text) {
        if (detail::is_ascii_letter(ch)) {
            if (reading_count) {
                throw std::invalid_argument("a number must be followed by '['");
            }
            current += ch;
        } else if ('0' <= ch && ch <= '9') {
            const auto digit = static_cast<std::size_t>(ch - '0');
            if (count > (std::numeric_limits<std::size_t>::max() - digit) / 10) {
                throw std::length_error("repeat count is too large");
            }
            count = count * 10 + digit;
            reading_count = true;
        } else if (ch == '[') {
            if (!reading_count) {
                throw std::invalid_argument("'[' must have a repeat count");
            }
            // 递：保存本层现场，开始一层全新的 current。
            frames.emplace_back(std::move(current), count);
            current.clear(); // moved-from string 可安全清空并复用
            count = 0;
            reading_count = false;
        } else if (ch == ']') {
            if (reading_count || frames.empty()) {
                throw std::invalid_argument("unbalanced brackets");
            }
            // 归：恢复调用现场；current 是内层递归的返回值。
            auto [prefix, times] = std::move(frames.back());
            frames.pop_back();
            detail::append_repeated(prefix, current, times);
            current = std::move(prefix);
        } else {
            throw std::invalid_argument("unexpected character");
        }
    }

    if (reading_count || !frames.empty()) {
        throw std::invalid_argument("incomplete encoded string");
    }
    return current;
}

在线评测通常保证输入合法、解码结果长度有限，因此可省略异常分支；工程代码仍应限制重复次数和最终输出大小，避免恶意输入造成内存耗尽。

复杂度

设输入长度为 n，最终输出长度为 L。输出本身至少需要 O(L) 时间和空间。上面实现的准确时间为 O(n + M)，其中 M 是所有已完成栈帧中追加字符数量的总和；深度嵌套但重复次数为 1 时，中间字符串会被多层复制，M 可以大于 L。在常见题目给定的输出上限下，这种实现足够直接可靠。

显式帧额外使用 O(depth) 个 Frame，同时还会保存各层前缀字符串；递归版同样需要调用栈和这些中间结果，只是由语言运行时维护。

反向问题：从解码串构造 k[...]

给定 aaabcbc，要求得到 3[a]2[bc]，看似是解码的逆操作，但必须先问清目标：同一个字符串的编码不唯一。

aaabcbc
3[a]2[bc]  // 能解码成 aaabcbc，但长度为 9
aaa2[bc]   // 也能解码，长度为 8
aaabcbc    // 原串长度为 7

所以若题意是“最短编码”，aaabcbc 应保持原样；若题意是“把连续重复片段都压成 k[...]”，则可以约定输出 3[a]2[bc]。两者是不同题目。

规则固定的连续重复压缩

以下示例采用的规则是：从左到右寻找当前位置开始的最长重复覆盖段；覆盖长度相同时选择更短的循环单元。单元内部继续递归压缩。它会得到题目期望的结果，但这是一个可解释的格式化策略，不保证全局最短。

#include <string>
#include <string_view>

struct Run {
    std::size_t unit_length = 1;
    std::size_t repeats = 1;
    std::size_t span = 1;
};

Run longest_repeated_run(std::string_view s, std::size_t start) {
    Run best;
    const std::size_t n = s.size();

    for (std::size_t unit = 1; start + 2 * unit <= n; ++unit) {
        std::size_t repeats = 1;
        while (start + (repeats + 1) * unit <= n &&
               s.substr(start, unit) == s.substr(start + repeats * unit, unit)) {
            ++repeats;
        }

        const std::size_t span = repeats * unit;
        if (repeats >= 2 &&
            (span > best.span || (span == best.span && unit < best.unit_length))) {
            best = {unit, repeats, span};
        }
    }
    return best;
}

std::string encode_repeated_runs(std::string_view s) {
    std::string out;
    for (std::size_t pos = 0; pos < s.size();) {
        const Run run = longest_repeated_run(s, pos);
        if (run.repeats == 1) {
            out += s[pos++];
            continue;
        }

        out += std::to_string(run.repeats);
        out += '[';
        out += encode_repeated_runs(s.substr(pos, run.unit_length));
        out += ']';
        pos += run.span;
    }
    return out;
}

// encode_repeated_runs("aaabcbc") == "3[a]2[bc]"

这个朴素实现会反复比较子串，适合作为思路展示；长字符串需要哈希、Z 函数/KMP 或 DP 来优化重复周期检测。

如果要求全局最短编码：区间 DP

标准“最短编码”题通常用区间 DP：

dp[left][right] = 子串 s[left..right] 的最短合法编码

对每个区间：

1. 初始值是原子串；
2. 枚举分割点，尝试 dp[left][mid] + dp[mid+1][right]；
3. 若整个子串由长度 p 的周期单元重复 r 次组成，则尝试 to_string(r) + '[' + dp[left][left+p-1] + ']'；
4. 仅当候选字符串严格更短时替换答案。

朴素区间 DP 常为 O(n³) 量级（周期检测方式会影响常数和复杂度）。它会正确地区分“可压缩”和“压缩后更短”：对 aaabcbc，最短答案就是原串，而不是 3[a]2[bc]。

可迁移的结论

“递归改显式栈”时，不是机械地把函数换成循环，而是先列出每个递归层返回前仍需要哪些局部变量，再把它们打包为一个栈帧。字符串解码需要 {前缀, 重复次数}；树的后序遍历可能需要 {节点, 访问阶段}；表达式解析还可能需要 {操作符, 操作数}。栈帧设计正确，递归到迭代的转换就自然完成。

关联笔记

• 字符串匹配与 KMP
• 树与二叉搜索树
• 图搜索、回溯与并查集
• 动态规划与贪心