CW_2 - COMPRESSED WORDS-2
Helen has come up with a way to shorten the length of the messages send to their counterparts in the past. Helen considers only individual words, and uses the following rules to define a "shortened word":
- a single, lower-case letter is a compressed word
- (e1 e2 ... et n) where t and n are non-negative integers and ei is a compressed word.
You should observe that a compressed word of one character is the same as an uncompressed word. To uncompress the compressed word (e1 e2 ... et n) we uncompress each ei, concatenate those uncompressed words into a new word, and repeatedly concatenate that word n times. For example:
- a would be uncompressed as a,
- (a 3) would be uncompressed as aaa,
- (a (b c d 2) 3) would be uncompressed as abcdbcdabcdbcdabcdbcd.
Write a program to uncompress a compressed word.
Input
First line T, the number of test cases (=12). Next T lines contain correctly formed compressed words.
Output
For each case print in a new line the uncompressed word without spaces.
Constraints
0 < n <= 10000, 1 <= t <= 26
length of expressions will be less than 100, and the compressed worf will consist of latters (a-z), numbers and brackets.
Note: There may or may not be more than one space between brackets and letters or number. For example ( a ), (a3), ( a 3 ) are all correct expressions.
Example
Input: 3 a ( a 3 ) ( a ( b c d 2 ) 3 ) Output: a aaa abcdbcdabcdbcdabcdbcd
hide comments
Francky:
2014-04-08 19:07:27
What are the constraints on e_i : it is said non-negative integers, but what are the full constraints ?
|
|
Mitch Schwartz:
2014-04-08 19:07:03
"for eg ( a ),(a3),( a 3 ) are all correct expressions"
|
|
Bhavik:
2014-04-08 19:07:03
i had the problem of internal error with CW2 which i could not resolve before i created this one...so i put up this one rather than CW2...though i rectified it later
|
|
Mitch Schwartz:
2014-04-08 19:07:03
It's not a big deal here, but in general it's best to write constraints such that any valid test case is solvable. E.g. you could write a constraint on output size to make clear that cases like (...(a 9) 9) 9)...) [as long as possible] aren't included. |
|
Francky:
2014-04-08 19:07:03
Please explain the troubles with CW2, it will be appreciate. |
Added by: | Bhavik |
Date: | 2014-04-08 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | CW |