What is an Infix Expression?
An Infix Expression (or Infix Notation) is characterized by a math expression wherein the operators are placed between operands, (as in 2 + 3).
In the case of infix expressions, parentheses (or brackets) must be used to indicate the order in which the author wants the operations to be executed. Otherwise, the person solving the problem is left to apply an order of operation convention (PEMDAS, BODMAS, etc.) to solve the expression.
What is a Postfix Expression?
As the name implies, a Postfix Expression (or Postfix Notation, or Reverse Polish Notation) is characterized by a math expression wherein the operators are placed after their operands (2 + 3 infix becomes 2 3 + postfix).
Since each postfix operator is evaluated from left to right, this eliminates the need for parenthesis. This is why postfix expressions are easier for computer algorithms to evaluate than infix expressions.
How to Convert Infix to Postfix Using Stack
In case you're not familiar, a stack is a collection or list wherein the last element added to the stack is always the first element to be removed.
Using a stack to temporarily store operators is necessary because as we are evaluating each operator token of the infix expression from left to right, we can't instantly know an operator's right-hand operand. Therefore we need to temporarily add (push) an operator to the stack and only remove (pop) it from the stack and append it to postfix expression once we know its right operand.
So now that you know what a stack is and why it is used, the next order of business is to assign precedence and associativity to each operator type based on an order of operations convention (PEMDAS or BODMAS). The only exception is, in the stack method parentheses don't have precedence because they don't exist in a postfix expression. Instead, parentheses are used to isolate parts of the infix notation that are to be executed independently of the operators outside of them. Any nested parentheses are evaluated prior to evaluating their encompassing parentheses.
| Operator | Symbol | Precedence | Associativity |
|---|---|---|---|
| Exponent | ^ | 4 | Right to Left |
| Multiplication | * | 3 | Left to Right |
| Division | / | 3 | Left to Right |
| Addition | + | 2 | Left to Right |
| Subtraction | - | 2 | Left to Right |
Now that you know what a stack is and have assigned precedence and associativity to each operator, the following are the steps to converting infix to postfix using stack.
Working from left to right, one token at a time, determine whether or not the current token is an operand, an operator, or an opening or closing parenthesis.
If the token is an operand, append it to the postfix expression. Operands always appear in the same order in the postfix expression as they do in the infix expression.
If the token is an opening parenthesis, push it to the stack. This marks the beginning of an expression that should be evaluated separately.
If the token is a closing parenthesis, until an opening parenthesis is encountered at the top of the stack, pop each operator from the stack and append to the postfix expression. This marks the end of the operands and operators located within the current set of parentheses.
If the token is an operator and it has greater precedence than the operator on the top of the stack, push the token to the stack.
If the token is an operator and it has lower precedence than the operator on the top of the stack, until the operator on top of the stack has lower precedence than the token, or until the stack is empty, pop each operator from the stack and append them to the postfix expression. Then push the current token to the stack.
If the token is an operator and it has the same precedence as the operator on the top of the stack, and the operator on top of the stack is left-to-right associative, until the operator on top of the stack has lower precedence than the token, or until the stack is empty, pop each operator from the stack and append them to the postfix expression. Then push the current token to the stack.
If the token is an operator and it has the same precedence as the operator on the top of the stack, but the operator on top of the stack is right-to-left associative, push the current token to the stack.
Finally, once all of the infix tokens have been evaluated, pop any remaining operators from the stack, one at a time, and append each of them to the postfix expression.
Infix to Postfix Conversion Examples
Since the step-by-step infix to postfix examples are quite long, I will first provide a simple example without any parentheses, and then provide a more complex example that includes parentheses and a case of right-to-left associativity. Both examples were generated by the infix to postfix calculator on this page.
Example #1: 6*4+2^5-3
Token #1 Evaluation
Infix: 6*4+2^5-3
Since 6 is an operand, append it to the postfix expression.
Postfix: 6
Stack:
Token #2 Evaluation
Infix: 6*4+2^5-3
Since the * is an operator and the stack is empty, push the * to the stack.
Postfix: 6
Stack:
| * |
Token #3 Evaluation
Infix: 6*4+2^5-3
Since 4 is an operand, append it to the postfix expression.
Postfix: 6 4
Stack:
| * |
Token #4 Evaluation
Infix: 6*4+2^5-3
Since + is an operator and has lower precedence than the * on the top of the stack, pop * from the stack and append it to the postfix expression.
Postfix: 6 4 *
Stack:
Push the + to the stack.
Postfix: 6 4 *
Stack:
| + |
Token #5 Evaluation
Infix: 6*4+2^5-3
Since 2 is an operand, append it to the postfix expression.
Postfix: 6 4 * 2
Stack:
| + |
Token #6 Evaluation
Infix: 6*4+2^5-3
Since ^ is an operator and has greater precedence than the + on the top of the stack, push ^ to the top of the stack.
Postfix: 6 4 * 2
Stack:
| ^ + |
Token #7 Evaluation
Infix: 6*4+2^5-3
Since 5 is an operand, append it to the postfix expression.
Postfix: 6 4 * 2 5
Stack:
| ^ + |
Token #8 Evaluation
Infix: 6*4+2^5-3
Since - is an operator and has lower precedence than the ^ on the top of the stack, pop ^ from the stack and append it to the postfix expression.
Postfix: 6 4 * 2 5 ^
Stack:
| + |
Since - is an operator, is left-to-right associative, and has the same precedence as the + at the top of the stack, pop + from the stack and append it to the postfix expression.
Postfix: 6 4 * 2 5 ^ +
Stack:
Push the - to the stack.
Postfix: 6 4 * 2 5 ^ +
Stack:
| - |
Token #9 Evaluation
Infix: 6*4+2^5-3
Since 3 is an operand, append it to the postfix expression.
Postfix: 6 4 * 2 5 ^ + 3
Stack:
| - |
All 9 Token Evaluations Completed
Since we are done processing the infix expression, pop the remaining operator from top of the stack and append it to the postfix expression.
Pop - from the stack and append it to the postfix expression.
Postfix: 6 4 * 2 5 ^ + 3 -
Stack:
Completed Conversion:
| Infix: | 6*4+2^5-3 |
| to | |
| Postfix: | 6 4 * 2 5 ^ + 3 - |
Example #2: 4*((2+6)/3)-2^2^3
Token #1 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since 4 is an operand, append it to the postfix expression.
Postfix: 4
Stack:
Token #2 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since the * is an operator and the stack is empty, push the * to the stack.
Postfix: 4
Stack:
| * |
Token #3 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since ( is an opening parenthesis, push it to the top of the stack.
Postfix: 4
Stack:
| ( * |
Token #4 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since ( is an opening parenthesis, push it to the top of the stack.
Postfix: 4
Stack:
| ( ( * |
Token #5 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since 2 is an operand, append it to the postfix expression.
Postfix: 4 2
Stack:
| ( ( * |
Token #6 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since + is an operator and has greater precedence than the ( on the top of the stack, push + to the top of the stack.
Postfix: 4 2
Stack:
| + ( ( * |
Token #7 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since 6 is an operand, append it to the postfix expression.
Postfix: 4 2 6
Stack:
| + ( ( * |
Token #8 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since the ) is a closing parenthesis, pop each operator from the stack one at a time and append to the postfix expression. Keep popping from the stack until an opening parenthesis is encountered.
Pop + from the top of the stack and append to the postfix expression.
Postfix: 4 2 6 +
Stack:
| ( ( * |
Since we are done with the expression inside the current parenthesis, pop the opening parenthesis from the top of the stack and discard.
Postfix: 4 2 6 +
Stack:
| ( * |
Token #9 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since / is an operator and has greater precedence than the ( on the top of the stack, push / to the top of the stack.
Postfix: 4 2 6 +
Stack:
| / ( * |
Token #10 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since 3 is an operand, append it to the postfix expression.
Postfix: 4 2 6 + 3
Stack:
| / ( * |
Token #11 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since the ) is a closing parenthesis, pop each operator from the stack one at a time and append to the postfix expression. Keep popping from the stack until an opening parenthesis is encountered.
Pop / from the top of the stack and append to the postfix expression.
Postfix: 4 2 6 + 3 /
Stack:
| ( * |
Since we are done with the expression inside the current parenthesis, pop the opening parenthesis from the top of the stack and discard.
Postfix: 4 2 6 + 3 /
Stack:
| * |
Token #12 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since - is an operator and has lower precedence than the * on the top of the stack, pop * from the stack and append it to the postfix expression.
Postfix: 4 2 6 + 3 / *
Stack:
Push the - to the stack.
Postfix: 4 2 6 + 3 / *
Stack:
| - |
Token #13 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since 2 is an operand, append it to the postfix expression.
Postfix: 4 2 6 + 3 / * 2
Stack:
| - |
Token #14 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since ^ is an operator and has greater precedence than the - on the top of the stack, push ^ to the top of the stack.
Postfix: 4 2 6 + 3 / * 2
Stack:
| ^ - |
Token #15 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since 3 is an operand, append it to the postfix expression.
Postfix: 4 2 6 + 3 / * 2 3
Stack:
| ^ - |
Token #16 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since ^ is an operator and has the same precedence as the ^ at the top of the stack, and the ^ at the top of the stack is right-to-left associative, push the ^ to the stack.
Postfix: 4 2 6 + 3 / * 2 3
Stack:
| ^ ^ - |
Token #17 Evaluation
Infix: 4*((2+6)/3)-2^3^4
Since 4 is an operand, append it to the postfix expression.
Postfix: 4 2 6 + 3 / * 2 3 4
Stack:
| ^ ^ - |
All 17 Token Evaluations Completed
Since we are done processing the infix expression, pop each of the remaining operators from top of the stack one at a time and append each to the postfix expression.
Pop ^ from the stack and append it to the postfix expression.
Postfix: 4 2 6 + 3 / * 2 3 4 ^
Stack:
| ^ - |
Pop ^ from the stack and append it to the postfix expression.
Postfix: 4 2 6 + 3 / * 2 3 4 ^ ^
Stack:
| - |
Pop - from the stack and append it to the postfix expression.
Postfix: 4 2 6 + 3 / * 2 3 4 ^ ^ -
Stack:
Completed Conversion:
| Infix: | 4*((2+6)/3)-2^3^4 |
| to | |
| Postfix: | 4 2 6 + 3 / * 2 3 4 ^ ^ - |