# Question

Formatted question description: https://leetcode.ca/all/394.html

 394	Decode String

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.

Examples:

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

@tag-stack


# Algorithm

Questions:

1. nested allowed? yes, 3[a2[c]]
2. count could be overflowed

Use stack to assist calculation, we use two stacks,

• One is used to store the number,
• One to save the string,

Traverse the input string,

• If we encounter a number, we update the count variable cnt;
• If you encounter a left parenthesis, we push the current cnt into the number stack, and push the current t into the string stack;
• If we encounter the right parenthesis, we take out the top element in the number stack and store it in the variable k, then add k t strings to the top element of the string stack, and then take the top element and store it in the string t;
• If we encounter a letter, we directly add it to the string t

Java