【题目来源】
洛谷：P1928 外星密码 - 洛谷 (luogu.com.cn)
【题目描述】
有了防护伞，并不能完全避免 \(2012\) 的灾难。地球防卫小队决定去求助外星种族的帮助。经过很长时间的努力，小队终于收到了外星生命的回信。但是外星人发过来的却是一串密码。只有解开密码，才能知道外星人给的准确回复。解开密码的第一道工序就是解压缩密码，外星人对于连续的若干个相同的子串 X 会压缩为 [DX] 的形式（\(D\) 是一个整数且 \(1\le D\le 99\)），比如说字符串 CBCBCBCB 就压缩为 [4CB] 或者[2[2CB]]，类似于后面这种压缩之后再压缩的称为二重压缩。如果是 [2[2[2CB]]] 则是三重的。现在我们给你外星人发送的密码，请你对其进行解压缩。
【输入】
输入一行，一个字符串，表示外星人发送的密码。
【输出】
输出一行，一个字符串，表示解压缩后的结果。
【输入样例】
AC[3FUN]
【输出样例】
ACFUNFUNFUN
【解题思路】
【算法标签】
《洛谷 P1928 外星密码》 #模拟# #字符串# #递归# #分治#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 递归解压缩字符串函数
string f(string s)
{string ans; // 存储解压后的结果// 遍历输入字符串的每个字符for (int i = 0; i < s.length(); i++) {// 如果是普通字符，直接加入结果if (s[i] != '[') {ans += s[i];continue;}// 处理压缩部分 [DX] 格式int mark = i + 1; // 数字开始位置int d = 0; // 重复次数Dint right = 1; // 括号嵌套计数器// 解析数字Dwhile (s[mark] >= '0' && s[mark] <= '9') {d = d * 10 + (s[mark] - '0');mark++;}// 找到匹配的右括号位置for (int j = i + 1; ; j++) {if (s[j] == '[') right++; // 遇到左括号，嵌套层数+1if (s[j] == ']') right--; // 遇到右括号，嵌套层数-1// 找到当前层级的右括号if (right == 0) {// 提取X部分并递归解压string x = s.substr(mark, j - mark);x = f(x); // 递归解压X// 将D个X添加到结果中for (int k = 0; k < d; k++) ans += x;i = j; // 跳过已处理的部分break;}}}return ans;
}int main()
{string s;cin >> s; // 读取压缩字符串cout << f(s); // 输出解压结果return 0;
}
【运行结果】
AC[3FUN]
ACFUNFUNFUN