Removing Parentheses

Interview

Time limit1sMemory limit128 MB

Summary
Given an expression of single-letter variables with addition and multiplication, remove every pair of parentheses that can go without changing the value, and print the result.
Level

Medium6 of 10

Topics
Stack, String, Implementation, Recursion
Solved
No attempts yet

Problem

The two expressions (((x)+(y))(t)) and (x+y)t are equal. Given an expression, write a program that removes as many parentheses as possible without changing its value and prints the result.

An expression consists only of additions and multiplications, and every variable is a single lowercase letter. An expression is defined by the following grammar.

E : P | P '+' E
P : F | F P
F : V | '(' E ')'
V : 'a' | 'b' | ... | 'z'

Associativity may be used for both addition and multiplication: x+(y+z) = (x+y)+z = x+y+z and x(yz) = (xy)z = xyz. However, commutativity and distributivity may NOT be used. Parentheses have the highest precedence, followed by multiplication, and then addition.

Input

The input consists of several test cases. Each test case is one expression that satisfies the grammar above, given on its own line. Each expression has length at most 1000. The input continues until end of file (EOF).

Output

For each test case, print the expression obtained by removing as many parentheses as possible while preserving its value, one per line.

Examples2

  1. Example 1

    Input
    x
(x+(y+z))
(x+(yz))
(x+y(x+t))
x+y+xt
    Expected output
    x
x+y+z
x+yz
x+y(x+t)
x+y+xt

  2. Example 2

    Input
    a
    Expected output
    a