Solution Review: Infix-to-Postfix Conversion

Solution

• We print operands in the same order as they arrive.
• If the stack is empty or contains a left parenthesis ( on top, we push the incoming operator in the stack.
• If the incoming symbol is a left parenthesis (, we push the left parenthesis to the stack.
• If the incoming symbol is a right parenthesis ), we pop that from the stack and print the operators until we see a left parenthesis (. We’ll discard the pair of parentheses.
• If the precedence of the incoming symbol is higher than the precedence of an operator at the top of the stack, then we push it to the stack.
• If the incoming symbol has equal precedence compared to the top of the stack, we use association. If the association is left to right, we pop and print the symbol at the top of the stack and then push the incoming operator. If the association is right to leave, we push the incoming operator.
• If the precedence of the incoming symbol is lower than the precedence of the operator on the top of the stack, we pop and print the top operator. Then we compare the incoming operator against the new operator at the top of the stack.
• Finally, we pop and print all operators on the stack.