题目描述

小赵和小钱在练字，小钱对小赵说：你知道吗，我练习的字是有蕴含的。

小赵不服气了，凭什么你的就有蕴含呢？

小钱说，你所看到的并不是我真正练习的字，你需要将我现在写下的字符串里面“%”和“#”之间的字重复符号前的那么多倍，才能看到我真正写的是什么。

你能帮帮小赵吗？

说明：可能存在嵌套的情况，如“3%g2%n##”，返回“gnngnngnn”，输入输出的字符串长度都不超过10000。

输入字符串保证合法，且输出的字符串中只包含大小写英文字母。

输入格式
一行带数字和嵌套括号的字符串。

输出格式
展开的字符串。

输入样例

3%acm#2%acm#

输出样例

acmacmacmacmacm

算法1

(递归) $O(n)$

数字%字母#

每个子序列都是上述的形式

C++ 代码

#include<bits/stdc++.h>
using namespace std;

string str;
int u;

string dfs()
{
    string res;
    while( u < str.size() )
    {
        auto now = str[ u ];
        if( now == '#' ) return res;
        else if( now >= '0' && now <= '9' )
        {
            int k = 0;
            while( str[ u ] != '%' )
            {
                k = k * 10 + str[ u ] - '0';
                u ++;
            }
            u ++;
            string single = dfs();
            while( k -- ) res += single;
        }
        else   res += now;
        u ++;
    }
}

int main()
{
    cin >> str;
    cout << dfs() << endl;
}

算法2

(栈) $O(n)$

注意这种14%abc12%ad#sda#情况
将%单独存入栈中作为标记

C++ 代码

#include<bits/stdc++.h>
using namespace std;

stack< int > nums;
stack< string > str;
vector< string > v;
string tmp, goal, Str;

int main()
{
    cin >> Str;
    int sum = 0;
    string tmp;

    for( auto x: Str )
    {
        if( x >= '0' && x <= '9' )
        {
            if( !tmp.empty() )
            {
                str.push( tmp );
                tmp.clear();
            }
            sum = sum * 10 + ( x - '0' );
        }
        else if( x == '%' )
        {
            string s;
            s = s + x;
            str.push( s );
            nums.push( sum );
            sum = 0;
        }
        else if( x == '#' )
        {
            reverse( tmp.begin(), tmp.end() );
            while( !str.empty() )
            {
                auto xx = str.top();
                str.pop();
                if( xx == "%" ) break;
                reverse( xx.begin(), xx.end() );
                tmp += xx;
            }
            int n = nums.top();
            //cout << n << endl;
            nums.pop();
            reverse( tmp.begin(), tmp.end() );
            auto tt = tmp;
            for( int i = 1 ; i < n; i ++ ) tmp += tt;
            //cout << tmp << endl;
            str.push( tmp );
            tmp.clear();
        }
        else tmp += x;
    }
    if( tmp.length() > 0 ) str.push( tmp );
    while( !str.empty() )
    {
        auto x = str.top();
        str.pop();
        v.push_back( x );
    }
    reverse( v.begin(), v.end() );
    goal.clear();
    for( auto x: v ) goal += x;
    cout << goal << endl;
    return 0;
}