Infix expression: The expression is of the form A op B, where an operator is in-between a pair of operands. ex: A+B*C+D
Postfix expression: The expression is of the form A B op, where an operator is followed for a pair of operands. ex: ABC*+D+
Please design an algorithm to transform the input infix expression string into a postfix expression string.
Operators: ^ * / + - ( )
Operands: 'a' ~ 'z'
Hint:
1. Priority of Operators: ^ > * / > + -
2. The order of operands does not change between infix and postfix.
3. Use stack to store the visited operators and pop them out at the proper sequence. (When the priority of the operator on top of stack is higher or equal to that of the incoming operator)
4. '(' has the highest priority, always push to stack. Once pushed, ‘(’ get the lowest priority.
5. ‘)’ has the lowest priority, therefore pop the operators in the stack until you see the matched ‘(’, then eliminate both.
6. Assume that all input infix expression shall be legal. No need to detect illegality.
A legal infix expresseion string.
A legal postfix expression string. (left-to-right associativity)