【leetcode】394. 字符串解码

题目链接：力扣

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

 这道题……好绕啊 以至于我看题解的时候都看了好久  才明白了。

首先不可避免的是，要记录两个值，一个是字符串，一个是字符串重复的次数，即数字

考虑有嵌套[]的情况下(如示例2：3[a2[c]] )由于在遍历字符串s的过程中，会冲掉前面保存的数组和字符串，所以要选用栈来对字符串和数字进行保存

这里用到两个栈，（也有人用一个栈的 stack<pair<string, int>> st，其本质也是两个栈，为了更清楚的表达，这里我们采用两个栈）

首先定义了两个栈

stack<string> Mystack;

stack<int> Numstack;

然后以此遍历字符串s

遍历字符有四种情况
        //1、如果是数字 将数字转成整型数字等待处理
        //2、如果是字符 将字符添加到当前临时字符串中
        //3、如果是'['  将当前数字和临时字符串添加到各自栈中
        //4、如果是']'  将数字和字符栈各取出，然后拼接成新的临时字符串

    string decodeString(string s) {stack<string> Mystack;stack<int> Numstack;string res = "";string temp="";  //记录循环数for(int i=0; i<s.size();i++){if('0'<=s[i] && s[i] <='9'){temp += s[i];continue;}else if(s[i] == '['){int count = atoi(temp.c_str());Numstack.push(count);Mystack.push(res);temp = "";res = "";}else if('a'<=s[i] && s[i]<='z'){res += s[i];   }else if(s[i] == ']'){ string pre  = Mystack.top();     //当前左括号之前的字符串int n = Numstack.top();          //当前左括号之前的数字string cur;                      //当前右括号内的字符串for(int i=0; i<n;i++)cur+=res;res = pre + cur;Numstack.pop();Mystack.pop();}}return res;}