394. Decode String

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

Examples:

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

解题要点：

血汗的教训啊！这题如果忽略左口号，会很难办。所以，先把所有左括号前的字母加到res里，这时如果碰到右括号，就开始提取数字stack对字母stack和res进行计算，算完后继续放养，直到遇到下一个左括号，再把res里的字母加到字母stack里。这样可以保证格式一定工整，不会混淆左右括号的层次。

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        res = ""
        stNum = []
        stChar = []
        i = 0
        while i < len(s):
            if s[i].isdigit():
                num = int(s[i])
                while i+1 < len(s) and s[i+1].isdigit():
                    num = num * 10 + int(s[i+1])
                    i+=1
                stNum.append(num)
            elif s[i] == '[':
                stChar.append(res)
                res = ""
            elif s[i] == ']':
                tempNum = stNum.pop()
                tempChar = stChar.pop()

                while tempNum > 0:
                    tempChar += str(res)
                    tempNum -= 1
                res = tempChar
            else:
                res += str(s[i])
                
            i+=1
        return res