做出来简单，循环或递归反复替换就行。但是如何做到高效？

  1. 反复替换会多次拼接字符串，效率大打折扣。
  2. 重复搜索 [、] 等字符也会使效率大打折扣（想一想最坏情况复杂度是多少）。

下面介绍一种高效算法。我们为每层括号保存

  1. head: 这层括号的首字符在 output 中的起始位置；
  2. repeat: 重复次数。

有多层括号，用栈 s 保存。

  • 遇到“|”：可以确定这两个信息，入栈；
  • 遇到“]”：出栈，从 head 到当前位置复制 repeat - 1 次；
  • 遇到字母：放进 output，等出栈时复制。

整体上只扫描了一次输入串；输出串也是一直往后拼接的，没有回退。总时间复杂度和空间复杂度都是 O(输入串长度 + 输出串长度)，与压缩递归层数无关。

#include <iostream>
#include <tuple>
#include <stack>

using namespace std;

int main() {
    string input, output;
    cin >> input;
    stack<tuple<size_t, size_t> > s; // tuple<head pos, repeat number>
    size_t repeat = 0;
    for (char c : input) {
        if (isalpha(c))
            output.push_back(c);
        else if (isdigit(c))
            repeat = repeat * 10 + c - '0';
        else if (c == '[')
            repeat = 0;
        else if (c == '|')
            s.emplace(output.size(), repeat);
        else if (c == ']') {
            size_t head, tail = output.size();
            tie(head, repeat) = s.top();
            s.pop();
            for (size_t j = 1; j < repeat; j++)
                output.insert(output.end(), output.begin() + head, output.begin() + tail);
        }
    }
    cout << output << endl;
}