Precedence trees in Python

Why this matters

A Python expression such as 2 + 3 * 4 has one value, but the line does not say which operator runs first. The interpreter follows a fixed set of rules called precedence (which operator groups first) and associativity (which way operators of equal rank group). If you read the line with the wrong rules, you predict the wrong value, and the program prints a number that looks plausible and is still wrong.

A precedence tree is a drawing of the grouping. It turns the flat line into a shape with one operator at the top, and the shape shows what each operator works on. Once you have the shape, you can write the same grouping with parentheses. Parentheses make the grouping visible to the next reader, including you in six months.

This lesson does one job: draw the tree, then write the parentheses. The operators themselves are covered in the earlier lessons of this module. Python's grouping has a few places where it differs from languages such as Java and C, and those places are marked below.

Operators are branches, operands are leaves

Start with a plain idea. An expression is a set of values combined by operators. Each operator takes one or two values and makes one new value. We draw this as a tree:

• An operator with two inputs is a node with two children. The children are the things it works on.
• A number or name with no inputs is a leaf, a node at the end of a branch.
• The top node is the last operation to run. Its value is the value of the whole expression.

Take 2 + 3 * 4. The * works on 3 and 4. The + works on 2 and the result of the multiplication. So the tree has + at the top:

+
├── 2
└── *
    ├── 3
    └── 4

Evaluate the tree from the bottom up. The * node gives 12. The + node then adds 2 and 12, which gives 14. Python prints 14 for this line:

The output is:

14
20

The tree shows that multiplication is lower down, so it runs first. That is the rule called precedence: * ranks higher than +, so * groups tighter. The second line uses brackets to group the addition first.

Now write the same grouping with parentheses: 2 + (3 * 4). The parentheses say what the tree says. Every parenthesis pair in a fully parenthesised expression corresponds to one node of the tree.

Same rank: left to right

