Author:  NEERC 2005  Time limit:  2 sec  
Input file:  brackets.in  Memory limit:  64 Mb  
Output file:  brackets.out 
Let us consider arithmetic expressions that consist of variables denoted by lowercase letters "a" to "z"; four binary arithmetic operations: addition ("+"), subtraction (" − "), multiplication ("*"), and division ("/"); opening ("(") and closing (")") round brackets. The normal order of precedence is used multiplication and division have the highest precedence, addition and subtraction have the lowest precedence. Operations of the same precedence are evaluated from left to right (for example a − b + c = (a − b) + c).
Thus, the grammar for the expressions is the following:
expression  →  term  expression + term  expression − term 
term  →  factor  term * factor  term / factor 
factor  →  variable  (expression) 
variable  →  a  b  ...  z 
Your task is to rewrite the given expression so that its semantics is not changed, but the resulting expression has the minimal number of round brackets.
You can remove any excessive brackets that do not change the order of evaluation, for example
(a + b) + (c)  ⇒  a + b + c, 
(a * b) / (c)  ⇒  a * b / c, 
You can think about these transformations as ones that only use "+" and "*" associativity, the fact that "" is the reverse operation to "+", "/" is the reverse operation to "*", and nothing else. You can apply the described transformations and remove excessive brackets as many times as you need to get the expression with the minimal number of round brackets.
No.  Input file (brackets.in ) 
Output file (brackets.out ) 

1 

