- An encoded string will be of the form <count>[encoded_string], where the 'encoded_string' inside the square brackets is being repeated exactly 'count' times. Note that 'count' is guaranteed to be a positive integer and can be greater than 9. - There are no extra white spaces and square brackets are well-formed.
Input: 2[a] “a” is encoded 2 times, hence the decoded string will be "aa". Input: 3[a2[b]] “b” is encoded 2 times, which decodes as 3[abb]. Now, "abb" is encoded 3 times, hence decoded string will be "abbabbabb".
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow. The only line of each test case contains a string 'S' which represents the encoded string.
For each test case, print a string i.e. the decoded string. Output for every test case will be printed in a separate line. Note: You are not required to print the expected output, it has already been taken care of. Just implement the function.
1 <= T <= 20 1 <= |S| <= 500 where |S| is the length of the Decoded string. Time limit: 0.400 sec
The idea is to maintain two Stacks. One will store the integers i.e. number of times the current string is repeated and the other one will store the strings itself.
We use a simple idea and always evaluate the innermost brackets first. We traverse through our encoded string