Unit 4 — Prefix/Infix/Postfix Notation

Lesson 1 — Three ways to write the same sum

Division: Elementary and above. This whole lesson is pencil-and-paper work. It is everything the ACSL Elementary Prefix/Infix/Postfix test asks, and it is the starting point for every other division.

Infix, prefix and postfix

The way you write sums at school puts each operator between its two numbers: 3 + 4. That is called infix notation ("in" the middle).

There are two other ways to write the same sum.

Prefix is also called Polish notation, after the Polish mathematician Jan Łukasiewicz who invented it, and postfix is Reverse Polish notation. Grandpa's calculator uses postfix.

The numbers (and later, letters) are called operands. The signs are operators. In all three notations the operands stay in the same order: only the operators move. Tokens (each number or operator) are written with one space between them, so 12 3 + means twelve plus three.

The five operators

The power sign has two spellings. The ACSL Elementary test writes it ^, as in 3 ^ 2. The other divisions' tests, and this book, write ↑, as in 3 ↑ 2. Both mean the same thing, and on a keyboard you type it as ^. This book always answers with ↑.

On the Elementary test every number is a single digit, you only ever divide by 1 or 2, and every power is 1 or 2 (5 ↑ 2 is 25, and 5 ↑ 1 is just 5).

Infix needs rules: PEMDAS

An infix sum only has one right answer because everyone agrees on the order of operations, often remembered as PEMDAS:

1. Parentheses (brackets) first;

2. then Exponents (powers, ↑);

3. then Multiplication and Division;

4. then Addition and Subtraction.

Multiplication and division are on the same level, and so are addition and subtraction. Operators on the same level are done from left to right.

Example 1. 8 - 3 - 2: both operators are on the same level, so go left to right. 8 − 3 = 5, then 5 − 2 = 3. Maya is right. Leo worked out 8 - (3 - 2), which is a different sum.

Example 2. 8 / 2 * 2: left to right, 8 / 2 = 4, then 4 × 2 = 8 (not 8 / 4 = 2).

Example 3. 6 + 8 / (4 - 2): brackets first, 4 − 2 = 2; then divide, 8 / 2 = 4; then add, 6 + 4 = 10.

Prefix and postfix need no brackets and no PEMDAS. The position of each operator already says which numbers it works on, so there is nothing to argue about. That is the answer to the second puzzle.

Evaluating postfix

To find the value of a postfix expression:

1. Find the first operator from the left.

2. Apply it to the two numbers just before it: the left one is the first number of the sum, the right one is the second.

3. Replace those three tokens by the answer, and repeat until one number is left.

Example 4. Grandpa's 6 8 4 2 - / +.

That is the calculator's 10, and the first puzzle is solved: it is exactly 6 + 8 / (4 - 2) from Example 3.

Example 5. 4 2 3 * +: the first operator is *, so 2 3 * = 6, giving 4 6 + = 10.

Watch out: order matters for -, / and ↑. 9 4 - is 9 − 4 = 5, not 4 − 9. The number that comes first is always the one on the left of the operator.

Evaluating prefix

In prefix each operator comes before its two numbers.

1. Find an operator that is followed straight away by two numbers.

2. Apply it to those two numbers, in order.

3. Replace the three tokens by the answer, and repeat.

The easiest operator to start with is the last one (the rightmost), since it is always followed by two numbers.

Example 6. * + 1 3 - 7 2

Example 7. + * 2 3 ↑ 4 2: ↑ 4 2 is 4 ↑ 2 = 16 and * 2 3 is 6, so the answer is 6 + 16 = 22.

Infix to prefix or postfix: brackets first

This method always works.

1. Fully bracket the infix sum: put brackets round every single operator and its two operands, following PEMDAS. Each bracket then holds exactly one operator.

2. Write the operands down in the same order.

3. Take the brackets from the inside out (and left to right when two are equally deep), and move each operator to just after its two operands for postfix, or just before them for prefix.

Example 8. Convert (7 - 3) * 2 + 8 / 2.

Fully bracketed, following PEMDAS: (((7 - 3) * 2) + (8 / 2)).

For postfix, the inside brackets first:

For prefix, the same brackets with each operator in front: (7 - 3) becomes - 7 3, then * - 7 3 2, then / 8 2, and the whole thing is + * - 7 3 2 / 8 2.

Check: all three forms have the value 12.

Example 9. The last puzzle: 2 * (9 - 4) + 6 / 2 is ((2 * (9 - 4)) + (6 / 2)). In postfix it is 2 9 4 - * 6 2 / +, and that is what Priya types. It evaluates to 10 + 3 = 13.

