This process uses a stack as well. We have to hold information that’s expressed inside parentheses while scanning to find the closing ‘)’. We also have to hold information on operations that are of lower precedence on the stack.
The algorithm is:
1. Create an empty stack and an empty postfix output string/stream
2. Scan the infix input string/stream left to right
3. If the current input token is an operand, simply append it to the output string (note the examples above that the operands remain in the same order)
4. If the current input token is an operator, pop off all operators that have equal or higher precedence and append them to the output string; push the operator onto the stack. The order of popping is the order in the output.
5. If the current input token is ‘(‘, push it onto the stack
6. If the current input token is ‘)’, pop off all operators and append them to the output string until a ‘(‘ is popped; discard the ‘(‘. 7. If the end of the input string is found, pop all operators and append them to the output string. This algorithm doesn’t handle errors in the input, although careful analysis of parenthesis or lack of parenthesis could point to such error determination.
