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

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

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

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

示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
此题关键难点在于中括号的嵌套
针对包含中括号的嵌套问题，一般都用栈来辅助解决。此题也不例外。
定义两个辅助栈，一个用来记录循环数字，一个用来记录要循环的字符串。
在循环外部定义数字变量num，和一个字符串cur，分别用来记录循环数字和字符串。
遍历一边字符串：
1、当当前字符为数字时：

num = num*10 + s[i] - '0';//记录数字

2、当当前字符为普通字符时，记录当前字符：

cur += s[i];

关键在以下遇到括号时的处理
3、当遇到左括号时：
此时表示数字已经记录完毕，当前数字进栈即可，对于字符串cur也进行一次进栈，防止整个字符串开头是没有编码过的字符串开头的，像fe3[lk]这样。如果不是也直接压栈，压入一个空字符串后面相加的时候不影响。
压入后数字清空，字符串清空，去重新记录后续要编码的的字符串。

                numS.push(num);
                strS.push(cur);
                num = 0;
                cur.clear();

4、当遇到右括号时该如何处理(最重要的情况)。
此时已经记录完成了要编码的字符串，遇到右括号进行数字栈弹栈，还原当前的编码字符串，即进行循环次数的编码还原。再将字符串栈顶的元素弹栈，和当前已经还原编码的字符串相连作为cur，此时就是为了处理多重嵌套的问题。当没有括号嵌套时，也没有关系，因为遇到左括号就压了一次栈，这时候也是把之前已经还原好的编码压栈记录了。
最后还原好的cur就是结果。
还是利用了左括号和右括号的对齐与压栈和进栈相互对应，压栈时就把当前已经还原好的结果压入栈，弹栈时，就是把原先还原好的结果连上新的刚还原好的字符串。

class Solution {
public:
    string decodeString(string s) {
        string res = "";
        if(s.length() == 0) return res;
        stack<int> numS;
        stack<string> strS;
        int num = 0;
        string cur = "";
        for(int i=0;i<s.length();i++){
            if(s[i] >= '0' && s[i] <= '9'){
                num = num*10 + s[i] - '0';
            }else if(s[i] == '['){
                numS.push(num);
                strS.push(cur);
                num = 0;
                cur.clear();
            }else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A'  && s[i] <='Z')){
                cur += s[i];
            }else if(s[i] == ']'){
                string tmp = "";
                for(int i=0;i<numS.top();i++){
                    tmp += cur;
                }
                numS.pop();
                cur.clear();
                cur = strS.top() + tmp;
                strS.pop();
            }
        }
        return cur;
    }
};