Precedence trees

Why this matters

A line such as a + b * c looks like it has one clear meaning, but the compiler must choose an order for the operations. Many people read it as "add a and b, then multiply by c". The compiler does the opposite: it multiplies b by c first. When a program gives a wrong answer, the cause is often a gap between the order the author had in mind and the order the compiler used.

The compiler follows fixed rules to choose the order. The rules are called precedence and associativity, and they are explained below. This lesson gives you a method that makes the rules visible. You draw the expression as a tree, then add parentheses so the code shows the same tree. A reader who sees the parentheses does not need to remember the rules.

The operators themselves (+, *, && and the others) are taught in the earlier lessons of this module. This lesson is only about how they group.

An expression is a tree

An expression is code that produces a value, such as 2 + 3 * 4. An operand is a value an operator works on. An operator is the symbol that does the work. In 2 + 3 * 4 the operands are 2, 3 and 4, and the operators are + and *.

A tree is a diagram with one point at the top, called the root. Lines go down from each point to its children. A point is called a node. A node with no children is a leaf. An expression becomes a tree when:

• each operand is a leaf,
• each operator is a node, and its operands hang below it,
• the root is the operator that runs last.

Here is 2 + 3 * 4 as a tree. Each line starts a node, and the indentation shows which node is the child of which.

+
|-- 2
`-- *
    |-- 3
    `-- 4

Read the tree from the bottom up. The * node has operands 3 and 4, so it runs first and produces 12. The + node has operands 2 and 12, so it runs next and produces 14. The next program checks that result and also shows how parentheses change it.

The first line uses the default order. The second line adds parentheses that match the tree, so it gives the same result. The third line adds parentheses that describe a different tree, so it gives a different result.

Output:

14
14
20

Precedence and associativity

Two rules decide the shape of the tree.

Precedence says which operator groups its operands first. An operator with higher precedence binds more tightly, which means it sits lower in the tree, closer to its operands. In the example above, * has higher precedence than +, so b * c forms before the + is applied.

Associativity decides the order when two operators have the same precedence. Most arithmetic operators group from left to right, so a - b - c means (a - b) - c. Assignment groups from right to left, so x = y = z means x = (y = z).

C++ has a fixed table of levels. The table below lists them from the tightest at the top to the loosest at the bottom. Operators on the same line share a level. The conditional operator ?: is left out because this module does not use it.

tightest   * / %                       left to right
           + -                         left to right
           << >>                       left to right
           < <= > >=                   left to right
           == !=                       left to right
           &                           left to right
           ^                           left to right
           |                           left to right
           &&                          left to right
           ||                          left to right
loosest    = and the compound forms    right to left

You do not need to memorise this table. The parentheses you write will show the grouping to any reader. The table matters most for the mistakes section, because some operators that look as if they should be grouped together are not.

Drawing a tree step by step

This method works for any expression, with or without parentheses.

1. Find the operator with the loosest precedence. It becomes the root, because it runs last.
2. If two or more operators share that loosest level, use their associativity. For a left-to-right level, the rightmost operator is the root. For a right-to-left level, the leftmost operator is the root.
3. Split the expression at the root. The part to the left and the part to the right each become a smaller expression.
4. Repeat steps 1 to 3 on each smaller expression, until you reach single operands.

Worked example 1: a mix of +, -, * and /

Take the expression a + b * c - d / e. Assume a is 1, b is 2, c is 3, d is 8 and e is 4.

Step 1. The loosest operators are + and -, which share a level and group from left to right. The rightmost of them is -, so - is the root.

Step 2. Split at the root. The left part is a + b * c, and the right part is d / e.

Step 3. In the left part, the loosest operator is +, so it is the root, with a on its left and b * c on its right. In the right part, the only operator is /.

Step 4. The finished tree looks like this:

-
|-- +
|   |-- a
|   `-- *
|       |-- b
|       `-- c
`-- /
    |-- d
    `-- e

Writing the tree as parentheses gives ((a + (b * c)) - (d / e)). The next program compares that result with a reader who ignores precedence and groups the first two operators.

Output:

tree 5
wrong grouping 0

The tree gives 5. The wrong grouping gives 0. Both programs have the same operators and the same operands, so only the grouping decides the answer.

Worked example 2: the same operator repeated

The subtraction a - b - c has two operators at the same level. Because they group from left to right, the tree is (a - b) - c. The rightmost - is the root, and its left child is the other -. The assignment x = y = z = 7 groups from right to left, so the leftmost = is the root, and it reads as x = (y = (z = 7)). The next program prints both cases.

The first two lines show the same answer, because they describe the same tree. The third line describes a different tree, a - (b - c), and it gives a different answer. The last line shows that the right-to-left grouping of assignment sets all three variables to 7.

Output:

3
3
9
7 7 7

Worked example 3: logical operators and a shift

Here is a condition with three parts: x > 0 && y > 0 || z == 1. The && operator is tighter than ||, so the root is ||. Its left child is the && node, which has the children x > 0 and y > 0. Its right child is z == 1. Written with parentheses, the tree is:

(((x > 0) && (y > 0)) || (z == 1))

The next program also includes a shift. In 3 << 1 + 1, the + binds more tightly than <<, so the expression means 3 << (1 + 1).

Output:

1
1
12

With these values, y > 0 is false, so the left side of || is false. The right side, z == 1, is true, so the whole condition is true. The result is 1, which is how C++ prints true through cout.

Adding parentheses that match the tree

Once you have the tree, you can write its parentheses. Start at the root. Wrap the left part and the right part in a pair of parentheses, then repeat for each part. Each operator gets one pair around its own operands. A single operand never needs a pair. The outermost pair around the whole expression is optional, but keeping it makes the top level easy to see.

