9/2/2021 4.9. Infix, Prefix and Postfix Expressions — Problem Solving with Algorithms and Data Structures
4.9. Infix, Prefix and Postfix Expressions
When you write an arithmetic expression such as B * C, the form of the expression provides you with
information so that you can interpret it correctly. In this case we know that the variable B is being multiplied
by the variable C since the multiplication operator * appears between them in the expression. This type of
notation is referred to as infix since the operator is in between the two operands that it is working on.
Consider another infix example, A + B * C. The operators + and * still appear between the operands, but
there is a problem. Which operands do they work on? Does the + work on A and B or does the * take B and
C? The expression seems ambiguous.
In fact, you have been reading and writing these types of expressions for a long time and they do not cause
you any problem. The reason for this is that you know something about the operators + and *. Each
operator has a precedence level. Operators of higher precedence are used before operators of lower
precedence. The only thing that can change that order is the presence of parentheses. The precedence
order for arithmetic operators places multiplication and division above addition and subtraction. If two
operators of equal precedence appear, then a left-to-right ordering or associativity is used.
Let’s interpret the troublesome expression A + B * C using operator precedence. B and C are multiplied
first, and A is then added to that result. (A + B) * C would force the addition of A and B to be done first
before the multiplication. In expression A + B + C, by precedence (via associativity), the leftmost + would be 1
done first.
Although all this may be obvious to you, remember that computers need to know exactly what operators to
perform and in what order. One way to write an expression that guarantees there will be no confusion with
respect to the order of operations is to create what is called a fully parenthesized expression. This type of
expression uses one pair of parentheses for each operator. The parentheses dictate the order of
operations; there is no ambiguity. There is also no need to remember any precedence rules.
The expression A + B * C + D can be rewritten as ((A + (B * C)) + D) to show that the multiplication
happens first, followed by the leftmost addition. A + B + C + D can be written as (((A + B) + C) + D) since
the addition operations associate from left to right. 1
There are two other very important expression formats that may not seem obvious to you at first. Consider
the infix expression A + B. What would happen if we moved the operator before the two operands? The
resulting expression would be + A B. Likewise, we could move the operator to the end. We would get A B +.
These look a bit strange.
These changes to the position of the operator with respect to the operands create two new expression
formats, prefix and postfix. Prefix expression notation requires that all operators precede the two
operands that they work on. Postfix, on the other hand, requires that its operators come after the
corresponding operands. A few more examples should help to make this a bit clearer (see Table 2).
A + B * C would be written as + A * B C in prefix. The multiplication operator comes immediately before the
operands B and C, denoting that * has precedence over +. The addition operator then appears before the A
and the result of the multiplication.
In postfix, the expression would be A B C * +. Again, the order of operations is preserved since the *
appears immediately after the B and the C, denoting that * has precedence, with + coming after. Although
the operators moved and now appear either before or after their respective operands, the order of the
operands stayed exactly the same relative to one another.
https://runestone.academy/runestone/books/published/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html 1/10
, 9/2/2021 4.9. Infix, Prefix and Postfix Expressions — Problem Solving with Algorithms and Data Structures
Table 2: Examples of Infix, Prefix, and Postfix
Infix Expression Prefix Expression Postfix Expression
A+B +AB AB+
A+B*C +A*BC ABC*+
Now consider the infix expression (A + B) * C. Recall that in this case, infix requires the parentheses to
force the performance of the addition before the multiplication. However, when A + B was written in prefix,
the addition operator was simply moved before the operands, + A B. The result of this operation becomes
the first operand for the multiplication. The multiplication operator is moved in front of the entire expression,
giving us * + A B C. Likewise, in postfix A B + forces the addition to happen first. The multiplication can be
done to that result and the remaining operand C. The proper postfix expression is then A B + C *.
Consider these three expressions again (see Table 3). Something very important has happened. Where did
the parentheses go? Why don’t we need them in prefix and postfix? The answer is that the operators are no
longer ambiguous with respect to the operands that they work on. Only infix notation requires the additional
symbols. The order of operations within prefix and postfix expressions is completely determined by the
position of the operator and nothing else. In many ways, this makes infix the least desirable notation to use.
1
Table 3: An Expression with Parentheses
Infix Expression Prefix Expression Postfix Expression
(A + B) * C *+ABC AB+C*
Table 4 shows some additional examples of infix expressions and the equivalent prefix and postfix
expressions. Be sure that you understand how they are equivalent in terms of the order of the operations
being performed.
1
Table 4: Additional Examples of Infix, Prefix, and Postfix
Infix Expression Prefix Expression Postfix Expression
A+B*C+D ++A*BCD ABC*+D+
(A + B) * (C + D) *+AB+CD AB+CD+*
A*B+C*D +*AB*CD AB*CD*+
A+B+C+D +++ABCD AB+C+D+
4.9.1. Conversion of Infix Expressions to Prefix
and Postfix
So far, we have used ad hoc methods to convert between infix expressions and the equivalent prefix and
postfix expression notations. As you might expect, there are algorithmic ways to perform the conversion
that allow any expression of any complexity to be correctly transformed.
https://runestone.academy/runestone/books/published/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html 2/10
4.9. Infix, Prefix and Postfix Expressions
When you write an arithmetic expression such as B * C, the form of the expression provides you with
information so that you can interpret it correctly. In this case we know that the variable B is being multiplied
by the variable C since the multiplication operator * appears between them in the expression. This type of
notation is referred to as infix since the operator is in between the two operands that it is working on.
Consider another infix example, A + B * C. The operators + and * still appear between the operands, but
there is a problem. Which operands do they work on? Does the + work on A and B or does the * take B and
C? The expression seems ambiguous.
In fact, you have been reading and writing these types of expressions for a long time and they do not cause
you any problem. The reason for this is that you know something about the operators + and *. Each
operator has a precedence level. Operators of higher precedence are used before operators of lower
precedence. The only thing that can change that order is the presence of parentheses. The precedence
order for arithmetic operators places multiplication and division above addition and subtraction. If two
operators of equal precedence appear, then a left-to-right ordering or associativity is used.
Let’s interpret the troublesome expression A + B * C using operator precedence. B and C are multiplied
first, and A is then added to that result. (A + B) * C would force the addition of A and B to be done first
before the multiplication. In expression A + B + C, by precedence (via associativity), the leftmost + would be 1
done first.
Although all this may be obvious to you, remember that computers need to know exactly what operators to
perform and in what order. One way to write an expression that guarantees there will be no confusion with
respect to the order of operations is to create what is called a fully parenthesized expression. This type of
expression uses one pair of parentheses for each operator. The parentheses dictate the order of
operations; there is no ambiguity. There is also no need to remember any precedence rules.
The expression A + B * C + D can be rewritten as ((A + (B * C)) + D) to show that the multiplication
happens first, followed by the leftmost addition. A + B + C + D can be written as (((A + B) + C) + D) since
the addition operations associate from left to right. 1
There are two other very important expression formats that may not seem obvious to you at first. Consider
the infix expression A + B. What would happen if we moved the operator before the two operands? The
resulting expression would be + A B. Likewise, we could move the operator to the end. We would get A B +.
These look a bit strange.
These changes to the position of the operator with respect to the operands create two new expression
formats, prefix and postfix. Prefix expression notation requires that all operators precede the two
operands that they work on. Postfix, on the other hand, requires that its operators come after the
corresponding operands. A few more examples should help to make this a bit clearer (see Table 2).
A + B * C would be written as + A * B C in prefix. The multiplication operator comes immediately before the
operands B and C, denoting that * has precedence over +. The addition operator then appears before the A
and the result of the multiplication.
In postfix, the expression would be A B C * +. Again, the order of operations is preserved since the *
appears immediately after the B and the C, denoting that * has precedence, with + coming after. Although
the operators moved and now appear either before or after their respective operands, the order of the
operands stayed exactly the same relative to one another.
https://runestone.academy/runestone/books/published/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html 1/10
, 9/2/2021 4.9. Infix, Prefix and Postfix Expressions — Problem Solving with Algorithms and Data Structures
Table 2: Examples of Infix, Prefix, and Postfix
Infix Expression Prefix Expression Postfix Expression
A+B +AB AB+
A+B*C +A*BC ABC*+
Now consider the infix expression (A + B) * C. Recall that in this case, infix requires the parentheses to
force the performance of the addition before the multiplication. However, when A + B was written in prefix,
the addition operator was simply moved before the operands, + A B. The result of this operation becomes
the first operand for the multiplication. The multiplication operator is moved in front of the entire expression,
giving us * + A B C. Likewise, in postfix A B + forces the addition to happen first. The multiplication can be
done to that result and the remaining operand C. The proper postfix expression is then A B + C *.
Consider these three expressions again (see Table 3). Something very important has happened. Where did
the parentheses go? Why don’t we need them in prefix and postfix? The answer is that the operators are no
longer ambiguous with respect to the operands that they work on. Only infix notation requires the additional
symbols. The order of operations within prefix and postfix expressions is completely determined by the
position of the operator and nothing else. In many ways, this makes infix the least desirable notation to use.
1
Table 3: An Expression with Parentheses
Infix Expression Prefix Expression Postfix Expression
(A + B) * C *+ABC AB+C*
Table 4 shows some additional examples of infix expressions and the equivalent prefix and postfix
expressions. Be sure that you understand how they are equivalent in terms of the order of the operations
being performed.
1
Table 4: Additional Examples of Infix, Prefix, and Postfix
Infix Expression Prefix Expression Postfix Expression
A+B*C+D ++A*BCD ABC*+D+
(A + B) * (C + D) *+AB+CD AB+CD+*
A*B+C*D +*AB*CD AB*CD*+
A+B+C+D +++ABCD AB+C+D+
4.9.1. Conversion of Infix Expressions to Prefix
and Postfix
So far, we have used ad hoc methods to convert between infix expressions and the equivalent prefix and
postfix expression notations. As you might expect, there are algorithmic ways to perform the conversion
that allow any expression of any complexity to be correctly transformed.
https://runestone.academy/runestone/books/published/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html 2/10
