递归解析方括号结构，遇到 [D... ] 时先展开内部字符串，再重复 D 次拼接。
OJ: luogu
题目 ID: P1928
难度:普及-
标签:递归字符串python
日期: 2026-07-15 22:00
题意
给定压缩字符串。形如 [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
def 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
/**
* 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;
}Guide 风格代码
cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：
cpp
/**
* 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-08-14 14:54
* update_at: 2026-08-14 14:54
*/
/* P1928 外星密码：递归解析，遇到 [k...] 就递归展开括号内的内容。 */
#include <iostream>
#include <string>
std::string compressed; // 待解压的密码
int pos = 0; // 当前解析到压缩串的第几个字符
// 从 pos 开始解析一段内容，遇到 ']' 或串尾就结束，返回解压后的字符串。
// 调用栈天然对应嵌套括号：读到 [ 里的数字后递归，就是进入更里层。
std::string decode() {
std::string result;
while (pos < (int)compressed.size() && compressed[pos] != ']') {
char ch = compressed[pos];
if (ch >= 'A' && ch <= 'Z') {
result += ch; // 普通字母直接加入结果
pos += 1;
} else if (ch == '[') {
pos += 1; // 跳过 '['
int repeat = 0;
// 数字可能不止一位，逐位拼出重复次数。
while (pos < (int)compressed.size() && compressed[pos] >= '0' && compressed[pos] <= '9') {
repeat = repeat * 10 + (compressed[pos] - '0');
pos += 1;
}
std::string inner = decode(); // 递归解析括号内的内容（可能还有嵌套）
for (int i = 0; i < repeat; i += 1) {
result += inner; // 按重复次数展开
}
} else {
pos += 1; // 其余字符（题目保证不会出现）直接跳过
}
}
if (pos < (int)compressed.size() && compressed[pos] == ']') {
pos += 1; // 跳过 ']'，让外层继续解析
}
return result;
}
int main() {
std::cin >> compressed;
std::cout << decode() << '\n';
return 0;
}复杂度
每个压缩字符解析一次，生成输出长度为 L，时间复杂度为
总结
嵌套括号结构通常适合递归解析。关键是让函数既返回展开结果，也返回解析到哪里了。