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;

}