Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
有了防护伞,并不能完全避免2012的灾难。地球防卫小队决定去求助外星种族的帮助。经过很长时间的努力,小队终于收到了外星
生命的回信。但是外星人发过来的却是一串密码。只有解开密码,才能知道外星人给的准确回复。解开密码的第一道工序就是
解压缩密码,外星人对于连续的若干个相同的子串”X”会压缩为”[DX]”的形式(D是一个整数且1 <= D <= 99),比如说字符
串”CBCBCBCB”就压缩为”[4CB]”或者”[2[2CB]]”,类似于后面这种压缩之后再压缩的我们称之为二重压缩。如果是
”[2[2[2CB]]]”,则是三重。现在我们将给你外星人发送的密码,请你对其进行解压缩。
[数据范围]
对于50%的数据:解压后的字符串长度在1,000以内,最多只有三重压缩。
对于100%的数据:解压后的字符串长度在20,000以内,最多只有十重压缩。
保证只包含数字、大写字母、’[’和’]’。
【输入格式】
第1行:一个字符串
【输出格式】
第1行:一个字符串
Sample Input
AC[3FUN]
Sample Output
ACFUNFUNFUN
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t093
【题解】
按照所给的规则模拟一下展开的过程就好;
这个过程有很多重复的步骤;
所以考虑用递归来搞;
每一层递归,看看里面还有没有嵌套;
如果没有嵌套,那么就直接处理出来;
然后返回上层;
注意会有这样的输入
[3C[2D]]->CDDCDDCDD
[2C[2D]F[2B]]->CDDFBBCDDFBB
具体的看代码君吧。
【完整代码】
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
string s;
string dfs(int l,int r)
{
int ll =0;
for (ll = l+1;ll <= r-1;ll++)//里面有没有嵌套
if (s[ll]=='[')
break;
if (ll==r)
{
int x = 0,i;
for (i = l+1;i <= r-1;i++)
if (s[i]>='0' && s[i] <= '9')
x = x*10+s[i]-'0';
else
break;
//i..r-1
string t = s.substr(i,r-i);
string ss = "";
for (i = 1;i <= x;i++)
ss+=t;
return ss;
}
else
{
//integer
//ll..rr待处理
int i,x = 0;
for (i = l+1;i<=r-1;i++)
if (s[i]>='0' && s[i]<='9')
x = x*10 + s[i]-'0';
else
break;
string ss = "",ts="";
for (int j = i;j<=r-1;j++)
if (s[j]=='[')
{
int jj = j+1;
int t = 1;
while (t!=0)
{
if (s[jj]==']') t--;
if (s[jj]=='[') t++;
if (t==0) break;
jj++;
}
ss+=dfs(j,jj);
j = jj;
}
else
ss+=s[j];
for (i = 1;i <= x;i++)
ts+=ss;
return ts;
}
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
cin >> s;
int len = s.size();
for (int i = 0;i <= len-1;i++)
if (s[i]=='[')
{
int j = i+1;
int t = 1;
while (j <= len-1 && t!=0)
{
if (s[j]=='[') t++;
if (s[j]==']') t--;
if (t==0) break;
j++;
}
//i..j是一个待展开的东西
cout << dfs(i,j);
i = j;
}
else
putchar(s[i]);
return 0;
}