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 Prefix Expression?
As the name implies, a Prefix Expression (or Prefix Notation, or Polish Notation) is characterized by a math expression wherein the operators are placed before their operands (2 + 3 infix becomes + 2 3 prefix).
Since each prefix operator is evaluated from right to left, this eliminates the need for parenthesis. This is why prefix expressions are easier for computer algorithms to evaluate than infix expressions.
How to Convert Infix to Prefix 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 output 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 prefix 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 prefix using stack.
First, reverse the order of the infix expression. For example, if the infix expression is 4*3+(5/2), the reverse would be )2/5(+3*4.
Next, working from left to right on the reversed infix expression, 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 output. Operands always appear in the same order in the output as they do in the infix expression.
If the token is a closing parenthesis, push it to the stack. This marks the beginning of an expression that should be evaluated separately.
If the token is an opening parenthesis, until a closing parenthesis is encountered at the top of the stack, pop each operator from the stack and append to the output. 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 or equal precedence than the token, or until the stack is empty, pop each operator from the stack and append them to the output. 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, push the 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, until the operator on top of the stack has lower or equal precedence than the token and is left-to-right associative, or until the stack is empty, pop each operator from the stack and append them to the output. Then push the current token to the stack.
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 output expression.
Finally, reverse the order of the output expression to get the prefix expression.
Infix to Prefix Conversion Examples
The following three infix-to-prefix examples each give a step-by-step illustration of how the rules stated in the previous section are applied on a character-by-character basis.
Example #1: A+B*C+D
Reverse Infix Expression:
D + C * B + A
Scan tokens one at a time from left to right.
| Character | Stack | Ouput |
|---|---|---|
| D | D | |
Since D is an operand, print to output. | ||
| + | + | D |
Since + is an operator, and the stack is empty, push it to the stack. | ||
| C | + | D C |
Since C is an operand, print to output. | ||
| * | + * | D C |
Since * is an operator, and it has higher precedence than the + at the top of the stack, push * to the stack. | ||
| B | + * | D C B |
Since B is an operand, print to output. | ||
| + | + + | D C B * |
Since + is an operator, and it has lower precedence than the * at the top of the stack, pop * from the stack and append it to the output, and then push + to the stack. | ||
| A | + + | D C B * A |
Since A is an operand, print to output. | ||
| Scanning complete. | ||
| Pop remaining 2 operators from stack, one at a time, and append to output. | ||
| + | D C B * A + | |
| D C B * A + + | ||
| Reverse final output. | ||
| Prefix: | + + A * B C D | |
Example #2: 5*(6^2-2)
Reverse Infix Expression:
) 2 - 2 ^ 6 ( * 5
Scan tokens one at a time from left to right.
| Character | Stack | Ouput |
|---|---|---|
| ) | ) | |
Since ) is a closing parenthesis, push it to the stack. | ||
| 2 | ) | 2 |
Since 2 is an operand, print to output. | ||
| - | ) - | 2 |
Since - is an operator, and it has higher precedence than the ) at the top of the stack, push - to the stack. | ||
| 2 | ) - | 2 2 |
Since 2 is an operand, print to output. | ||
| ^ | ) - ^ | 2 2 |
Since ^ is an operator, and it has higher precedence than the - at the top of the stack, push ^ to the stack. | ||
| 6 | ) - ^ | 2 2 6 |
Since 6 is an operand, print to output. | ||
| ( | 2 2 6 ^ - | |
Since ( is an opening parenthesis, pop from the stack until a closing parenthesis is encountered. So pop ^ from the stack and append it to the output, pop - from the stack and append it to the output, and then pop the closing parenthesis from the stack and discard both parenthesis. | ||
| * | * | 2 2 6 ^ - |
Since * is an operator, and the stack is empty, push it to the stack. | ||
| 5 | * | 2 2 6 ^ - 5 |
Since 5 is an operand, print to output. | ||
| Scanning complete. | ||
| Pop remaining operator from stack and append to output. | ||
| 2 2 6 ^ - 5 * | ||
| Reverse final output. | ||
| Prefix: | * 5 - ^ 6 2 2 | |
Example #3: 2*(1+(4*(2+1)+3))
Reverse Infix Expression:
) ) 3 + ) 1 + 2 ( * 4 ( + 1 ( * 2
Scan tokens one at a time from left to right.
| Character | Stack | Ouput |
|---|---|---|
| ) | ) | |
Since ) is a closing parenthesis, push it to the stack. | ||
| ) | ) ) | |
Since ) is a closing parenthesis, push it to the stack. | ||
| 3 | ) ) | 3 |
Since 3 is an operand, print to output. | ||
| + | ) ) + | 3 |
Since + is an operator, and it has higher precedence than the ) at the top of the stack, push + to the stack. | ||
| ) | ) ) + ) | 3 |
Since ) is a closing parenthesis, push it to the stack. | ||
| 1 | ) ) + ) | 3 1 |
Since 1 is an operand, print to output. | ||
| + | ) ) + ) + | 3 1 |
Since + is an operator, and it has higher precedence than the ) at the top of the stack, push + to the stack. | ||
| 2 | ) ) + ) + | 3 1 2 |
Since 2 is an operand, print to output. | ||
| ( | ) ) + | 3 1 2 + |
Since ( is an opening parenthesis, pop from the stack until a closing parenthesis is encountered. So pop + from the stack and append it to the output, and then pop the closing parenthesis from the stack and discard both parenthesis. | ||
| * | ) ) + * | 3 1 2 + |
Since * is an operator, and it has higher precedence than the + at the top of the stack, push * to the stack. | ||
| 4 | ) ) + * | 3 1 2 + 4 |
Since 4 is an operand, print to output. | ||
| ( | ) | 3 1 2 + 4 * + |
Since ( is an opening parenthesis, pop from the stack until a closing parenthesis is encountered. So pop * from the stack and append it to the output, pop + from the stack and append it to the output, and then pop the closing parenthesis from the stack and discard both parenthesis. | ||
| + | ) + | 3 1 2 + 4 * + |
Since + is an operator, and it has higher precedence than the ) at the top of the stack, push + to the stack. | ||
| 1 | ) + | 3 1 2 + 4 * + 1 |
Since 1 is an operand, print to output. | ||
| ( | 3 1 2 + 4 * + 1 + | |
Since ( is an opening parenthesis, pop from the stack until a closing parenthesis is encountered. So pop + from the stack and append it to the output, and then pop the closing parenthesis from the stack and discard both parenthesis. | ||
| * | * | 3 1 2 + 4 * + 1 + |
Since * is an operator, and the stack is empty, push it to the stack. | ||
| 2 | * | 3 1 2 + 4 * + 1 + 2 |
Since 2 is an operand, print to output. | ||
| Scanning complete. | ||
| Pop remaining operator from stack and append to output. | ||
| 3 1 2 + 4 * + 1 + 2 * | ||
| Reverse final output. | ||
| Prefix: | * 2 + 1 + * 4 + 2 1 3 | |