Precedence is only half the story. When two operators have the same rank, the grouping goes in a fixed direction. For most binary operators in Python (+, -, *, /, //, %, <<, &, and, or) the direction is left to right.

Take 10 - 4 - 3. Both operators have the same rank. The left one groups first, so the tree is:

-
├── -
│   ├── 10
│   └── 4
└── 3

The inner 10 - 4 gives 6, and the outer 6 - 3 gives 3. Now compare the grouping someone might expect if they read right to left:

-
├── 10
└── -
    ├── 4
    └── 3

That tree gives 10 - (4 - 3), which is 9. Python gives 3. Here is the code to check both:

The output is:

B: 3
B2: 9

The rule is: for left-to-right operators, the left group wins unless parentheses say otherwise. When you write a - b - c, add the parentheses (a - b) - c in your head or on paper.

The exception is the power operator **. It groups right to left, so 2 ** 3 ** 2 means 2 ** (3 ** 2), which is 512, and not (2 ** 3) ** 2, which is 64:

The output is:

C: 512
C2: 64

Assignment in Python is a statement, not an expression with a tree, so it does not take part in precedence in the same way. A chain such as x = y = z = 5 assigns the value 5 to x, y and z from left to right. The assignment lesson covered that case.

Turning a tree into parentheses

Suppose you have a tree and need the parentheses. The method is mechanical:

1. Find the top node, the operator that runs last.
2. Wrap its left child and its right child in parentheses, if the child is itself an operator.
3. Repeat for each child, working down until every operator has been wrapped.
4. Remove only the parentheses that the precedence rules would add anyway, if you want the shortest form. You may keep all of them for clarity.

Here is a longer expression: a + b * c - d / e. Build the tree first. The * groups b and c. The / groups d and e. The + joins a with the product. The - joins the sum with the quotient:

-
├── +
│   ├── a
│   └── *
│       ├── b
│       └── c
└── /
    ├── d
    └── e

Read the top node first. Its children are the + subtree and the / subtree. Wrap each one:

((a + (b * c)) - (d / e))

The outer pair belongs to the top -. Inside it, (a + (b * c)) is the + node, and (b * c) is the * node. A reader can now check the grouping without knowing the rank table.

You can also go the other way. Given the fully parenthesised form, draw the tree by reading from the inside out. Each pair of parentheses is one node. The operator just inside the pair is that node's operator.

Try the check in code. Both lines below give the same value because the parentheses match the tree:

The output is:

19.0
19.0

The division / always gives a float, so the result has a decimal point. The two lines agree because the parentheses match the tree.

Example two: a longer condition

Conditions are the place where precedence mistakes cost the most, because a condition decides which branch of the program runs. Take this one:

score >= 50 and attempts < 3 or has_pass and not blocked

Draw the tree. Start at the top. The lowest-ranking operator in this line is or, so it is the top node. Its left side is score >= 50 and attempts < 3. Its right side is has_pass and not blocked. Each and joins two comparisons or names. The not is a unary operator, which means it takes one input, so it is a node with a single child:

or
├── and
│   ├── >=
│   │   ├── score
│   │   └── 50
│   └── <
│       ├── attempts
│       └── 3
└── and
    ├── has_pass
    └── not
        └── blocked

Turn the tree into parentheses:

((score >= 50) and (attempts < 3)) or (has_pass and (not blocked))

The redundant pair around not blocked is kept on purpose, since it marks the unary operator's input. Now check that the two forms always agree. The program below tries every combination of the inputs that the condition uses, and counts how often the two forms differ:

The output is:

mismatches: 0

Zero mismatches means the parentheses match the grouping the interpreter uses. This check is a good habit: when a condition is hard to read, write the parenthesised form, and test both forms on a few inputs before you trust the change.

The rank table

You do not need to memorise the whole table, but you do need the order for the operators you use. The Python language reference lists these groups from the highest rank to the lowest:

• brackets, calls and indexing: ( ), f(x), x[i]
• the power operator **
• unary operators: unary +, unary - and ~
• multiplication group: *, /, //, %
• addition group: +, -
• shift group: <<, >>
• bitwise AND: &
• bitwise exclusive OR: ^
• bitwise OR: |
• comparisons: ==, !=, <, <=, >, >=, is, is not, in, not in
• the word not
• the word and
• the word or
• the conditional expression x if condition else y
• assignment and the walrus :=

Operators higher in the list group tighter. Two rules make the list easy to remember:

• Arithmetic is tighter than shifts, and shifts are tighter than the bitwise operators. So 1 << 2 + 1 is 1 << (2 + 1), which is 8.
• Comparisons are tighter than and and or, so a < b and c < d is (a < b) and (c < d).

Two rows in this table differ from Java and C. The bitwise & ranks above the comparisons in Python, and comparisons chain. Both points are shown below.

The traps in the middle of the table

The table has a few surprises. Each trap below is a place where the way the line looks is not the way Python groups it.

Shift and addition

1 << 2 + 1 looks like it means (1 << 2) + 1, which is 5. Python groups the addition first, so the line means 1 << (2 + 1), which is 8. The program below prints both forms side by side:

The output is:

D: 8
E: 5

Bitwise AND and equality

In Python, & ranks above ==. So flags & 4 == 4 is read as (flags & 4) == 4, which is what most people mean. The program below shows both forms give the same answer:

The output is:

True True

In Java, the equality operator ranks above &, so the same text means flags & (4 == 4) and fails to compile. A reader who knows Java may expect the failure. Write the brackets anyway, so the line says the same thing in every language.

Comparisons chain

A comparison such as 1 < 2 == True does not mean (1 < 2) == True in Python. Comparisons chain, so a < b == c means a < b and b == c. The middle value 2 is compared with True as well:

The output is:

G: False
G2: True
H: False

The first line is False, because 2 == True is False. The second line is True, because the brackets force 1 < 2 to become True first. This is the most surprising grouping in Python, and it is the reason to write brackets whenever two comparisons share a line.

Chains are useful too. 1 < 2 < 3 means 1 < 2 and 2 < 3, and the arithmetic lesson and the logic lesson both used that form. The difference is only in the middle value, which is compared on both sides.

Logical AND and logical OR

and ranks above or. So False or True and False means False or (True and False), which is False. The line below prints the result of the same grouping:

The output is:

I: False
I2: False

Both lines give False here, so this example does not show the difference. The difference appears with other inputs. Take True or False and False. The grouping True or (False and False) gives True, and the left-to-right reading (True or False) and False gives False. Python uses the first:

The output is:

True
False

Unary minus and the power operator

The power operator ** ranks above the unary minus. So -2 ** 2 means -(2 ** 2), which is -4, and not (-2) ** 2, which is 4. Write brackets when you want the square of a negative number:

The output is:

U: -4 4
V: -9 9 -6

The last value shows that unary minus binds tighter than *. The expression -3 * 2 is (-3) * 2, which is -6.

Conversions instead of casts

Python has no cast operator such as (double). A conversion is a function call, such as float(7). A call binds tightly, so in float(7) / 2 the conversion applies to 7 only, and the result is 3.5:

The output is:

F: 3.5
F2: 3.0

In G, the floor division happens first with two int values, so the result is 3, and the conversion changes the type afterwards.

The word not

The word not ranks below the comparisons. So not flag == False means not (flag == False), which is a negated comparison. Java's ! ranks above ==, so the same text there means (!flag) == false. For bools (the two values True and False) the two forms always give the same answer, but the grouping in the text is different. Write the brackets when the line is hard to read:

The output is:

K: False False False

The conditional expression

The conditional expression x if condition else y groups right to left, in the same way as a chain of else if. The line below is read as "big" if n > 3 else ("mid" if n > 1 else "small"):

The output is:

L: mid

A nested conditional expression is hard to read even when Python gets it right. For chains of three or more choices, an if and elif chain is clearer.

A worked example from start to finish

Here is one full run of the method on a new line, so you can see each step. The line is:

total = 1 if 2 * 3 + 4 << 1 > 10 else 0

Step 1: list the operators by rank. Unary: none here. Multiplication: *. Addition: +. Shift: <<. Comparison: >. Conditional: if else. Assignment: =.

Step 2: group the tightest operator first. 2 * 3 becomes one node.

Step 3: group the next tightest. (2 * 3) + 4 becomes a node.

Step 4: shift. The << takes the sum from step 3 on its left and 1 on its right. Its node is (((2 * 3) + 4) << 1).

Step 5: comparison. > compares that shift result with 10. Its node is ((((2 * 3) + 4) << 1) > 10).

Step 6: conditional. The condition is the comparison node, and the two choices are 1 and 0.

The final parenthesised form is:

1 if (((2 * 3) + 4) << 1) > 10 else 0

Run it:

The output is:

1

The shift gives (6 + 4) << 1, which is 20, and 20 > 10 is True, so the conditional gives 1.

Common mistakes

Mistake 1: reading the line left to right

People often group the leftmost operator first even when a tighter one is to its right. In a + b * c, the * groups first. If you read it left to right, you get (a + b) * c, which gives a different value. Always draw the tree, or put the parentheses in, before you trust the value.

Mistake 2: a comparison chain that reads as two tests

A line such as 0 <= x == y looks like a comparison followed by an equality test. It is a chain: 0 <= x and x == y. Read a chain as a set of tests that all have to hold, and write brackets when you want a different meaning.

Mistake 3: a conversion that covers too little

A conversion binds to the operand next to it. float(total) / count divides a float, which gives a fraction. float(total // count) divides two ints first and loses the fraction. The program below uses total = 7 and count = 2:

The output is:

float(total) / count = 3.5
float(total // count) = 3.0

Mistake 4: a shift that reads as a comparison

Some people write a << b + c and expect the shift to happen first. The addition happens first, as the earlier example shows. Use parentheses whenever a shift and an addition share a line.

Mistake 5: a long chain of conditional expressions

Chains like a if x else b if y else c if z else d are valid, but they are hard to check. When you find yourself counting else words, rewrite the code with if and elif.

Practice

Each exercise has its answer below it. Try the exercise on paper before you read the answer.

Exercise 1. Draw the tree for x + y * 2 - z. Then write the same expression with full parentheses.

Show the answer

The * groups y and 2 first. The + joins x and that product. The - joins the sum and z:

-
├── +
│   ├── x
│   └── *
│       ├── y
│       └── 2
└── z

Parenthesised form: ((x + (y * 2)) - z).

Exercise 2. Add the parentheses that show the grouping of a or b and c == d.

Show the answer

Equality groups first, then and, then or:

a or (b and (c == d))

Exercise 3. What does r = 2 + 3 << 1 store in r? Show the grouping first.

Show the answer

Addition ranks above shift, so the tree is (2 + 3) << 1. The sum is 5, and 5 shifted left by 1 is 10. The value of r is 10.

Exercise 4. Two programs compute an average with total set to 9 and count set to 4. One uses float(total) / count, the other uses float(total // count). What does each one print?

Show the answer

The first divides a float by an int, so the result is 2.25. The second divides two ints first, so the result is 2, which the conversion then turns into 2.0. The first prints 2.25 and the second prints 2.0.

Exercise 5. A student wrote if n & 1 == 0: to test whether n is even. Does it work in Python? Explain, and say what line you would write for a reader who knows Java.

Show the answer

It works in Python. The & ranks above ==, so the line means (n & 1) == 0. A reader who knows Java would read it as n & (1 == 0), which does not compile there, so the brackets if (n & 1) == 0: make the meaning clear in both languages.

Exercise 6. Predict the output of print(1 < 2 < 3 == 3).

Show the answer

It prints True. The chain means 1 < 2 and 2 < 3 and 3 == 3, and all three tests are True.

Summary

• A precedence tree puts the last operation at the top, with operators as branches and values as leaves.
• Operators with the same rank group left to right, except the power operator **, which groups right to left.
• Each node of the tree becomes one pair of parentheses, so a fully parenthesised line matches the tree.
• The traps are in the middle of the rank table: shifts below addition, & above comparisons, comparisons that chain, and and above or.
• Conversions such as float(x) bind to the operand next to them, so a conversion over a division needs its own parentheses.
• When a condition is hard to read, write the parenthesised form and check it against the original on a few inputs.