Practical 15 continued: Prefix to Postfix, and Evaluating It

The algorithm in three lines

1. Read the prefix expression from right to left.
2. An operand is pushed as it stands.
3. An operator pops two, and pushes first second operator as one string.

The stack in this algorithm holds strings, not numbers: partly built postfix expressions. At the end there is exactly one, and that is the answer.

Why right to left. In prefix the operator comes before its operands, so reading forwards you meet an operator before you know what it applies to. Reading backwards you meet the operands first, and by the time the operator arrives, its two operands are the two most recent things on the stack. Reading forwards would need recursion or a second pass.

Which popped value is which. The stack is read backwards, so the first value popped is the one that was nearer the operator, which is its first operand. Hence a = stack.pop() then b = stack.pop() and the result is a b operator. Swap those and - 10 6 converts to 6 10 -, which evaluates to -4 instead of 4. The trace above is where to check it: at the -, the stack held ['6', '10'] and the result was 10 6 -.

Evaluating postfix

The same shape with numbers instead of strings, and the operand order reversed:

b = stack.pop()        # the SECOND operand
a = stack.pop()        # the first
stack.append(a - b)    # not b - a

Reading forwards this time, so the first value popped is the one pushed most recently, which is the second operand. That is the opposite of the conversion, and the two traces on the page are what make it clear: in the conversion at the -, the stack was ['6', '10']; in the evaluation at the -, it was [7, 10, 6] and the answer was 10 - 6.

The program checks the answer against arithmetic. (3 + 4) * (10 - 6) is 7 times 4, which is 28, and the page prints both the program's 28 and that reasoning. A conversion that silently reversed the subtraction would give 7 times -4, which is -28, and the check would catch it.

Note the / result is a float. 6 5 * 3 / gives 10.0 and not 10, because Python's / always gives a float. For integer division the operator would be //, and a calculator that must print 10 has to say so explicitly. That is worth a line in the journal, because the examiner's model answer may show 10.

What must be refused

Three faults, and all three are shown firing:

The end-of-expression check is the one students leave out. After the loop the stack must hold exactly one value. If it holds more, the expression had too many operands; if the loop ran out of operands for an operator, that was caught earlier. Both checks are two lines and both are marked.

Infix to postfix, which is where precedence comes in

MU's bullet asks for prefix to postfix, and infix to postfix is worth having as well: it is the conversion a compiler actually does, it is at least as likely in an examination, and it is the only one of the three that needs a precedence table.

The algorithm is Dijkstra's shunting yard, and the name is worth knowing.

PRECEDENCE = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
RIGHT_ASSOCIATIVE = {"^"}


def infix_to_postfix(infix, trace=False):
    """Dijkstra's shunting-yard algorithm: one stack, one pass, left to right."""
    out, stack = [], []
    if trace:
        print(f"    {'token':<7}{'output so far':<24}stack")
    for token in infix.split():
        if token == "(":
            stack.append(token)
        elif token == ")":
            while stack and stack[-1] != "(":
                out.append(stack.pop())
            if not stack:
                raise ValueError("a ')' with no '(' before it")
            stack.pop()                       # throw the '(' away
        elif token in PRECEDENCE:
            while (stack and stack[-1] != "("
                   and (PRECEDENCE[stack[-1]] > PRECEDENCE[token]
                        or (PRECEDENCE[stack[-1]] == PRECEDENCE[token]
                            and token not in RIGHT_ASSOCIATIVE))):
                out.append(stack.pop())
            stack.append(token)
        else:
            out.append(token)
        if trace:
            print(f"    {token:<7}{' '.join(out):<24}{stack}")

    while stack:
        top = stack.pop()
        if top == "(":
            raise ValueError("a '(' that is never closed")
        out.append(top)
    return " ".join(out)


print("infix to postfix, step by step")
i = "( 3 + 4 ) * ( 10 - 6 )"
print("  infix  :", i)
print("  postfix:", infix_to_postfix(i, trace=True))

print()
print("precedence and brackets, seven expressions")
for i in ("2 + 3 * 4",
          "( 2 + 3 ) * 4",
          "2 * 3 + 4",
          "2 + 3 - 4",
          "2 ^ 3 ^ 2",
          "( 2 ^ 3 ) ^ 2",
          "2 * ( 3 + 4 ) / 7"):
    print(f"  {i:<22} -> {infix_to_postfix(i)}")

