OpenKattis
University of Bergen

# Reverse Polish to Infix Notation (Hard)

The following is an example of an expression written in reverse polish notation:

$\texttt{1 3 + 2 4 5 - + /}$

It is a postfix notation, and is computer friendly when it comes to calculating the answer; however, this notation is hard to read for the human eye. Implement a program which takes an arbitrary reverse polish expression and converts it to a fully bracketed expression in infix notation. In the above example, the output would be:

$\texttt{((1+3)/(2+(4-5)))}$

## Input

The first and only line contains a sequence of tokens separated by single whitespaces. A token may be either a non-negative $32$-bit integer or one of the operators $\texttt{\{ +, -, *, /\} }$. The line will contain at most $200\, 000$ tokens. The tokens form a valid reverse polish expression.

## Output

Output a single line with the infix notation.

Sample Input 1 Sample Output 1
1 3 + 2 4 5 - + /

((1+3)/(2+(4-5)))

Sample Input 2 Sample Output 2
100 30 20 + 2 * -

(100-((30+20)*2))