Practical 3 continued: Infix to Postfix with a Stack

The brackets themselves are never output.

1. An operator: while the stack has an operator on top that should come first, pop it to the

output. Then push this one.

1. At the end, pop everything left to the output.
2. An opening bracket still on the stack at the end, or a closing bracket with no opening one, is an

unbalanced expression.

Rule 4 is the whole algorithm, and "should come first" is where precedence and associativity live:

• higher precedence on the stack, pop it;
• equal precedence and the operator is left associative, pop it;
• equal precedence and the operator is right associative, leave it.

The program

"""Infix to postfix, and the evaluation of postfix, for Module 2 practical 3."""

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


def tokenize(text):
    """Split into numbers, names, operators and brackets."""
    tokens = []
    i = 0
    while i < len(text):
        character = text[i]
        if character.isspace():
            i += 1
        elif character.isdigit() or character == ".":
            j = i
            while j < len(text) and (text[j].isdigit() or text[j] == "."):
                j += 1
            tokens.append(text[i:j])
            i = j
        elif character.isalpha():
            j = i
            while j < len(text) and text[j].isalnum():
                j += 1
            tokens.append(text[i:j])
            i = j
        elif character in PRECEDENCE or character in "()":
            tokens.append(character)
            i += 1
        else:
            raise ValueError(f"cannot read {character!r} at position {i}")
    return tokens


def is_operand(token):
    return token not in PRECEDENCE and token not in "()"


def pops_first(on_stack, arriving):
    """Should the operator already on the stack come out before this one?"""
    if on_stack == "(":
        return False
    if PRECEDENCE[on_stack] > PRECEDENCE[arriving]:
        return True
    if PRECEDENCE[on_stack] < PRECEDENCE[arriving]:
        return False
    return arriving not in RIGHT_ASSOCIATIVE      # equal: left associative pops


def to_postfix(text, trace=False):
    """The postfix form of an infix expression. Prints a trace if asked."""
    tokens = tokenize(text)
    output = []
    stack = []
    rows = []

    def note(token, action):
        rows.append((token, action, " ".join(stack), " ".join(output)))

    for token in tokens:
        if is_operand(token):
            output.append(token)
            note(token, "operand, straight to the output")
        elif token == "(":
            stack.append(token)
            note(token, "push the bracket")
        elif token == ")":
            popped = []
            while stack and stack[-1] != "(":
                popped.append(stack.pop())
                output.append(popped[-1])
            if not stack:
                raise ValueError("a ')' with no matching '('")
            stack.pop()
            note(token, f"pop to the '(': {' '.join(popped) or 'nothing'}")
        else:
            popped = []
            while stack and pops_first(stack[-1], token):
                popped.append(stack.pop())
                output.append(popped[-1])
            stack.append(token)
            if popped:
                note(token, f"pop {' '.join(popped)} first, then push {token}")
            else:
                note(token, f"push {token}")

    while stack:
        top = stack.pop()
        if top == "(":
            raise ValueError("a '(' that is never closed")
        output.append(top)
    note("end", "pop the rest of the stack")

    if trace:
        print(f"  {'token':<7} {'stack':<12} {'output':<24} what happened")
        for token, action, stack_now, output_now in rows:
            print(f"  {token:<7} {stack_now:<12} {output_now:<24} {action}")

    return " ".join(output)


def evaluate_postfix(text):
    """The value of a postfix expression, using a stack."""
    stack = []
    for token in tokenize(text):
        if is_operand(token):
            stack.append(float(token))
            continue
        if len(stack) < 2:
            raise ValueError(f"the operator {token!r} has too few operands")
        right = stack.pop()
        left = stack.pop()
        if token == "+":
            stack.append(left + right)
        elif token == "-":
            stack.append(left - right)
        elif token == "*":
            stack.append(left * right)
        elif token == "/":
            if right == 0:
                raise ZeroDivisionError("division by zero in the expression")
            stack.append(left / right)
        elif token == "%":
            stack.append(left % right)
        elif token == "^":
            stack.append(left ** right)
    if len(stack) != 1:
        raise ValueError("the expression left more than one value on the stack")
    return stack[0]

Four things in that file are the marks.

pops_first is the whole algorithm, and it has four cases: an opening bracket never pops, higher precedence pops, lower precedence does not, and equal precedence pops only when the arriving operator is left associative.