print()
print("the two bracket faults")
for bad in ("( 2 + 3", "2 + 3 )"):
    try:
        infix_to_postfix(bad)
    except ValueError as e:
        print(f"  {bad!r:<12} ValueError: {e}")

infix to postfix, step by step
  infix  : ( 3 + 4 ) * ( 10 - 6 )
    token  output so far           stack
    (                              ['(']
    3      3                       ['(']
    +      3                       ['(', '+']
    4      3 4                     ['(', '+']
    )      3 4 +                   []
    *      3 4 +                   ['*']
    (      3 4 +                   ['*', '(']
    10     3 4 + 10                ['*', '(']
    -      3 4 + 10                ['*', '(', '-']
    6      3 4 + 10 6              ['*', '(', '-']
    )      3 4 + 10 6 -            ['*']
  postfix: 3 4 + 10 6 - *

precedence and brackets, seven expressions
  2 + 3 * 4              -> 2 3 4 * +
  ( 2 + 3 ) * 4          -> 2 3 + 4 *
  2 * 3 + 4              -> 2 3 * 4 +
  2 + 3 - 4              -> 2 3 + 4 -
  2 ^ 3 ^ 2              -> 2 3 2 ^ ^
  ( 2 ^ 3 ) ^ 2          -> 2 3 ^ 2 ^
  2 * ( 3 + 4 ) / 7      -> 2 3 4 + * 7 /

the two bracket faults
  '( 2 + 3'    ValueError: a '(' that is never closed
  '2 + 3 )'    ValueError: a ')' with no '(' before it

The four rules

