题目描述

给你一个字符串，由[ ，]，数字和大写字母组成，现要求对其解码。字符串中形如[DX]，表示D个连续的X，例如[4CB]或[2[2CB]]都可以表示。一旦出现括号就会有数字，且为正整数，会有两组方括号相邻的情况，如[4A][5B]。

输入样例

AC[3FUN]

输出样例

ACFUNFUNFUN

算法思路

• 通过递归的方式扫描遍历字符串，扫描遍历的同时按照题目要求输出
• 每次$dfs(u)$，若位置$u$是字母，则正常输出即可，下标索引自增，同时进入下一层递归，开始从新的位置扫描字符串
• 每次$dfs(u)$，若位置$u$是[，则扫描数字，输出要求重复的字符串，本层递归实现的是输出位置$u$的[，及与其配对的]之间的字符串解码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

string str;
int len;

void dfs(int u)
{
    //NOTE 递归结束条件
    if (str[u] == ']' || u == len) return;

    if (str[u] == '[')
    {
        u ++;   //跳过'['
        int num = 0;    //开始扫描计数
        while (str[u] >= '0' && str[u] <= '9')
        {
            num = num * 10 + (str[u] - '0');
            u ++;
        }

        while (num --)  //重复输出要求的字符串
            dfs(u);

        //NOTE 匹配消除对应的符号'['、']'
        int waitKey = 1;
        while (waitKey)
        {
            if (str[u] == '[') waitKey ++;
            else if (str[u] == ']') waitKey --;
            u ++;
        }
    }
    else
    {
        while (str[u] >= 'A' && str[u] <= 'Z')
        {
            printf("%c", str[u]);
            u ++;
        }
    }
    dfs(u);
}

int main()
{
    cin >> str;
    len = str.length();

    dfs(0);

    return 0;
}