SPOJ.com - Problem CW

CW_2 - COMPRESSED WORDS-2

#text-processing

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
(e₁ e₂ ... e_t n) where t and n are non-negative integers and e_i 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 (e₁ e₂ ... e_t n) we uncompress each e_i, 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

Submit solution!

hide comments

< Previous 1 2 Next >

	Bhavik: 2014-04-08 20:42:44 @mitch: thank you for understanding my concerns. ok i got your point,i will certainly look into improving constraints for this problem with right problem statement also:) i have no problems with the question moved to tutorial or to remain in classical...i just want question to be good enough that people enjoy solving it:) i will update the dataset when i am ready with better testcases
	Mitch Schwartz: 2014-04-08 20:31:25 @Bhavik: Ok, I understand that your somewhat harsh assessment of CW problem setter is more because of his unresponsiveness than because of the issues with the problem itself. I do thank you for being very responsive and understanding. It can be moved back to classical, but I would like to see it improved first, and we can discuss. The idea behind making 0.00s hard or impossible is that some solvers are very interested in speed optimisation and would like to compare their speeds against other solvers. If all the fastest ones got 0.00s then there is no way to compare in fine detail. This problem could be hard for some approaches or languages, but in general it's not a hard problem. So allowing speed comparisons like that makes it more interesting, and more suitable for classical. Edit: Thanks for your understanding. :) Last edit: 2014-04-08 21:15:49
	Bhavik: 2014-04-08 20:16:10 and for time limit i am not in the favour of building huge datasets just for not allowing 0.00s solution to exist. A bad complexity solution will not pass with given time limit either way and tricky cases were already included in dataset..so it was only logic that i was looking for
	Bhavik: 2014-04-08 20:11:32 @Mitch: i agree that i am wrong on that part since i just copied the wordings from CW...so i should have been careful with that...but as i said i am ready to accept my mistakes and rectify it for both as psetter and for users and as you mentioned my mistakes earlier i tried to rectify as soon as possible...so kindly don't misinterpret my previous comments ,i have no intentions of proving others /myself wrong or right!! Last edit: 2014-04-08 20:27:52
	Mitch Schwartz: 2014-04-08 20:10:20 Regarding 0.00s: It is possible to e.g. increase size of test data and also increase time limit (so that slower solutions can still pass). I'm not sure how slow the solutions are that you wanted to allow, but a difference in >= 200x (the 1s time limit vs my 0.00s, should be at most 0.005s in order to get rounded that way) seems a lot to me.
	Mitch Schwartz: 2014-04-08 20:02:03 If you can't see that "(a)" is not a valid compressed word according to the definition, I think you should be most concerned about that. Wording in the description is a bit sloppy. It's not a big deal. You switch from "shortened word" to "compressed word", and a correct wording of point (2) is (there are several ways): "(e1 e2 ... et n) is a compressed word, where t and n are non-negative integers and ei is a compressed word for all 1<=i<=t." So you can think about building the language from those two rules. There is no way to get "(a)" from those two rules... It does not make sense to define compressed words and then allow "regular expressons" in input that are not compressed words. For example, "(1 e 5 a)" is also a valid regular expression that doesn't contain any illegal characters; should we expect that in input? Last edit: 2014-04-08 20:33:00
	Bhavik: 2014-04-08 19:43:04 @MITCH: i dont where i am wrong...i am giving attention to the problems that users are having with this question by clearing their doubts or vive-versa if you think it is tutorial just because it was solvable in 0.00(as i interpreted) you did and i am not arguing about that i think you have misinterpreted about what i commented earlier in CW i am simply not putting questions and going into oblivion that the psetter in CW did..that was my point in that case though i will look into your suggestions for future problems:) Last edit: 2014-04-08 19:53:11
	Mitch Schwartz: 2014-04-08 19:37:12 From CW: "though it truly deserves to be in classical,but due to the ignorance of psetter all the efforts of users trying to do this is wasted:( i think spoj administrators should take away problem making rights from such people who don't care to make right problems or if psetter have some time issues they should atleast say so that we can look for problem after some time again.. " You should have higher standards for yourself if you make a comment like that. Please re-read my suggestions and reconsider your position on this problem.
	Mitch Schwartz: 2014-04-08 19:28:58 Moved to tutorial.
	Mitch Schwartz: 2014-04-08 19:19:37 There is a definition of shortened/compressed word at the beginning of problem description. "(a)" is not in the language defined there. Adding mention of "regular expressions" does not fix this error. I got AC with a workaround, but this should be fixed. Furthermore, it should be harder to get 0.00s. This was mentioned by Francky in CW. REPLY: i know 0.00s makes it look easy but i think it will be only in cases where predefined fucntions or STL library are available(C++,java,python etc).If i disallow these languages then it will be not fair for those users without STL it would be difficult and certainly not 0.00s though i am not against STL Last edit: 2014-04-08 19:29:50

Submit solution!

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