Example 10. Same-level operators go left to right, so 9 - 4 - 2 + 1 is (((9 - 4) - 2) + 1), which in postfix is 9 4 - 2 - 1 + and in prefix is + - - 9 4 2 1.

Check yourself: evaluate your answer and the original sum. If the values differ, something moved to the wrong place.

Prefix or postfix back to infix

Work in the other direction by scanning for a small piece you can undo.

• In prefix, find an operator followed by two operands.

• In postfix, find two operands followed by an operator.

Replace that piece by a bracketed infix piece, which now counts as one operand, and repeat.

Example 11. The postfix 2 3 * 4 2 ↑ +

Prefix to postfix, and back

To go from prefix to postfix, go through infix: first turn the prefix into a bracketed infix sum, then turn that into postfix.

Example 12. The prefix + * 2 3 ↑ 4 2 from Example 7. To infix: ↑ 4 2 becomes (4 ↑ 2), * 2 3 becomes (2 * 3), and the whole thing is ((2 * 3) + (4 ↑ 2)). To postfix: 2 3 * 4 2 ↑ +. That is exactly the expression of Example 11, and both have the value 22.

Postfix to prefix works the same way, through infix. Lesson 2 shows a quicker way that skips the infix step.

Optional. This unit's folder also holds a small Python program, assets/l1.py, that evaluates a postfix expression. You do not need it for the Elementary test: everything in this lesson is done with pencil and paper. Students going on to Lesson 2 meet it there.

Elementary checklist. You can now:

• use PEMDAS, and go left to right on the same level;

• evaluate a postfix expression;

• evaluate a prefix expression;

• convert infix to prefix and to postfix by fully bracketing;

• convert prefix to postfix and postfix to prefix, through infix.

That is the whole Elementary test. Exercises 1 to 9 are an Elementary practice test. Junior, Intermediate and Senior students continue with Lessons 2 and 3.

Lesson 2 — Longer expressions, and a stack by hand

Division: Junior and above.

A self-checker for Lesson 1

If you can run a Python program, this one evaluates a postfix expression, using exactly the "take the two numbers before the operator" idea of Lesson 1. Work each question by hand first, then use it to check yourself. Type the power sign as ^. It is saved as assets/l1.py; you do not need to understand the code yet, and Lesson 3 explains every line.

To run it, open a terminal in this unit's folder, type python assets/l1.py, then type a postfix expression such as 6 8 4 2 - / + and press Enter; it prints 10. You can also feed it a file: python assets/l1.py < assets/l1/3.in checks 5 2 ^ 6 2 / - and prints 22.

Letters, big numbers and powers

From Junior up, operands can be numbers of any size or letters standing for numbers, such as A B C. Letters are converted exactly like numbers: they are operands, and they never change order.

The power ↑ sits above * and / in PEMDAS. So 2 * 3 ↑ 2 is 2 × 9 = 18, not 6 ↑ 2 = 36. The questions in this book never put two ↑ in a row without brackets, so you never have to decide which power goes first.

Example 1. Convert (A + B * C) / (D - E) ↑ 2 to prefix and postfix.

Fully bracketed: the ↑ binds (D - E) and 2 first, and the / is done last.

((A + (B * C)) / ((D - E) ↑ 2))

Inside out: (B * C) → B C *, then (A + …) → A B C * +; (D - E) → D E -, then (… ↑ 2) → D E - 2 ↑; finally the /.

• Postfix: A B C * + D E - 2 ↑ /

• Prefix: / + A * B C ↑ - D E 2

Watch out: the 2 in ↑ 2 is an operand like any other, so it keeps its place in the list of operands: A, B, C, D, E, 2.

Prefix to postfix directly

Going through infix works, but for long expressions a direct method is faster. Find an operator with its two finished operands, and rewrite that piece in the other notation inside square brackets. A bracketed piece counts as one operand from then on. When nothing is left to do, drop the brackets.

Example 2. The prefix - * A + B C / D E to postfix. In prefix, a piece is an operator followed by two operands.

So the postfix is A B C + * D E / -.

Postfix to prefix is the same idea: in postfix a piece is two operands followed by an operator, and you rewrite it as [operator operand operand]. Run Example 2 backwards to see it.

A stack: how a machine evaluates postfix

A stack is a pile, like a pile of plates: you only ever put a plate on the top (a push) or take the top plate off (a pop).

To evaluate postfix with a stack, read the tokens from left to right:

• an operand: push it;

