Infix, Prefix and Postfix

The conversions, run

The program below converts by building the expression tree implicitly through full bracketing, so the three forms can be printed together and checked against each other.

def to_forms(expression):
    """Given a fully bracketed infix expression as nested tuples, print all three."""

    def infix(node):
        if not isinstance(node, tuple):
            return node
        left, operator, right = node
        return "(%s %s %s)" % (infix(left), operator, infix(right))

    def prefix(node):
        if not isinstance(node, tuple):
            return node
        left, operator, right = node
        return "%s %s %s" % (operator, prefix(left), prefix(right))

    def postfix(node):
        if not isinstance(node, tuple):
            return node
        left, operator, right = node
        return "%s %s %s" % (postfix(left), postfix(right), operator)

    return infix(node=expression), prefix(expression), postfix(expression)


cases = [
    ("A + B",              ("A", "+", "B")),
    ("A + B x C",          ("A", "+", ("B", "x", "C"))),
    ("(A + B) x C",        (("A", "+", "B"), "x", "C")),
    ("A + B x C - D",      (("A", "+", ("B", "x", "C")), "-", "D")),
    ("(A + B) x (C - D)",  (("A", "+", "B"), "x", ("C", "-", "D"))),
]

print("%-20s %-24s %-18s %s" % ("meaning", "infix, bracketed", "prefix", "postfix"))
for name, tree in cases:
    infix_form, prefix_form, postfix_form = to_forms(tree)
    print("%-20s %-24s %-18s %s" % (name, infix_form, prefix_form, postfix_form))

meaning              infix, bracketed         prefix             postfix
A + B                (A + B)                  + A B              A B +
A + B x C            (A + (B x C))            + A x B C          A B C x +
(A + B) x C          ((A + B) x C)            x + A B C          A B + C x
A + B x C - D        ((A + (B x C)) - D)      - + A x B C D      A B C x + D -
(A + B) x (C - D)    ((A + B) x (C - D))      x + A B - C D      A B + C D - x

Read rows two and three together. The infix strings differ only by brackets; the postfix strings differ by the order of the symbols, with no brackets at all. That is the whole idea.

The precedence table to memorise

For this paper, the operators and their precedence, highest first:

Brackets are not an operator; they override the table.

The one to be careful about is ^. It is right associative, so 2 ^ 3 ^ 2 is 2 ^ (3 ^ 2), which is 2 to the 9th, 512, and not (2 ^ 3) ^ 2, which is 64. Examiners use this.

Quick revision

• Infix: operator between operands. Prefix (Polish): operator before. Postfix (Reverse Polish): operator

after.

• Infix is ambiguous without precedence, associativity and brackets; the string alone does not say what

it means.

• Prefix and postfix need none of those: the order of symbols fixes the meaning.
• Hand method: fully bracket in precedence order, then move each operator just after its closing bracket

for postfix, or just before its opening bracket for prefix, and drop the brackets.

• Precedence: ^ highest and right associative, then x / %, then + -, both left associative.
• 2 ^ 3 ^ 2 is 512, not 64.

Test yourself

1. Write A + B * C in prefix and postfix. Prefix + A x B C; postfix A B C x +.

2. Write (A + B) * C in postfix, and say how it differs from the answer above. A B + C x. The symbols are in a different order; no brackets are needed to tell the two apart.

3. Why do prefix and postfix need no brackets? Because the position of each operator relative to its operands fixes which operands it applies to, so there is no ambiguity for precedence or brackets to resolve.

4. Give the hand method for converting infix to postfix. Fully bracket the expression in precedence order, move each operator to just after its closing bracket, then remove the brackets.

5. State the precedence and associativity of the operators in this paper. ^ is highest and right associative; x, / and % are next and left associative; + and - are lowest and left associative.

6. Evaluate 2 ^ 3 ^ 2 and say why the answer is not 64.

1. Exponent is right associative, so it is 2 ^ (3 ^ 2), which is 2 to the 9th, not (2 ^ 3) ^ 2.