Complicated Expressions

Time limit1sMemory limit128 MB

Summary

Parse an arithmetic expression with parentheses and reprint it with every redundant parenthesis removed while preserving exact operator precedence and associativity semantics.

Level: Medium7 of 10
Topics: String, Recursion, Implementation
Solved: No attempts yet

Problem

ACM is a mobile phone operator running a GSM network, so it must build its own transmitting stations, and computing the exact behaviour of electro-magnetic waves is very important. Unfortunately, predicting electro-magnetic fields is a very complex task, and the formulas that describe them are long and hard to read. For example, below are Maxwell's Equations, which describe the basic laws of electrical engineering.

\nabla \times \vec{\mathbf{B}} = 0 \\ \nabla \cdot \vec{\mathbf{E}} = \frac{\rho}{\varepsilon_0} \\ \nabla \times \vec{\mathbf{H}} = \vec{\mathbf{j}} + \frac{\partial \vec{\mathbf{D}}}{\partial t} \\ \nabla \times \vec{\mathbf{E}} = -\frac{\partial \vec{\mathbf{B}}}{\partial t}

ACM has designed its own computer system that can perform such field computations and produce the results as mathematical expressions. Unfortunately, because an expression is generated in several steps, the result always contains some unnecessary parentheses. Your task is to take these partial results and make them "nice" by removing every unnecessary parenthesis without changing the meaning of the expression.

Input

The first line contains a single positive integer $T$ , the number of expressions that follow. Each expression is given on a single line and consists only of lowercase letters, the operators (+, -, *, /), and parentheses (( and )). The letters are variables that may take any value; the operators and parentheses have their usual meaning. Multiplication and division have higher priority than addition and subtraction. Operations of the same priority are evaluated from left to right (that is, the operators are left-associative). There are no spaces inside the expressions. No input line contains more than 250 characters.

Output

For every expression print a single line. The line must contain the same expression with the unnecessary parentheses removed. You must remove as many parentheses as possible without changing the meaning of the expression. Two expressions are considered to have the same meaning if and only if one of the following holds:

The ordering of the operations stays the same. That is, (a+b)+c is the same as a+b+c, and a+(b/c) is the same as a+b/c.
The order of some operations is swapped but the result is unchanged under the associativity of addition and multiplication. That is, a+(b+c) and (a+b)+c are the same. You may also combine addition with subtraction, and multiplication with division, when the subtraction or division is the second operation. For example, a+(b-c) is the same as a+b-c.

You cannot use any other law. In particular, you cannot swap the left and right operands, and you cannot rewrite a-(b-c) as a-b+c.

Examples2

Example 1

Input

8
(a+(b*c))
((a+b)*c)
(a*(b*c))
(a*(b/c)*d)
((a/(b/c))/d)
((x))
(a+b)-(c-d)-(e/f)
(a+b)+(c-d)-(e+f)

Expected output

a+b*c
(a+b)*c
a*b*c
a*b/c*d
a/(b/c)/d
x
a+b-(c-d)-e/f
a+b+c-d-(e+f)

Example 2

Input

3
a-(b-c)
a/(b/c)
a+(b+c)

Expected output

a-(b-c)
a/(b/c)
a+b+c