CMEXPR  Complicated Expressions
The most important activity of ACM is the GSM network. As the mobile phone operator, ACM must build its own transmitting stations. It is very important to compute the exact behaviour of electromagnetic waves. Unfortunately, prediction of electromagnetic fields is a very complex task and the formulas describing them are very long and hardtoread. For example, Maxwell's Equations describing the basic laws of electrical engineering are really tough.
ACM has designed its own computer system that can make some field computations and produce results in the form of mathematic expressions. Unfortunately, by generating the expression in several steps, there are always some unneeded parentheses inside the expression. Your task is to take these partial results and make them "nice" by removing all unnecessary parentheses.
Input
There is a single positive integer T on the first line of input (equal to about 10000). It stands for the number of expressions to follow. Each expression consists of a single line containing only lowercase letters, operators (+, , *, /) and parentheses (( and )). The letters are variables that can have any value, operators and parentheses have their usual meaning. Multiplication and division have higher priority then subtraction and addition. All operations with the same priority are computed from left to right (operators are leftassociative). There are no spaces inside the expressions. No input line contains more than 250 characters.
Output
Print a single line for every expression. The line must contain the same expression with unneeded parentheses removed. You must remove as many parentheses as possible without changing the semantics of the expression. The semantics of the expression is considered the same if and only if any of the following conditions hold:
 The ordering of operations remains the same. That means "(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 remains unchanged with respect to the addition and multiplication associativity. That means "a+(b+c)" and "(a+b)+c" are the same. We can also combine addition with subtraction and multiplication with division, if the subtraction or division is the second operation. For example, "a+(bc)" is the same as "a+bc".
You cannot use any other laws, namely you cannot swap left and right operands and you cannot replace "a(bc)" with "ab+c".
Example
Sample Input:
8 (a+(b*c)) ((a+b)*c) (a*(b*c)) (a*(b/c)*d) ((a/(b/c))/d) ((x)) (a+b)(cd)(e/f) (a+b)+(cd)(e+f)
Sample Output:
a+b*c (a+b)*c a*b*c a*b/c*d a/(b/c)/d x a+b(cd)e/f a+b+cd(e+f)
hide comments
sohit5012:
20190513 14:27:19
Consider using Postfix notation.


j_b_b_j:
20190510 16:57:17
cases that helped me find mistakes:


revo:
20190424 21:10:55
I used Expression tree along with modified traversal. Just a pointer to people who might want to solve this going forward and need a starting point. 

skandgupta:
20180630 19:40:24
the question is so confusing


alan_20210202:
20180604 13:56:46
Transforming the expression into an AST and print it recursively should be a pretty straightforward idea.


Antonio Roberto Paoli:
20180115 06:19:19
This test case caused me a WA.


quock:
20170428 05:26:39
Getting stuck in solve this problem . What guys do you prefer to solve I means "stack" or other way ?


imshubhamk:
20160730 20:22:09
pls anyone tell does unary operators are allowed or not???????


etgd:
20160420 12:49:07
Is there complete list of testing cases? Despite all my efforts and checks i have *wrong answer*. 

fallingstar:
20151022 10:56:28
@Rahul Anshietty you are bound to only remove brackets without changing the result of the expression. a/(b/c)/d <> a/b/c/d (you can try by replacing a,b,c,d with numbers)

Added by:  adrian 
Date:  20040509 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  ACM Central European Programming Contest, Prague 2000 