Infix, Prefix and Postfix Expressions:
Examples:
Infix Expression |
Prefix Expression |
Postfix Expression |
---|---|---|
A + B | + A B | A B + |
A + B * C | + A * B C | A B C * + |
(A + B) * C | * + A B C | A B + C * |
A + B * C + D | + + A * B C D | A B C * + D + |
(A + B) * (C + D) | * + A B + C D | A B + C D + * |
A * B + C * D | + * A B * C D | A B * C D * + |
A + B + C + D | + + + A B C D | A B + C + D + |
Algorithm for converting an expression from infix to postfix:
- Create an empty stack called myStack for keeping operators. Create an empty list for output.
- Convert 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 myStack.
- If the token is a right parenthesis, pop the myStack 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 myStack. However, first remove any operators already on the myStack that have higher or equal precedence and append them to the output list.
- When the input expression has been completely processed, check the myStack. Any operators still on the stack can be removed and appended to the end of the output list.