Given an encoded string, return its decoded 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.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Example 4:

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

  思路一：利用递归去做，如果遇到数字就进行展开，由于递归的结构就会自动从里到外一层一层的展开返回，注意检索的数组index得传引用，o(n)的时间复杂度，注意数字可能是两位数或者三位数。 虽然oc了，但是代码十分不优雅。。。 看起来很碎。

class Solution {
public:
    string decodeString(string s) {
        // 用什么样的数据结构可以方便的完成字符串的解码呢？
        // 用一个递归的结构去一层一层的展开
        string res="";
        int n=s.size();
        for(int i=0;i<n;++i){
            if(s[i]>='a' && s[i]<='z'){
                res+=s[i];
            }
            else{
                res+=unfold(i,s,n);
                cout<<i<<endl;
            }
        }
        return res;
        
    }
    string unfold(int &i,string &s,int &n){
        // 将折叠的字符串展开 这个数字可能会有很多位
        int num=0;
        while(i<n){
            if(s[i]>='0'&&s[i]<='9'){
                num=num*10+(s[i]-'0');
            }
            else{
                break;
            }
            i++;
        }
        string tmp="";
        string res="";
        while(i<n){
            if(s[i]>='a' &&s[i]<='z'){
                tmp+=s[i];
            }
            else if(s[i]>='0'&&s[i]<='9'){
                tmp+=unfold(i,s,n);
            }
            else if(s[i]==']') break;
            i++;
        }
        for(int j=0;j<num;++j){
            res+=tmp;
        }
        return res;
    }
};

 思路二，利用两个堆栈进行处理。一个栈用来存储重复字符串个数 ，一个栈存储需要重复的字符串前缀。

class Solution {
public:
    string decodeString(string s) {
        string t = "";
        stack<int> s_num;
        stack<string> s_str;
        int cnt = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] >= '0' && s[i] <= '9') {
                cnt = 10 * cnt + s[i] - '0';
            } else if (s[i] == '[') {
                s_num.push(cnt);
                s_str.push(t);
                cnt = 0; t.clear();
            } else if (s[i] == ']') {
                int k = s_num.top(); s_num.pop();
                for (int j = 0; j < k; ++j) s_str.top() += t;
                t = s_str.top(); s_str.pop();
            } else {
                t += s[i];
            }
        }
        return s_str.empty() ? t : s_str.top();
    }
};