Between humans and computers: A tale of two notations

Photo by iSawRed on Unsplash

🔗 This article is part of the series: What do programmers and computers do?

Let me start with a simple mathematical expression.

(3 ⋅ 4 + 8) ⋅ (16 - 2 ⋅ 7)

Please spend 10 seconds and evaluate this in your head. It shouldn’t take you more than that. As you do that, pay close attention to the order of operations you did to reach the result.

Observing and evaluating our mental models when we do things is very useful.

There are, of course, multiple ways to do this, but I did it this way.

1) 3 ⋅ 4 = 12
2) 12 + 8 = 20 
3) Remembered 20 as the result of the first parenthesized expression
4) 2 ⋅ 7 = 14 
5) 16 - 14 = 2
6) Recalled 20 from an earlier step
6) 20 ⋅ 2 = 40

Now, why did I do it this way?

Why didn’t I, for instance, first add 8 to 4?

You may say — because multiplication takes precedence over addition.

Or why didn’t I start by multiplying 8 and 16?

You may say — because there are some parentheses in between.

In both cases, you’d be right.

And here’s my first point:

When we evaluate mathematical expressions, we have some assumptions about how they work; we follow specific rules to interpret them.

One of those rules is that different operations have different priorities — some operations should be evaluated before others.

The other rule is that the entire expression within parentheses should be treated as a whole in the outer context. In my example, all parts of the expression are numbers, so we evaluate each parenthesized expression to a single value and then use them in the outermost multiplication instead of their respective parenthesized expressions.

OK, but who set these rules?

I know very little about the history of mathematical notations, but the answer is — it doesn’t matter.

What does matter is that we all agree on the rules so that we all get the same results when we evaluate these things on our own. The other thing that matters is that these rules are tied to how we write the expressions (the notation).

Because of these rules and the notation we use (the infix notation), we can’t just drop the parentheses.

3 ⋅ 4 + 8 ⋅ 16 - 2 ⋅ 7 =
12 + 8 ⋅ 16 - 2 ⋅ 7 =
12 + 128 - 2 ⋅ 7 =
12 + 128 - 14 = 
140 - 14 = 
126

Or worse — ignore the operation precedence and just evaluate the operations from left to right.

3 ⋅ 4 + 8 ⋅ 16 - 2 ⋅ 7 = 
12 + 8 ⋅ 16 - 2 ⋅ 7 =
20 ⋅ 16 - 2 ⋅ 7 =
320 - 2 ⋅ 7 =
318 ⋅ 7 =
2226

Whenever we change some rules, we could end up with a different (wrong) result.

Now, let me write the same expression another way, in a different notation:

3 4 ⋅ 8 + 16 2 7 ⋅ - ⋅

Wait, what?! 😕

How is this useful, you may ask?

And how is it even the same expression?!

Understanding what’s happening is more complicated than our first expression with parentheses. Why would you ever want to write math expressions this way?

Well, you wouldn’t.

But a computer would.

This notation has a different set of rules than our initial notation, so it’s necessary to know those rules to make sense of its expressions.

Every notation comes with its own rules governing how to interpret expressions written in it.

But before I explain why this notation is useful, let me share yet another notation with you, a more visual one. Here it is:

Mathematical expression tree

This is a tree structure. A tree starts with a root node (at the top), and each node in a tree represents either a value or an operation to be performed on its subnodes (also called child nodes).

We can pick an operator node with only value nodes and replace it with the result obtained by performing that operation on its corresponding subnodes. For example, we can replace the multiplication node that has 2 and 7 as subnodes and replace it with the result, which is 14. Like this:

Reduced mathematical expression tree

If we keep doing this until we replace all the operators, we’ll end up with a single value node. That will be the result of the whole mathematical expression.

Why is this visual (or structural) notation useful?

Well, it has a couple of interesting properties.

The first is the fact that parentheses are no longer needed. The precedence of the operations is ingrained in how we organize the tree nodes. The lack of parentheses makes the whole expression have fewer tokens. The original expression has 15 tokens (values, operators, parentheses). The tree structure has 11 tokens (nodes). The number of tokens will be relevant in our future explorations.

