Indian National Olympiad in Informatics

Related:

Online Programming Contest, 10-11 June 2006

IARCS home > OLYMPIAD

Basic Division

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₁+E₂) is translated as Translate[E₁] Translate[E₂] +.
An expression of the form (E₁-E₂) is translated as Translate[E₁] Translate[E₂] -.

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))