Problem 1: Postfix Evaluation, *(K Narayan Kumar, CMI)*

Consider arithmetic expressions built from the letters
`a`,…`z` using the operators `+` and
`-`. Here is an example:

((a+b)-(((c+d)-e)+a))

We will only consider such expressions, in which all brackets are
inserted explicitly. A fully bracketed expression can be translated
into a different form called *postfix*, using the following
simple rules:

- A variable remains as it is:
`Translate[x] = x`for any`x`in {a,…,z}. - An expression of the form
`(E`is translated as_{1}+E_{2})`Translate[E`._{1}] Translate[E_{2}] + - An expression of the form
`(E`is translated as_{1}-E_{2})`Translate[E`._{1}] Translate[E_{2}] -

For example, the expression above would be translated as follows:

Translate[((a+b)-(((c+d)-e)+a))] = Translate[(a+b)] Translate[(((c+d)-e)+a)] - = Translate[a] Translate[b] + Translate[((c+d)-e)] Translate[a] + - = a b + Translate[(c+d)] Translate[e] - a + - = a b + Translate[c] Translate[d] + e - a + - = a b + c d + e - a + -

Your task is to carry out the reverse of this operation. You will be given a valid expression in postfix--that is, one obtained by applying Translate to some well bracketed expression. You have to reconstruct the original expression from the postfix expression has been obtained by translation.

Input format

A single line containing a postfix expression involving `+`,
`-` and the letters `a,b,…,z`.

Output format

The fully bracketed expression that generates the input via the translation described above.

Test data

You may assume that the input expression has at most 80 symbols.

Example

Here is a sample input and output corresponding to the example discussed above.

Sample input

ab+cd+e-a+-

Sample output

((a+b)-(((c+d)-e)+a))

Copyright (c) IARCS 2003-2018; Last Updated: 08 Aug 2006