题解 | 字符串解码

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return string字符串
 */
void push(char* stack,int* top,char x){
    stack[++(*top)]=x;
}
int pop(char* stack,int* top){
    if(top>=0){
        int x=stack[(*top)--];
        return x;
    }
    return -1;
}


char* decodeString(char* s ) {
    // write code here
    
    char* stack1=(char*)malloc(sizeof(char)*100);//存储 最后一个示例比给定的字符串长度范围要大！所以额外开点
    int top1=-1;//当前元素
    char* stack2=(char*)malloc(sizeof(char)*strlen(s));//操作
    int top2=-1;

    for(int i=0;i<strlen(s);i++){
        if(s[i]!=']'){//入栈
            push(stack1,&top1,s[i]);//放入存储栈
        }else{//遇到']' 处理要复制的子串
            while(top1!=-1&&stack1[top1]!='['){//逆着放入操作栈
                int x=pop(stack1, &top1);
                push(stack2,&top2,x);
            }
            //处理'['
            pop(stack1,&top1);//'['出栈
            int time=0;//复制次数
            int basic=1;
            while(top1>=0&&stack1[top1]>='0'&&stack1[top1]<='9'){
                int temp=(pop(stack1,&top1)-'0')*basic;
                time+=temp;
                basic*=10;
            }
            while(time>0){
                for(int k=top2;k>=0;k--){//复制子串
                    push(stack1, &top1, stack2[k]);
                }
                time--;
            }
            while(top2>=0){//清空操作栈
                pop(stack2, &top2);
            }
        }
    }
    free(stack2);
    return stack1;
}