码蹄集丨字符串的解码

B站老师思路讲解：https://www.bilibili.com/video/BV1r84y1E7TB/?t=1415.0&vd_source=3ae2a916df1bc5c1114c2bf3e95a2118

Python代码实现：

原文链接：https://blog.51cto.com/u_15745546/5950626

def main():
    s = input()
    n = len(s)
    arr = []
    mm = {}
    for i in range(n):
        if s[i] == '[':
            arr.append(i)
        elif s[i] == ']':
            mm[arr[-1]] = i
            arr.pop(-1)

    def decode(ii, jj):
        if ii > jj:
            return ""
        if ii == jj:
            return s[ii]

        if s[ii] == '[':
            x = ii + 1
            while x + 1 < jj and '0' <= s[x + 1] <= '9':
                x += 1

            k = int(s[ii + 1: x + 1])
            return decode(x + 1, mm[ii] - 1) * k + decode(mm[ii] + 1, jj)

        else:
            x = ii
            while x + 1 <= jj and s[x + 1] not in "[]":
                x += 1

            return s[ii: x + 1] + decode(x + 1, jj)

    print(decode(0, n - 1))


if __name__ == '__main__':
    main();

C++代码实现：

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

string decode(string s, int ii, int jj, unordered_map<int, int>& mm) {
    if (ii > jj) {
        return "";
    }

    if (ii == jj) {
        return string(1, s[ii]);
    }

    if (s[ii] == '[') {
        int x = ii + 1;
        while (x + 1 < jj && s[x + 1] >= '0' && s[x + 1] <= '9') {
            x++;
        }
        int k = stoi(s.substr(ii + 1, x - ii));
        string sub_str = decode(s, x + 1, mm[ii] - 1, mm);
        string res = "";
        for (int i = 0; i < k; i++) {
            res += sub_str;
        }
        return res + decode(s, mm[ii] + 1, jj, mm);
    } else {
        int x = ii;
        while (x + 1 <= jj && s[x + 1] != '[' && s[x + 1] != ']') {
            x++;
        }
        return s.substr(ii, x - ii + 1) + decode(s, x + 1, jj, mm);
    }
}

int main() {
    string s;
    cin >> s;

    int n = s.length();
    vector<int> arr;
    unordered_map<int, int> mm;

    for (int i = 0; i < n; i++) {
        if (s[i] == '[') {
            arr.push_back(i);
        } else if (s[i] == ']') {
            mm[arr.back()] = i;
            arr.pop_back();
        }
    }

    cout << decode(s, 0, n - 1, mm) << endl;

    return 0;
}

提交测试结果：