一道stack的題目

原題如下

Given an encoded string, return it’s 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].

Examples:

s = “3[a]2[bc]”, return “aaabcbc”.

s = “3[a2[c]]”, return “accaccacc”.

s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.

看到括号比對首先想到用棧來解決問題。

是以周遊字元串當發現‘[’時将目前i壓入棧，發現‘]’時，将棧頂彈出并處理。

其中要注意處理完後i的取值。

代碼如下：

string decodeString(string s) {
    stack<int>p;

    for(int i=;i<s.size();i++){
        if(s[i]=='[') p.push(i);
        if(s[i]==']'){
            int k=p.top();
            p.pop();
            string s1=s.substr(,k);
            string s2=s.substr(i+);
            string s3=s.substr(k+,i-k-);
            int num=;
            int total=;
            int len=s1.size()-;
            while(len>=&&s[len]<='9'&&s[len]>='0'){

                len--;
            }
            for(int j=len+;j<s1.size();j++){
                num*=;
                num+=s1[j]-'0';
            }
            if(len==-) s1="";
            else
            s1=s1.substr(,len+);
            s=s1;
            i=s1.length()+num*s3.length()-;
            while(num--) s+=s3;
            s+=s2;

         }
     }

        return s;
    }