For the expression in worked example 1, the process gives ((a + (b * c)) - (d / e)). The pair around b * c is needed to show that the multiplication happens first, even though the default order would do the same.

There is a second reason to add parentheses. Some grouping is correct by the table but hard to remember. A reader who sees a & b == c has to recall that == binds more tightly than &. Adding parentheses removes that step. The rule for your own code is simple: if a reader would have to check the table to be sure, add the parentheses.

Parentheses never change the value of a correct expression. They only make the intended tree visible. If you add them and the result changes, the tree you drew was wrong, and you should draw it again.

Checking a tree with a program

When you are unsure about a long expression, store each node in its own variable and print the results. Each variable holds the value of one subtree. If the pieces combine to the same value as the one-line expression, your tree matches what the compiler does.

Output:

left 7
right 2
whole 5
same as one line 5

The variables left and right are the two children of the root in the tree from worked example 1. The variable whole is the root itself. The last line uses the original expression, and it prints the same value, so the tree and the code agree. The split into variables can be removed once you trust the tree, but the values are useful while you learn.

Common mistakes

Reading left to right instead of by precedence

The most common mistake is to read a + b * c from left to right, as if the first operator always ran first. With a set to 2, b set to 3 and c set to 4, the left-to-right reading is (a + b) * c, which gives 20. The compiler gives 14. The first program in this lesson shows both values.

Fix: before you trust an expression that mixes two or more operators, draw its tree. The root is always the loosest operator, not the first one you see.

Bit operators below comparisons

The & operator is looser than ==. This trips up many people who test a single bit. The next program tests whether bit 2 of flags is clear.

Output:

0
1

The first line means flags & (MASK == 0). The comparison MASK == 0 is false, which is 0, so the expression becomes 3 & 0, which is 0. The second line adds parentheses that match the intended tree, (flags & MASK) == 0. It returns 1, which is the correct answer, because 3 & 4 is 0 and the bit is clear.

Compiling the same file with g++ -std=c++20 -Wall prints a warning for the first line. The warning names the exact problem:

example.cpp:7:27: warning: suggest parentheses around comparison in operand of ‘&’ [-Wparentheses]

Warnings from -Wall are worth reading. This one appears because the compiler suspects the grouping was not intended.

Assignment inside a condition

A single = stores a value. A double == compares two values. Writing one where you meant the other compiles, because both are valid C++. The next snippet is a common version of the error.

#include <iostream>
using namespace std;
 
int main() {
    int x = 3;
    if (x = 5) {
        cout << "inside the if" << endl;
    }
    return 0;
}

Compiling it with g++ -std=c++20 -Wall prints this warning, and the program then prints inside the if:

example.cpp:6:11: warning: suggest parentheses around assignment used as truth value [-Wparentheses]

The = stores 5 in x. The value of that assignment is 5, and any nonzero number counts as true in an if. So the body runs no matter what x held before. Writing if (x == 5) checks the value without changing it.

Shifts and addition

The + operator binds more tightly than <<. Someone who wants (1 << 2) + 1, which is 5, may write 1 << 2 + 1 and get 8. The expression means 1 << (2 + 1), which is 1 << 3, which is 8. Parentheses fix the meaning: (1 << 2) + 1.

Practice

Exercise 1. Draw the tree for int r = 10 - 2 * 3 + 8 / 4; and give the value of r.

Show the answer

The loosest operators are - and +. They group from left to right, so the rightmost one, +, is the root. Its left child is 10 - 2 * 3, and its right child is 8 / 4. The tree is:

+
|-- -
|   |-- 10
|   `-- *
|       |-- 2
|       `-- 3
`-- /
    |-- 8
    `-- 4

The value is (10 - 6) + 2, which is 6.

Exercise 2. Add the parentheses that match the default grouping of bool ok = a == 1 || b == 2 && c == 3;.

Show the answer

The && operator binds more tightly than ||, and == binds more tightly than both. The matching declaration is bool ok = ((a == 1) || ((b == 2) && (c == 3)));. With a set to 0, b set to 0 and c set to 1, the value of ok is false, which prints 0.

Exercise 3. If n is 16, what does int v = n >> 1 + 1; store in v?

Show the answer

The + binds more tightly than >>, so the expression is n >> (1 + 1), which is 16 >> 2. Shifting 16 right by 2 places gives 4. The value of v is 4.

Exercise 4. Let x be 4. What does if (x & 4 == 4) do, and how do you write the test correctly?

Show the answer

The == binds more tightly than &, so the condition means x & (4 == 4). The comparison 4 == 4 is 1, and 4 & 1 is 0. The condition is false, even though bit 2 of x is on. The correct test is if ((x & 4) == 4), which is true for x equal to 4.

Exercise 5. Draw the tree for int s = 2 * 3 << 1 + 1; and give the value of s.

Show the answer

The loosest operator is <<, so it is the root. Its left child is 2 * 3, and its right child is 1 + 1. The tree is:

<<
|-- *
|   |-- 2
|   `-- 3
`-- +
    |-- 1
    `-- 1

The value is 6 shifted left by 2 places, which is 24.

Summary

• An expression can be drawn as a tree, with operands as leaves and the loosest operator as the root.
• Higher precedence binds more tightly, so its operator sits lower in the tree.
• Associativity decides the order when operators share a level: most arithmetic groups left to right, and assignment groups right to left.
• Add parentheses that match the tree, especially when a reader would otherwise need the precedence table.
• Bit operators such as & and | are looser than comparisons, so x & 4 == 4 does not test bit 2.
• Read the warnings from -Wall, because they often point at a grouping mistake.