BRACKETS - Fully Parenthesized Expression

Clyde has written a program that can evaluate arithmetic expressions. There is just one problem - the expressions must be fully parenthesized!

Help Clyde by making sure all of his expressions are fully parenthesized - he's willing to reward you.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 1000) that indicates the amount of test cases.
On the next n lines will be a string s representing the expression. S will always contain a valid expression and will be strictly less than 256 characters in length.

The operators used in s are */% of high precedence and +- of low precedence. All operators are binary. All input strings will consist of only characters in the set "0123456789+-*/%()" (no whitespace).

Output

Your program should output n lines, each containing the fully parenthesized expression s.

A fully parenthesized expression is one where each operator is one where all operands are surrounded by either one parenthesis and one operator, or two parentheses. There should not be any extra parentheses.

The outputted expression does not need to be a solvable expression.

Fully Parenthesized Not Fully Parenthesized
(42) 42
(1+(2*3)) 1+(2*3)
(1+((61%(3+6))*7)) 1+61%(3+6)*7

Example

Input
6
42
1+2*3
1%6*2
2/0
(1+((61%(3+6))*7))
(((((1)))))

Output
(42)
(1+(2*3))
((1%6)*2)
(2/0)
(1+((61%(3+6))*7))
(1)

Score

Your score is the length of your source code.


Added by:Jargon
Date:2010-05-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6
Resource:Own problem

hide comments
2013-05-17 21:42:26 Mitch Schwartz
The real top score is 109 106 in Perl by Jander at http://www.spoj.com/SHORTEN/ranks/BRACKETS/ .

Last edit: 2013-08-26 09:21:36
2012-09-09 18:21:48 (Tjandra Satria Gunawan)(曾毅昆)
finally 533B :-) from 1246B (my first submission) compressed into 533B, compression ratio: 57,2%
need ~3 hours to shorten my C code... Most user solve this problem using python, not C..
2012-09-09 18:57:13 Piotr KÄ…kol
198 is not the shortest code. ;-) The shortest is for now 133 in Ruby. ;-)
// Edit: Now 115 in Ruby. :-)


Last edit: 2011-01-06 16:02:39
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.