And at the end, pop everything left. A ( still on the stack means it was never closed.

Precedence: ^ is 3, and / are 2, + and - are 1. That is what makes 2 + 3 4 come out as 2 3 4 +: when the arrives, the + on the stack has lower precedence, so it stays, and the * goes on top of it.

Associativity is the subtle part, and the run shows it. 2 ^ 3 ^ 2 gives 2 3 2 ^ ^, which evaluates as 2 to the power of (3 to the power of 2), which is 2 to the 9, which is 512. That is right: exponentiation is right associative. Every other operator here is left associative, so 2 + 3 - 4 gives 2 3 + 4 -, which is (2 + 3) - 4.

The one condition in the program that does this is:

or (PRECEDENCE[stack[-1]] == PRECEDENCE[token]
    and token not in RIGHT_ASSOCIATIVE)

An operator of equal precedence is popped only if the new operator is left associative. Drop the and and 2 ^ 3 ^ 2 converts to 2 3 ^ 2 ^, which is (2 cubed) squared, or 64, not 512. The run prints both forms, 2 ^ 3 ^ 2 and ( 2 ^ 3 ) ^ 2, so the difference can be read off the page.

The brackets never appear in the output. They were only ever there to overrule precedence, and once the operators are in the right order they have nothing left to say. That is the point of postfix in one sentence.

The three conversions, side by side

Prefix to postfix can also be done by reversing the infix method, and it can be done with recursion, and it can be done by building an expression tree and taking its post-order traversal. That last route is the link to [Practical 17: Binary Search Trees and Tree Traversals]: prefix is the pre-order traversal of an expression tree, postfix is its post-order traversal, and infix is its in-order traversal. That sentence is worth four marks and it is the reason these two topics sit next to each other on the syllabus.

Procedure

1. Write the first program and run it. Check the trace of * + 3 4 - 10 6 against your own

working on paper.

1. Swap a and b in the conversion and run it again. - 10 6 now converts to 6 10 - and the

value becomes -4.

1. Swap a and b in the evaluator instead, and note that the same wrong answer appears from the

other end.

1. Convert + * 2 3 / 8 4 by hand, then check it, then evaluate it.
2. Write the shunting-yard program. Convert 2 ^ 3 ^ 2 and evaluate it with the first program:

the answer should be 512.

1. Remove the associativity condition and confirm that the answer becomes 64.
2. Add unary minus, so that - 5 means negative five. It is harder than it looks, and saying

why in the journal is worth more than making it work: the same symbol now has two meanings and two precedences, and the converter has to tell them apart from what came before it.

Result

A prefix expression was converted to postfix with one stack, reading right to left, and the conversion was traced token by token. The postfix expression was evaluated with a second stack reading left to right, giving 28 for ( 3 + 4 ) * ( 10 - 6 ), which agrees with the arithmetic done by hand. The order of the two popped operands was shown to matter, and to be opposite in the two algorithms. Three malformed expressions were refused with the appropriate exceptions. Infix was then converted to postfix by the shunting-yard algorithm with a precedence table, and right associativity of exponentiation was demonstrated by 2 ^ 3 ^ 2 converting to 2 3 2 ^ ^ and ( 2 ^ 3 ) ^ 2 to 2 3 ^ 2 ^.

Where marks are lost

• Reading prefix from left to right. It has to be read backwards, or the operator arrives

before its operands.

• Popping the operands in the wrong order, so subtraction and division come out negated or

inverted. It is the opposite order in the two algorithms.

• Not checking that exactly one value is left at the end.
• Not checking that an operator has two operands before popping.
• Leaving the brackets in the postfix output.
• Popping an equal-precedence operator for ^, which makes exponentiation left associative

and gives 64 where the answer is 512.

• Forgetting to discard the ( after a ), so it reaches the output.
• Not reporting an unclosed ( at the end.
• Showing no trace. The examiner marks the working, and the stack after each token is the

working.

For the journal

Write the aim, MU's own wording, and the table of the three notations with one expression written in all three. Then the conversion algorithm in three numbered lines, the program, and the full trace, because the trace is what is marked. Then the evaluation with its trace and the hand check that 7 times 4 is 28. Then the shunting-yard program with the table of seven expressions, and the two forms of 2 ^ 3 ^ 2 side by side with their values, 512 and 64. Close with the sentence about expression trees: prefix, infix and postfix are the pre-order, in-order and post-order traversals of the same tree. The conclusion: postfix needs no brackets because the operator's position fixes its operands, which is why it can be evaluated in one pass with one stack.

Quick revision

• Infix needs brackets and precedence; prefix and postfix need neither, because the operator's

position says which operands it takes.

• Postfix is evaluated in one left-to-right pass with one stack: operands wait, an operator takes

the two most recent.

• Prefix to postfix: read right to left, push operands, and on an operator pop two and push

first second operator.

• In the conversion, the first value popped is the first operand. In the evaluation, the first

value popped is the second operand. They are opposite, and -, / and ^ are where it shows.

• At the end of either algorithm the stack must hold exactly one value.
• Infix to postfix is the shunting yard: operands out, ( pushed, ) pops to the (, an

operator pops those of higher or equal precedence and is then pushed.

• Precedence: ^ 3, * and / 2, + and - 1.
• ^ is right associative, so an equal-precedence operator is not popped for it. 2 ^ 3 ^ 2

is 2 3 2 ^ ^, which is 512; ( 2 ^ 3 ) ^ 2 is 2 3 ^ 2 ^, which is 64.

• Brackets never appear in the postfix output.
• Prefix, infix and postfix are the pre-order, in-order and post-order traversals of the

expression tree.

Questions you should be able to answer

1. Why do prefix and postfix need no brackets? Because the position of the operator determines which operands it applies to, so the expression has exactly one reading. Infix is ambiguous without precedence rules and brackets.

2. Why is a prefix expression read from right to left? Because the operator comes before its operands, so reading forwards you meet an operator before you know what it applies to. Read backwards, the two operands are already on the stack when the operator arrives.

3. In the evaluator, which of the two popped values is the second operand? The first one popped, because it was pushed most recently. So a is popped second and the result is a - b, not b - a.

4. Convert + 3 4 - 10 6 to postfix and evaluate it. 3 4 + 10 6 - , which is 7 times 4, which is 28.

5. What two checks must be made for a malformed expression? That an operator has two operands available when it is reached, and that exactly one value remains on the stack at the end.

6. Convert 2 + 3 4 to postfix, and say why. 2 3 4 +. When the arrives, the + on the stack has lower precedence, so it is not popped; the goes above it and comes off first.

7. What is the postfix form of 2 ^ 3 ^ 2, and what is its value? 2 3 2 ^ ^, which is 2 to the power of 9, so 512. Exponentiation is right associative, so an equal-precedence operator is not popped for it. ( 2 ^ 3 ) ^ 2 gives 2 3 ^ 2 ^, which is 64.

8. Where do the brackets go in the postfix output? Nowhere. They existed only to overrule precedence, and once the operators are in the right order they carry no information.

9. What is the relationship between the three notations and a binary tree? They are the three depth-first traversals of the expression tree: prefix is pre-order, infix is in-order, and postfix is post-order.