Infix to Postfix Expression Conversion

This problem requires you to convert an infix expression into its equivalent postfix (Reverse Polish) notation.

In an infix expression, operators are written in-between operands (e.g. 2 + 3), whereas in postfix notation the operator follows its operands (e.g. 2 3 +).

You are given an arithmetic expression which consists of integer operands and the operators +, -, *, and /. All tokens (operands, operators, and parentheses) are separated by spaces. Parentheses may alter the precedence of the operators. The standard operator precedence rules apply, i.e., multiplication and division have a precedence of 2 and addition and subtraction have a precedence of 1. In mathematical terms, if we denote the precedence of an operator \(\oplus\) as \(p(\oplus)\), then:

\[ p(+)=p(-)=1, \quad p(*)=p(/)=2 \]

Your task is to implement a conversion algorithm (commonly known as the Shunting-yard algorithm) to parse the input infix expression and output its postfix form. The output should maintain a single space between tokens.

inputFormat

The input consists of a single line from standard input (stdin) containing the infix expression. All tokens (operands, operators, and parentheses) are separated by spaces. For example: ( 3 + 5 ) * ( 2 - 8 ) / 4.

outputFormat

Output a single line to standard output (stdout) representing the postfix expression with tokens separated by a single space. For example: 3 5 + 2 8 - * 4 /.## sample

2 + 3

2 3 +