Infix to Postfix
- Create an empty stack called op_stack for keeping operators. Create an empty list for
output.
- onvert the input infix string to a list by using the string method split.
- Scan the token list from left to right.
- If the token is an operand, append it to the end of the output list.
- If the token is a left parenthesis, push it on the op_stack.
- If the token is a right parenthesis, pop the op_stack until the corresponding left
parenthesis is removed. Append each operator to the end of the output list.
- If the token is an operator, *, /, +, or −, push it on the op_stack. However, first
remove any operators already on the op_stack that have higher or equal precedence
and append them to the output list. (The left and right parenthesis will receive the lowest value possible. This way any
operator that is compared against it will have higher precedence and will be placed on top of it.)
-
When the input expression has been completely processed, check the op_stack. Any
operators still on the stack can be removed and appended to the end of the output list.
Stack processing
-
Create an empty stack called operand_stack.
- Convert the string to a list by using the string method split.
- Scan the token list from left to right.
- If the token is an operand, convert it from a string to an integer and push the value
onto the operand_stack.
- If the token is an operator, *, /, +, or −, it will need two operands. Pop the
operand_stack twice. The first pop is the second operand and the second pop is
the first operand. Perform the arithmetic operation. Push the result back on the
operand_stack.
- When the input expression has been completely processed, the result is on the stack. Pop
the operand_stack and return the value.
© Problem Solving with Algorithms and Data Structures