Infix to Postfix Expression Conversion

In our usual mathematical expressions, we write in infix notation where the operator is placed between two operands. To remove ambiguity in the evaluation order, parentheses are used. On the other hand, postfix notation (or Reverse Polish Notation) places the operator immediately after its two operands, removing the need for parentheses while inherently encoding the order of operations.

For example, the infix expression: 8-(3+2*6)/5+4 can be converted to the postfix expression: 8 3 2 6 * + 5 / - 4 + following these steps:

8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9

Your task is to write a program that converts a given infix expression (which is well-formed) to its equivalent postfix notation. Ensure that every token in the output is separated by a single space.

inputFormat

The input consists of a single line containing a valid infix expression. The expression may contain multi-digit numbers, the operators +, -, *, /, and parentheses ( and ). There are no spaces in the input expression.

outputFormat

Output the corresponding postfix expression with each token (number or operator) separated by a single space.

sample

8-(3+2*6)/5+4

8 3 2 6 * + 5 / - 4 +