Remove Redundant Parentheses

Interview

Time limit1sMemory limit128 MB

Summary

Given valid arithmetic expressions over single uppercase variables with + and -, remove every matching parenthesis pair whose removal keeps the expression's value unchanged.

Level: Medium6 of 10
Topics: Stack, String, Implementation, Greedy
Solved: No attempts yet

Problem

You typed the report for your term project on your personal computer. The report contains several one-line arithmetic expressions. The original expressions have no redundant parentheses. A pair of matching parentheses is redundant if removing that single pair does not change the value of the expression.

While you were away, your younger sibling inserted some redundant pairs of matching parentheses into the expressions. Assume that afterwards each expression is still syntactically correct and still evaluates to its original value (the value before the parentheses were inserted).

Write a program that removes all redundant parentheses to restore each expression to its original form.

To keep things simple, assume the following:

The input contains several expressions, one per line.
Every variable in the expressions is a single uppercase letter.
The only operators are the binary '+' and the binary '-'.

The only transformation allowed is the omission of redundant parentheses; no algebraic simplification is allowed.

Input

The first line contains a single integer $M$ , the number of test cases ( $1 \le M \le 10$ ). Each of the next $M$ lines contains exactly one valid expression. A line may contain arbitrary space characters, and the length of each line (including spaces) is at most $255$ characters.

Output

For each test case, print the expression with all redundant parentheses removed, one per line. The order of the operands must be the same in the input and in the output. Remove every space character from the output expressions.

Examples8

Example 1

Input

3
(A-B + C) - (A+(B - C)) - (C-(D- E) )
  ((A)-( (B)))
A-(B+C)

Expected output

A-B+C-(A+B-C)-(C-(D-E))
A-B
A-(B+C)

Example 2
Input
```
1
A
```
Expected output
```
A
```
Example 3
Input
```
1
A+B-C
```
Expected output
```
A+B-C
```
Example 4
Input
```
1
(A+B-C)
```
Expected output
```
A+B-C
```
Example 5
Input
```
1
A-(B-C)
```
Expected output
```
A-(B-C)
```
Example 6
Input
```
1
A+(B-C)
```
Expected output
```
A+B-C
```
Example 7
Input
```
1
(((A)))
```
Expected output
```
A
```

Example 8

Input

2
  A -  ( B + C )  
X-(Y-(Z-W))

Expected output

A-(B+C)
X-(Y-(Z-W))