Infix to Postfix Expression Conversion

You are given an arithmetic expression in infix notation that contains single-letter operands (such as a, b, etc.) and operators +, -, *, / and ^. Your task is to convert the given expression to its corresponding postfix notation (also known as Reverse Polish Notation). The conversion should take into account operator precedence and associativity.

The operator precedence is defined as follows:

• Lowest: + and - (i.e., precedence = 1)
• Medium: * and / (i.e., precedence = 2)
• Highest: ^ (i.e., precedence = 3)

Note that the exponentiation operator ^ is right-associative while the other operators are left-associative. Parentheses ( ) can be used to override the usual precedence rules.

Example:

• a + b should be converted to a b +.
• (a + b) * c should be converted to a b + c *.

inputFormat

The input consists of a single line containing an infix expression. The expression contains only single-letter operands, the operators +, -, *, /, ^, and parentheses. There may be spaces in the expression which should be ignored.

outputFormat

Output the corresponding postfix expression. The tokens in the output should be separated by a single space.

a + b

a b +