Reverse Polish Notation (RPN) to Infix Conversion

Given an expression in Reverse Polish Notation (RPN), convert it to its equivalent infix notation with full parentheses to maintain the order of operations. In RPN, every operator follows all of its operands. The algorithm involves reading tokens from the input, using a stack to store operands, and whenever an operator is encountered, popping the top two items from the stack, combining them with the operator inside parentheses, and then pushing the resulting expression back onto the stack.

For example, the RPN expression "3 4 +" should be converted to "(3 + 4)" and "5 1 2 + 4 * + 3 -" should be converted to "((5 + ((1 + 2) * 4)) - 3)".

The operators used can be +, -, *, and /. All binary operations must be enclosed in parentheses. In mathematical notation, you might see the addition operator represented as \( + \) and similarly for the others.

inputFormat

The input consists of a single line containing a valid RPN expression. The tokens (operands and operators) in the expression are separated by spaces.

Example:

5 1 2 + 4 * + 3 -

outputFormat

The output is the corresponding infix expression with full parentheses. There should be no extra spaces or newline characters in the output.

Example:

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

## sample

3 4 +

(3 + 4)