P1928 外星密码

克尔苏加德 · 2020-03-18 23:32:45 · 题解

看别人都是递归的方法，我来发一手纯粹的栈吧

我们将读入依次入栈，仔细读题后发现其实除了右括号对栈有影响，其他的字符对于栈都是没有影响的。

那么怎么来处理右括号呢

• 当一个右括号遇到一个右括号，就从栈顶弹出，直至弹出一个左括号为止
• 然后将中间这段的数字和字符分离开，假设分离的数字为k，分离的字符串为s1
• 再把s1按照顺序k次压入栈
• 最后只要将栈从低向上输出就可以了

下面就是代码啦

#include<iostream>
#include<cstdio>
#include<stack>

using namespace std;

stack<char> q;
string s;
char s1[20005],ss[20005];  //注意这里不能将s1,ss定义为字符串，不然会全re，我也不知道为什么，还求各位大佬帮忙解决下 
int k,k1,k2;

int main(){
    cin>>s;
    for(int i = 0; i < s.length(); i ++){
        if(s[i] == ']'){
            k1 = 0;
            while(q.top() != '['){
                k1 ++;
                s1[k1] = q.top();
                q.pop();
            }
            q.pop();
            k2 = k1;
            k = 0;
            while(s1[k2] >= '0' && s1[k2] <= '9'){
                k = k * 10 + s1[k2] - '0';
                k2 --;
            }
            for(int j = 1; j <= k; j ++)
                for(int l = k2; l > 0; l --)
                    q.push(s1[l]);
        }
        else q.push(s[i]);
    }
    k = 0;
    while(!q.empty()){
        ss[k] = q.top();
        q.pop();
        k ++;
    }
    for(int i = k - 1; i >= 0; i --)
        cout<<ss[i];
    return 0;
}