234. Decode String

Given an encoded string with the rule k[encoded_string] meaning the inner string repeated k times (k is a positive integer), return the decoded string. Encodings may be nested.

Input: A quoted encoded string.

Output: Quoted string — the decoded result.

Examples

Input: "3[a]"
Output: "aaa"
Explanation: 'a' repeated 3 times.

Input: "3[a2[c]]"
Output: "accaccacc"
Explanation: Nested decoding.

Input: "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Explanation: Sequential blocks.

Constraints

• 1<=s.length<=100
• 1<=k<=300

Asked by