Codah ClubTrain. Submit. Improve.
Sign in
English
#00067C

ZAGRADE - COCI

Mirko was bored at his chemistry class, so he played Bomb Switcher on his cell phone. Unfortunately, he was spotted and was given a ridiculously heavy assignment for homework. For a given valid math expression with brackets, he must find all different expressions that can be obtained by removing valid pairs of brackets from the original expression. Two expressions are different if there is a character at which they differ.


For example, given (2+(2*2)+2), one can get (2+2*2+2), 2+(2*2)+2, and 2+2*2+2. (2+2*2)+2 and 2+(2*2+2) can't be reached, since we would have to remove pairs of brackets that are not valid. More than one pairs of brackets can surround the same part of the expression.



InputThe first and only line of input contains one valid mathematical expression composed of nonnegativeintegers, basic arithmetic operations denoted with characters '+', '*', '-' and '/', and brackets '(' and ')'.Given expression won‟t have more than 200 characters, and will have at least one, and no more than 10 pairs of brackets. Each expression is guaranteed to have at least one pair of brackets.


OutputOutput all different expressions that can be obtained by removing valid pairs of brackets, sorted lexicographically.



Input:
(0/(0))
Output:
(0/0)
0/(0)
0/0



Input:
(2+(2*2)+2)
Output:
(2+2*2+2)
2+(2*2)+2
2+2*2+2



Input:
(1+(2*(3+4)))
Output:
(1+(2*3+4))
(1+2*(3+4))
(1+2*3+4)
1+(2*(3+4))
1+(2*3+4)
1+2*(3+4)
1+2*3+4

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.