LeetCode:394. Decode String

https://leetcode.com/problems/decode-string/description/

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".

如果对数据结构队列和栈，波兰式、逆波兰式，这道题就不难了。当然，也可以用递归写。
思路：1、如果遇到的是数字，就放入栈中，这里用‘-’字符代表一个数，因为数字可能大于9，把具体的数字保存在
另外一个栈中了。
2、当遇到是右括号的时候，把栈顶所有字符元素str出栈，还有数字N也出栈，然后N倍的str 又压入栈中。
3、最后栈中的元素就是结果了。注意下顺序。

class Solution 
{
    public:
        string decodeString(string s)
        {
            string retstr;          
            if(0==s.length())
                return retstr;
            string sub_str;
            stack<char> all;
            stack<int>  stack_cnt;
            int curPos = 0;
            char curCh = 0;
            int cnt = 0;
            while( curPos<s.length())
            {
                curCh = s[curPos];
                if( isalpha(curCh) )
                {
                    all.push(curCh);
                }
                else if( isdigit(curCh))
                {
                    sub_str = s.substr(curPos);
                    cnt = atoi(sub_str.c_str());
                    all.push('-');
                    stack_cnt.push(cnt);
                    while(curPos<s.length() && s[curPos]!='[')
                        ++curPos;
                }
                else if(curCh==']')
                {
                    string str;
                    int cnt = 0;
                    char ch = 0;
                    while(!all.empty())
                    {
                        ch = all.top();
                        all.pop();
                        if(ch=='-')
                            break;
                        str.push_back(ch);
                    }               
                    cnt = stack_cnt.top();
                    stack_cnt.pop();
                    for(int i=0; i<cnt; ++i)
                    {
                        for(int j=str.length()-1; j>=0; --j)
                            all.push(str[j]);
                    }
                }
                ++curPos;
            }

            stack<char> tmpstack;
            while(!all.empty())
            {
                curCh = all.top();
                all.pop();
                tmpstack.push(curCh);
            }
            while(!tmpstack.empty())
            {
                curCh = tmpstack.top();
                tmpstack.pop();
                retstr.push_back(curCh);
            }
            return retstr; 
        }
};