Infix to Postfix Expression Conversion

Given an arithmetic expression written in infix notation, your task is to convert it into postfix notation (also known as Reverse Polish Notation). You should implement the conversion using the Shunting-yard algorithm and follow the operator precedence rules given below:

• Operators: ^ (exponentiation), * (multiplication), / (division), + (addition), - (subtraction).
• The exponentiation operator ^ has the highest precedence and is right-associative.
• The multiplication and division operators have the next highest precedence and are left-associative.
• The addition and subtraction operators have the lowest precedence and are left-associative.
• Parentheses ( ) may be used to override these precedence rules.

For example, the infix expression A+B*(C^D-E)^(F+G*H)-I should convert to the postfix expression:

$$ABCD^E-FGH*+^*+I-$$

Implement your solution so that it reads from stdin and writes the result to stdout.

inputFormat

The input consists of a single line containing a valid infix expression composed of uppercase alphabetic characters (operands) and the operators +, -, *, /, ^, and parentheses ( ).

Input is provided via standard input (stdin).

outputFormat

Output the corresponding postfix expression as a single line. The result must be written to standard output (stdout).

A+B*(C^D-E)^(F+G*H)-I

ABCD^E-FGH*+^*+I-