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