( is never popped by rule 4. It is only removed by its own closing bracket, which is what if on_stack == "(" protects.

In evaluate_postfix the SECOND value popped is the LEFT operand. right = stack.pop() comes first. Getting that round the wrong way gives the right answer for + and * and the wrong answer for -, /, % and ^, which is exactly the bug that survives testing on addition.

The unbalanced cases raise, both a closer with nothing open and an opener never closed.

A conversion traced, which is the journal entry

from postfix import to_postfix

expression = "a + b * c - d"
print(f"converting {expression!r}")
answer = to_postfix(expression, trace=True)
print(f"  postfix: {answer}")

converting 'a + b * c - d'
  token   stack        output                   what happened
  a                    a                        operand, straight to the output
  +       +            a                        push +
  b       +            a b                      operand, straight to the output
  *       + *          a b                      push *
  c       + *          a b c                    operand, straight to the output
  -       -            a b c * +                pop * + first, then push -
  d       -            a b c * + d              operand, straight to the output
  end                  a b c * + d -            pop the rest of the stack
  postfix: a b c * + d -

Read the stack column. The + was pushed and stayed there while arrived, because binds tighter; then - arrived, which does not bind tighter than +, so * and + both came out before - was pushed. That is rule 4 happening, and copying that table into the journal is what the entry is for.

Brackets, which is the other half

from postfix import to_postfix

expression = "( a + b ) * c"
print(f"converting {expression!r}")
print(f"  postfix: {to_postfix(expression, trace=True)}")

converting '( a + b ) * c'
  token   stack        output                   what happened
  (       (                                     push the bracket
  a       (            a                        operand, straight to the output
  +       ( +          a                        push +
  b       ( +          a b                      operand, straight to the output
  )                    a b +                    pop to the '(': +
  *       *            a b +                    push *
  c       *            a b + c                  operand, straight to the output
  end                  a b + c *                pop the rest of the stack
  postfix: a b + c *

The brackets appear in neither the output nor the final stack. They exist only to hold the + back until the ) arrives, and then they are discarded. Brackets are never part of postfix, which is the whole point of the notation.

The right associative power operator

from postfix import to_postfix

for expression in ["2 ^ 3 ^ 2", "2 - 3 - 4", "a ^ b ^ c", "a - b - c"]:
    print(f"{expression:<12} -> {to_postfix(expression)}")

print()
print("read them against each other:")
print("  2 ^ 3 ^ 2 -> 2 3 2 ^ ^   the RIGHT ^ is applied first, so 3^2 then 2^9")
print("  2 - 3 - 4 -> 2 3 - 4 -   the LEFT - is applied first, so (2-3) then -4")

2 ^ 3 ^ 2    -> 2 3 2 ^ ^
2 - 3 - 4    -> 2 3 - 4 -
a ^ b ^ c    -> a b c ^ ^
a - b - c    -> a b - c -

read them against each other:
  2 ^ 3 ^ 2 -> 2 3 2 ^ ^   the RIGHT ^ is applied first, so 3^2 then 2^9
  2 - 3 - 4 -> 2 3 - 4 -   the LEFT - is applied first, so (2-3) then -4

Those two lines are the whole difference between left and right associativity, and they are the pair to put in the journal. In 2 3 2 ^ ^ the first ^ reached is applied to 3 and 2; in 2 3 - 4 - the first - is applied to 2 and 3.

Every conversion evaluated, which is what proves it

A conversion that looks right can still be wrong. The only way to be sure is to evaluate the postfix and compare it with the value of the infix.

from postfix import to_postfix, evaluate_postfix

cases = [
    "2 + 3",
    "2 + 3 * 4",
    "2 * 3 + 4",
    "( 2 + 3 ) * 4",
    "2 * ( 3 + 4 )",
    "10 - 4 - 3",
    "10 - ( 4 - 3 )",
    "2 ^ 3 ^ 2",
    "( 2 ^ 3 ) ^ 2",
    "100 / 5 / 2",
    "100 / ( 5 / 2 )",
    "2 + 3 * 4 - 5 / 5",
    "( ( 2 + 3 ) * ( 4 - 1 ) ) ^ 2",
    "17 % 5 + 1",
]

print(f"{'infix':<32} {'postfix':<26} {'value':>12} {'Python':>12}  same?")
for infix in cases:
    postfix = to_postfix(infix)
    mine = evaluate_postfix(postfix)
    theirs = eval(infix.replace("^", "**"))
    agree = abs(mine - theirs) < 1e-9
    print(f"{infix:<32} {postfix:<26} {mine:>12.4f} {theirs:>12.4f}  {agree}")

infix                            postfix                           value       Python  same?
2 + 3                            2 3 +                            5.0000       5.0000  True
2 + 3 * 4                        2 3 4 * +                       14.0000      14.0000  True
2 * 3 + 4                        2 3 * 4 +                       10.0000      10.0000  True
( 2 + 3 ) * 4                    2 3 + 4 *                       20.0000      20.0000  True
2 * ( 3 + 4 )                    2 3 4 + *                       14.0000      14.0000  True
10 - 4 - 3                       10 4 - 3 -                       3.0000       3.0000  True
10 - ( 4 - 3 )                   10 4 3 - -                       9.0000       9.0000  True
2 ^ 3 ^ 2                        2 3 2 ^ ^                      512.0000     512.0000  True
( 2 ^ 3 ) ^ 2                    2 3 ^ 2 ^                       64.0000      64.0000  True
100 / 5 / 2                      100 5 / 2 /                     10.0000      10.0000  True
100 / ( 5 / 2 )                  100 5 2 / /                     40.0000      40.0000  True
2 + 3 * 4 - 5 / 5                2 3 4 * + 5 5 / -               13.0000      13.0000  True
( ( 2 + 3 ) * ( 4 - 1 ) ) ^ 2    2 3 + 4 1 - * 2 ^              225.0000     225.0000  True
17 % 5 + 1                       17 5 % 1 +                       3.0000       3.0000  True

Every row agrees, and the last column is the point: the conversion is not being proof-read, it is being checked against Python's own arithmetic on the original infix expression. Fourteen expressions, including both bracketings of the power operator and both of the division, and every value matches.

eval is used here only to produce a second opinion inside a test on a string this program wrote itself. Never use eval on text that came from a user, because it runs whatever it is given. That is worth a sentence in the journal, because it is the one place this chapter uses a dangerous tool and it should be seen to be used carefully.

Evaluation traced

from postfix import tokenize, is_operand

def evaluate_traced(text):
    stack = []
    print(f"  {'token':<7} {'action':<34} stack after")
    for token in tokenize(text):
        if is_operand(token):
            stack.append(float(token))
            print(f"  {token:<7} {'push the operand':<34} {stack}")
            continue
        right = stack.pop()
        left = stack.pop()
        value = {"+": left + right, "-": left - right,
                 "*": left * right, "/": left / right,
                 "^": left ** right}[token]
        stack.append(value)
        print(f"  {token:<7} {f'{left} {token} {right} = {value}':<34} {stack}")
    return stack[0]


print("evaluating 2 3 4 * + 5 -")
print("  the answer is", evaluate_traced("2 3 4 * + 5 -"))

evaluating 2 3 4 * + 5 -
  token   action                             stack after
  2       push the operand                   [2.0]
  3       push the operand                   [2.0, 3.0]
  4       push the operand                   [2.0, 3.0, 4.0]
  *       3.0 * 4.0 = 12.0                   [2.0, 12.0]
  +       2.0 + 12.0 = 14.0                  [14.0]
  5       push the operand                   [14.0, 5.0]
  -       14.0 - 5.0 = 9.0                   [9.0]
  the answer is 9.0

Read the token column. Operands are pushed and an operator pops two and pushes one, so the stack shrinks by one each time an operator is reached. The expression is valid exactly when the stack holds one value at the end, which is how evaluate_postfix detects a malformed expression.

The bug that survives testing on addition

from postfix import tokenize, is_operand


def evaluate_wrong(text):
    """Pops the operands in the WRONG order."""
    stack = []
    for token in tokenize(text):
        if is_operand(token):
            stack.append(float(token))
            continue
        left = stack.pop()       # WRONG: the first pop is the RIGHT operand
        right = stack.pop()
        stack.append({"+": left + right, "-": left - right,
                      "*": left * right, "/": left / right}[token])
    return stack[0]


from postfix import evaluate_postfix

print(f"{'postfix':<14} {'correct':>10} {'wrong order':>13}  same?")
for text in ["2 3 +", "2 3 *", "10 4 -", "100 5 /"]:
    right_way = evaluate_postfix(text)
    wrong_way = evaluate_wrong(text)
    print(f"{text:<14} {right_way:>10.4f} {wrong_way:>13.4f}  "
          f"{abs(right_way - wrong_way) < 1e-9}")

postfix           correct   wrong order  same?
2 3 +              5.0000        5.0000  True
2 3 *              6.0000        6.0000  True
10 4 -             6.0000       -6.0000  False
100 5 /           20.0000        0.0500  False

There it is. The wrong order is correct for + and * and wrong for - and /, because addition and multiplication do not care which way round their operands are and subtraction and division do. A student who tests only on 2 3 + ships the bug.

right = stack.pop() first, then left = stack.pop(). The second value out is the left operand, because it went in first.

Unbalanced expressions

from postfix import to_postfix

for expression in ["( a + b", "a + b )", "( ( a )", "a + b"]:
    try:
        print(f"{expression!r:<12} -> {to_postfix(expression)}")
    except ValueError as error:
        print(f"{expression!r:<12} -> refused: {error}")

'( a + b'    -> refused: a '(' that is never closed
'a + b )'    -> refused: a ')' with no matching '('
'( ( a )'    -> refused: a '(' that is never closed
'a + b'      -> a b +

Both faults are caught, and they are caught in different places: a closing bracket with nothing open is found when the stack runs out during rule 3, and an opening bracket never closed is found when rule 5 empties the stack and meets a (.

Prefix to postfix, if the examiner asks for it instead

MU's row says infix, and an examiner may ask for prefix, so here it is: read the prefix expression right to left, push operands, and when an operator is reached pop two and push them followed by the operator.

from postfix import tokenize, is_operand, evaluate_postfix


def prefix_to_postfix(text):
    """Read right to left, pushing partial postfix strings."""
    stack = []
    for token in reversed(tokenize(text)):
        if is_operand(token):
            stack.append(token)
        else:
            first = stack.pop()
            second = stack.pop()
            stack.append(f"{first} {second} {token}")
    return stack.pop()


for prefix, expected in [("+ a b", "a b +"),
                         ("+ a * b c", "a b c * +"),
                         ("* + a b c", "a b + c *"),
                         ("- + 2 3 4", "2 3 + 4 -")]:
    got = prefix_to_postfix(prefix)
    print(f"{prefix:<14} -> {got:<14} expected {expected:<14} {got == expected}")

print("and the last one evaluates to", evaluate_postfix(prefix_to_postfix("- + 2 3 4")))

+ a b          -> a b +          expected a b +          True
+ a * b c      -> a b c * +      expected a b c * +      True
* + a b c      -> a b + c *      expected a b + c *      True
- + 2 3 4      -> 2 3 + 4 -      expected 2 3 + 4 -      True
and the last one evaluates to 1.0

It is shorter than the infix conversion because prefix, like postfix, needs no precedence rules at all: the shape already says what applies to what.

Procedure

1. Save postfix.py with PRECEDENCE, RIGHT_ASSOCIATIVE, tokenize, pops_first, to_postfix

and evaluate_postfix.

1. Write pops_first with its four cases, including the opening bracket and the right associative

exception.

1. Make to_postfix able to print a trace table of token, stack, output and what happened.
2. Raise for a closing bracket with nothing open and for an opening bracket never closed.
3. In evaluate_postfix, pop the right operand first and the left second.
4. Convert a + b * c - d with the trace on and copy the table out.
5. Convert ( a + b ) * c with the trace on and note that the brackets appear nowhere in the output.
6. Convert 2 ^ 3 ^ 2 and 2 - 3 - 4 and say why the two differ.
7. Convert and then evaluate at least ten expressions, comparing each value with the value of the

infix, and record that every one agrees.

1. Write the wrong operand order and record that it is correct for + and * and wrong for - and

/.

Result

a + b c - d converted to the expected postfix, and the trace showed and + both leaving the stack before - was pushed. ( a + b ) c converted with no bracket in the output. 2 ^ 3 ^ 2 gave 2 3 2 ^ ^ and 2 - 3 - 4 gave 2 3 - 4 -, which is the right and left associative difference. Fourteen expressions were converted and evaluated, and every value agreed with Python's own value of the infix expression to within a billionth. The traced evaluation showed the stack shrinking by one at every operator and holding exactly one value at the end. Popping the operands in the wrong order gave the correct answer for + and and the wrong answer for - and /. Both unbalanced bracket cases were refused.

Where marks are lost

• No trace table. The table is the answer to this question; the postfix string alone is a

fraction of it.

• Treating ^ as left associative. 2 ^ 3 ^ 2 then converts to 2 3 ^ 2 ^, which is wrong.
• Popping the ( in rule 4. It must only be removed by its own ).
• Outputting the brackets. Postfix has none.
• Forgetting rule 5, so the last operators never reach the output.
• Popping the operands in the wrong order when evaluating, which passes every test on + and

*.

• Not evaluating the result at all. Converting and evaluating is what proves the conversion.
• Single character tokens only, so 12 + 345 is read as five one digit operands.
• No check for unbalanced brackets.

For the journal

The aim in MU's words. The three notation table, and the two lines showing that postfix needs neither brackets nor precedence. The precedence and associativity table, with ^ marked right associative. The six rules. Then postfix.py, and then the trace table for at least two expressions, one with an operator precedence decision and one with brackets, because those two tables are the entry. Then the 2 ^ 3 ^ 2 against 2 - 3 - 4 pair with one sentence on associativity. Then the table of conversions with their evaluated values beside Python's own values, and one sentence: the conversion is proved by evaluating it, not by reading it. The conclusion: the stack holds operators until an operator of lower or equal precedence arrives, brackets are discarded, and the operand popped second is the left one.

Quick revision

• Infix a + b, prefix + a b, postfix a b +.

Postfix needs no brackets and no precedence rules.

• Precedence: ^ 3, * / % 2, + - 1.
• Associativity: everything left except ^, which is right.
• Rule 1 operand to the output. Rule 2 push (. Rule 3 on ) pop to the ( and discard both.

Rule 4 pop while the top should come first, then push. Rule 5 pop the rest at the end.

• "Should come first": higher precedence pops. Equal precedence pops only if the arriving

operator is left associative, and ( never pops.

• 2 ^ 3 ^ 2 gives 2 3 2 ^ ^. 2 - 3 - 4 gives 2 3 - 4 -.
• Evaluating postfix: push operands; on an operator pop two and push one, so the stack

shrinks by one.

• right = pop() first, then left = pop(). The wrong order is right for + and * and wrong

for -, /, %, ^.

• Valid exactly when one value is left on the stack at the end.
• Unbalanced: a ) when the stack has no (, or a ( still there after rule 5.
• Never eval text from a user.

Questions you should be able to answer

1. Why does postfix need no brackets? Because the position of the operator already says which operands it applies to, so there is nothing left ambiguous for brackets or precedence rules to settle.

2. Convert a + b c and (a + b) c. a b c + and a b + c .

3. State rule 4. When an operator arrives, pop to the output every operator on the stack that should come out first, then push the new one.

4. What does "should come out first" mean exactly? Higher precedence on the stack pops; equal precedence pops only when the arriving operator is left associative; an opening bracket never pops.

5. Which operator is right associative, and what difference does it make? ^. 2 ^ 3 ^ 2 becomes 2 3 2 ^ ^, so the right hand power is applied first. Treating it as left associative gives 2 3 ^ 2 ^, which is a different value.

6. What happens to the brackets? They are never output. An opening bracket is pushed and removed by its matching closing bracket, and both are discarded.

7. How do you evaluate postfix? Read left to right. Push operands. On an operator, pop two, apply it, and push the result. One value should remain.

8. Which popped value is the left operand? The second one popped, because it was pushed first. So right = pop() then left = pop().

9. Why does the wrong operand order pass most tests? Because addition and multiplication give the same answer either way round. It fails on subtraction, division, remainder and power.

10. How do you know a conversion is correct rather than plausible? Evaluate the postfix and compare the value with the value of the original infix expression. Doing it for fourteen expressions is what this chapter does.

11. How are the two unbalanced cases detected? A closing bracket with nothing open empties the stack during rule 3; an opening bracket never closed is still on the stack at rule 5.