A correct mathematical expression is given, consisting of variables denoted by lowercase Latin letters, infix binary operations, and parentheses for grouping subexpressions. All operations have associativity from left to right and priorities are shown in the table:
|
Priority |
Operations |
|
1 (largest) |
*, / |
|
2 |
+, - |
|
3 |
& |
|
4 |
^ |
|
5 (smallest) |
| |
It is required to remove from the expression all unnecessary pairs of brackets that do not affect the order of operations in it (operations should be interpreted abstractly, without any mathematical meaning, relying only on the formal order of operations). Priority determines the order in which operations are performed in a chain, and associativity determines the direction of evaluation in a chain of operations of the same priority.
|
Enter |
Output |
Remarks |
|
a+(b*c) |
a+b*c |
(‘*’ has a higher priority than ‘+’, so it is already executed first - the parentheses are superfluous); |
|
((a+b)+(c+d)) |
a+b+(c+d) |
(Parentheses around the entire expression are allowed, but never affect the order of evaluation inside. Since the associativity of all operations is left to right, the first inner brackets are redundant, and the second – are not, without them the expression would be equivalent to (((a+b)+c) +d)); |
|
((a)+b)&c^d |
a+b&c^d |
(parentheses around a variable are always superfluous). |
|
(((a)&b^c|((d)))) |
a&b^c|d |
|
|
a |
a |
|
Input file format:
One line containing the original mathematical expression no longer than 100 characters.
Output file format:
One line with a mathematical expression without extra brackets.