• an operator: pop the top value (it is the right operand), pop the next one (the left operand), work out left operator right, and push the answer.

At the end, the stack holds one value: the answer.

Example 3. 9 3 5 + * 12 4 / -, with the stack written bottom to top:

The answer is 69. Writing the table is slower than the scanning method of Lesson 1, but it never loses track of a long expression, and it is exactly how a program does it.

Watch out: the first value you pop is the right operand. For 72 3 - you pop 3 first, and the sum is 72 − 3, not 3 − 72.

A stack for prefix: read from the right

Prefix works the same way, reading the tokens from right to left. The one change: now the first value you pop is the left operand.

Example 4. - * 2 + 3 4 / 9 3, read from the right:

The answer is 11.

A stack in Python

A Python list can be a stack. This book keeps a list stack together with a count top of how many values are on it, and never shrinks the list:

• push a value: if top equals len(stack), append it; otherwise write it over the old value at stack[top]. Then add 1 to top.

• pop: take 1 from top; the popped value is stack[top].

• the top value is stack[top - 1].

Values above top are just leftovers from earlier; the program ignores them.

Put it together: this program evaluates a postfix expression and prints the stack after each token, just like the table in Example 3. Use it to check your own stack tables. An operator pops two values (right first, then left) by moving top down 2, and the loop at the end prints the values from stack[0] up to the top. It is saved as assets/l2.py.

Run it from this unit's folder:

python assets/l2.py < assets/l2/2.in

The input 9 3 5 + * 12 4 / - prints the nine rows of Example 3, one per token, ending with - : 69. assets/l2/3.in holds 2 3 ^ 1 -, which shows a power on the stack.

Lesson 3 — Evaluating and converting with Python

Division: Junior and above.

A postfix evaluator

The stack method turns straight into a program. The function apply does one operation, and the loop pushes operands and handles operators. Python writes the power ↑ as **, and the program reads it as ^, the keyboard's spelling.

show compares the value with its whole-number part: if they are equal, it prints the whole number; if not, it prints the decimal. The self-checker assets/l1.py from the start of Lesson 2 is exactly apply, the loop of evaluate_postfix, and show, reading the expression with input(). Look back at it now: you can read every line.

A prefix evaluator

For prefix, walk the tokens from right to left with range(len(tokens) - 1, -1, -1), and remember that the first value popped is now the left operand.

Converting with a stack

A stack can hold text as well as numbers. To turn postfix into prefix, push each operand as a piece of text; for an operator, pop two pieces and push one new piece, operator, left, right, joined with spaces. That is the square-bracket method of Lesson 2, done by a machine. It is saved as assets/l3.py.

Run it from this unit's folder:

python assets/l3.py < assets/l3/1.in

The input A B C * + D E - / prints / + A * B C - D E. assets/l3/3.in runs Lesson 2's Example 2 backwards: A B C + * D E / - prints - * A + B C / D E. To go from prefix to postfix instead, read from the right, and push left, right, operator.

Longer expressions and non-whole answers

Division: Intermediate and above.

Intermediate and Senior questions use longer expressions, and a division does not have to come out whole. The stack method is the same; just keep the fractions. Write a non-whole answer as a decimal. In this book every division ends after a few decimal places (halves, quarters, tenths and so on), never a repeating decimal such as 1/3.

Example 1. 7 2 / 3 4 * +: 7 / 2 = 3.5, 3 × 4 = 12, and 3.5 + 12 = 15.5.

Example 2. 3 4 ↑ 5 * 9 2 / 6 * - 8 /

A fraction in the middle can still end in a whole answer: in 9 4 / 2 ↑ 16 *, the value 9 / 4 = 2.25, and 2.25 ↑ 2 = 5.0625, but 5.0625 × 16 = 81.

Letters with values. A question may give values for the letters, such as A = 3 and B = 5. Replace each letter by its value, then evaluate as usual.

Optional aside: expression trees

Not assessed.

An expression can also be drawn as a tree: each operator is a branch point with its left operand below-left and its right operand below-right. Here is (A + B * C) / (D - E) ↑ 2 from Lesson 2:

            /
         /     \
       +         ↑
      / \       / \
     A   *     -   2
        / \   / \
       B   C D   E

Reading the tree in three orders gives the three notations:

• prefix: the operator, then its left side, then its right side: / + A * B C ↑ - D E 2;

• infix: the left side, then the operator, then the right side (with brackets);

• postfix: the left side, then the right side, then the operator: A B C * + D E - 2 ↑ /.

You will meet trees again later in the book; for now, the stack is all you need.