The other interesting property is its structure. With a tree structure, we can use a simple stack data structure to evaluate the whole expression using just two different operations. Before I get to these two operations, let me do something interesting with this tree.

I’ll post-order traverse this tree.

For those less experienced with this structure, a tree traversal is a journey across the tree nodes in a particular order. We always start from a root node. Post-order (post meaning after) means that the node is visited only after all its subnodes are visited. This is done recursively, which means that as we start from a root node, we look to see if it has subnodes, and if it does, we first visit them, and if any of those subnodes have subnodes of their own, we visit them first and so on and so on… When we’re done visiting all subnodes of a node, we visit the node itself.

If you apply the above process to our example tree, you’ll get the following expression:

3 4 ⋅ 8 + 16 2 7 ⋅ - ⋅

If you look closely, you will see it’s the same expression I shared previously. The one that makes sense only for computers, remember?

Now is the time to return to the computer evaluation of mathematical expressions.

We can now define an algorithm that scans the tokens from left to right and does the following:

• If the token is a value, push it onto the stack.
• If the token is an operator (of arity N), pop N values from the stack and perform the operation defined by the operator. Push the result of the operation onto the stack.

These two rules tell us how to interpret expressions in this new notation (postfix notation or Reverse Polish Notation).

Here’s the process performed on our expression. The first line shows the expression with a currently read token put in brackets. The second line shows the stack state after the token is read and the corresponding action is taken.

3 4 ⋅ 8 + 16 2 7 ⋅ - ⋅
STACK: empty

[3] 4 ⋅ 8 + 16 2 7 ⋅ - ⋅
STACK: 3

3 [4] ⋅ 8 + 16 2 7 ⋅ - ⋅
STACK: 3 4

3 4 [⋅] 8 + 16 2 7 ⋅ - ⋅
STACK: 12

3 4 ⋅ [8] + 16 2 7 ⋅ - ⋅
STACK: 12 8

3 4 ⋅ 8 [+] 16 2 7 ⋅ - ⋅
STACK: 20

3 4 ⋅ 8 + [16] 2 7 ⋅ - ⋅
STACK: 20 16

3 4 ⋅ 8 + 16 [2] 7 ⋅ - ⋅
STACK: 20 16 2

3 4 ⋅ 8 + 16 2 [7] ⋅ - ⋅
STACK: 20 16 2 7

3 4 ⋅ 8 + 16 2 7 [⋅] - ⋅
STACK: 20 16 14

3 4 ⋅ 8 + 16 2 7 ⋅ [-] ⋅
STACK: 20 2

3 4 ⋅ 8 + 16 2 7 ⋅ - [⋅]
STACK: 40

As you can see, when an expression is written in a convenient form, it’s trivial to write an algorithm to calculate the result.

For us humans, the convenient form is the infix notation because it groups things in a way that we find comprehensible. For computers, a more convenient one is the postfix notation. Of course, some algorithms can read the infix notation directly, token by token. Still, in reality, they either first convert the expression from the infix to the postfix (Shunting Yard algorithm) or perform similar conversion steps as they go.

📖 Off topic. During my university years, I had an HP 33s calculator. It had a Reverse Polish Notation mode. It was confusing at first, but after a couple of days of practice, I was at least 30% more efficient than when I used the typical algebraic method — both in speed and accuracy. I never looked back.

If you have an Android phone and use a calculator often, I strongly suggest the RealCalc app. It has an RPN mode, and it’s incredible. (disclaimer: they did not pay me to advertise the app 😉). I don’t use iPhones, but I’m pretty sure there are calc apps with RPN support for iOS, too.

Try it out.

✅ Let me summarize the article into the most essential points:

• Pay attention to the mental models you have. It will help you understand, abstract, and optimize your thoughts.
• Every notation (mathematical or otherwise) has to have its own set of rules that govern how to interpret what is written in it.
• Using the proper notation for a job makes things simpler and more efficient for humans and computers.

In a follow-up article, we’ll explore how these thoughts apply to programming languages.