字符串解码

问题

原题链接：https://leetcode.cn/problems/decode-string

解法

这是一个很经典的栈问题，只要理解了我们用栈存储pair<重复次数，起始位置>，通过pair我们既可以知道要重复的次数，也可以定位到该从哪儿开始重复，因此这就是该算法的主要解决思路。不同情况我们考虑做好对应处理，是字母就存上。是数字就让计数增加即可。是“[”表示前面的就是单独的一段，此刻存入stack。是“]”表示前面是一段的结束，此时该取出栈顶的pair重复存相应字符段一定的次数。

class Solution {
public:
    string decodeString(string s) {
        stack<pair<int,int>> stk;//存储count数和，当前字符串的其实位置
        string ans;
        int count=0; //临时存储的个数
        for(auto& item:s){
            if(isdigit(item)){
                count=count*10+(item-'0');
            }else if(isalpha(item)){
                ans+=item;
            }else if(item=='['){
                stk.push({count,ans.size()});
                count=0;
            }else if(item==']'){
                int n=stk.top().first;
                string s=ans.substr(stk.top().second,ans.size()-stk.top().second);
                for(int i=0;i<n-1;i++){
                    ans+=s;//已经有一个了所以上限为n-1；
                }
                stk.pop();//弹出处理完的元素
            }
        }
        return ans;
    }
};