[Leetcode][Algo] 394. Decode String

题目：

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

 思路：

讲真，这道题知道用栈，但是没啥思路。。。就是属于毛也写不出来的那种题。。。看了别人的答案才有点儿feel。。。可怕。

1.  用两个栈，分别存储数字和中间字符串

2. 局部字符串变量res，用来存储拼接最后的结果

3. 遇到"["就是说要开始准备组合咯~~就要把之前的res，还有数字，都压栈保存起来。然后之前的数字啊，res都清空，为后面做准备。

4. 遇到"]"就是说，哎呀这个需要decode的东东已经over了，可以开始啦。

　　res里面保存的是需要重复的串，因为之前已经push_back了，相当于再重复的次数就是nums-1次。

      重复完了以后，把保存在chars 栈里面的字符串弹出来，接上。把用过的字符串和数字都弹出来。

代码：

class Solution {
public:
    string decodeString(string s) {
        string res="";
        stack<string> chars;
        stack<int> nums;
        int num = 0;
        for(char c:s){
            if(isdigit(c)){  
                num = num * 10 + c-'0'; //calc nums
            }
            else if(isalpha(c)){
                res.push_back(c);  //form string
            }
            else if(c == '['){
                nums.push(num);
                chars.push(res);
                num = 0;
                res = "";
            }
            else if(c == ']'){
                string temp = res;  //already push back once
                for(int i = 0; i<nums.top()-1;i++){   
                    res += temp;
                }
                res = chars.top() + res;
                chars.pop();
                nums.pop();
            }
        }
        return res;
    }
};