外星密码

题意

给定压缩字符串。形如 [DX] 表示把字符串 X 重复 D 次，压缩可以嵌套。输出完整解压后的字符串。

思路

递归解析最自然。

写函数 parse(text, index)，从 index 开始解析，直到遇到 ] 或字符串结束，返回：

当前层展开后的字符串；
解析结束后的下标。

遇到大写字母，直接加入当前层结果。

遇到 [：

读取后面的数字 D；
递归解析括号内部；
把内部字符串重复 D 次加入当前层。

Python 知识

str.isupper() 判断是否是大写字母。
str.isdigit() 判断数字字符，适合读取一位或两位重复次数。
函数返回 (结果字符串, 新下标)，可以避免使用全局指针。
解压结果长度不超过 20000，字符串拼接列表 parts 足够稳妥。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27def parse(text, index):
    parts = []

    while index < len(text) and text[index] != "]":
        if text[index].isupper():
            parts.append(text[index])
            index += 1
        elif text[index] == "[":
            index += 1
            repeat = 0
            while text[index].isdigit():
                repeat = repeat * 10 + int(text[index])
                index += 1
            inner, index = parse(text, index)
            parts.append(inner * repeat)
        else:
            index += 1

    if index < len(text) and text[index] == "]":
        index += 1

    return "".join(parts), index


encoded = input().strip()
decoded, _ = parse(encoded, 0)
print(decoded)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

string s;
int idx;

string decode() {
    string res;
    while (idx < (int)s.size() && s[idx] != ']') {
        if (isupper(s[idx])) { res += s[idx]; idx++; }
        else if (s[idx] == '[') {
            idx++; // 跳过 '['
            int repeat = 0;
            while (isdigit(s[idx])) {
                repeat = repeat * 10 + (s[idx] - '0');
                idx++;
            }
            string inner = decode();
            for (int i = 0; i < repeat; i++) res += inner;
        } else idx++;
    }
    if (idx < (int)s.size() && s[idx] == ']') idx++;
    return res;
}

int main() {
    cin >> s;
    idx = 0;
    cout << decode() << endl;
    return 0;
}

复杂度

每个压缩字符解析一次，生成输出长度为 L，时间复杂度为 $O(L)$ ，空间复杂度为 $O(L)$ 。

总结

嵌套括号结构通常适合递归解析。关键是让函数既返回展开结果，也返回解析到哪里了。

目录

题意

思路

Python 知识

代码

复杂度

总结