Beyond BODMAS: The Power of Polish and Reverse Polish Notation
An Alternative Way of Writing Mathematical Expressions

I was working on a project where I needed to implement a new feature for an app. The feature would allow users to fetch documents from a database based on provided parameters. One of these parameters was the search keywords. It seemed simple enough at first - users would pass a value for the parameter, like keywords= "hello", and the server would fetch all the documents with the word "hello" in them.

But then, someone asked if they could search for multiple keywords in a document. No problem, I thought. I allowed users to pass multiple keywords as a string, like keywords="hello there". This would return all the documents with both "hello" and "there" in them.

Then, someone else came along and asked if they could search for a document with one keyword in it and the other keyword not in it. With a coy smile and a purple top hat, they asked if there was a solution. "Add an exclamation mark in front of it, you silly!" I said. And just like that, when a user passed keywords= "hello !there", they would get all the documents with "hello" in them and "there" not.

Another person asked if they could search for multiple keywords and get all the documents with any of the keywords in them. They wanted to broaden their search. This request seemed reasonable, so I allowed users to pass multiple keywords as a string, separated by a comma. If a user passed keywords= "hello, there", they would get all the documents with either "hello" or "there" in them.

It seemed like I had covered everything anyone could possibly need to create a query. The parsing logic seemed complete. Use a space for AND, a comma for OR and an exclamation for NOT. So, keywords= "hello there, general !kenobi" will translate to hello AND there OR general AND NOT kenobi. Just replace all the words in the expression with a "True" if the word is in the document and with a "False" if not. If the expression evaluates to "True", then that document is returned.

I thought I have covered all the bases, but as it turns out, I was wrong. With implicit precedence of "NOT" over "AND" over "OR", I could only create queries with limited complexity. What if I wanted to make a query like ((old AND ben) OR (obi AND van) OR general) AND kenobi, I had to write keywords= "old ben kenobi, obi van kenobi, general kenobi" which seemed unnecessarily long and repetitive. If the query becomes very complex, the expression will become very very long with a lot of repetitions.

I considered enabling users to write queries with brackets, as it is a familiar format and would make the queries more explicit. However, implementing a parser for this type of expression presents a significant challenge. The parser would need to analyze the query multiple times to determine which operations to evaluate first, making it difficult for the computer to parse. Although it would be easy for users to write queries in this format, as a self-proclaimed lazy person, I'm hesitant to undertake the task of writing such a complicated parser.

However, there is a solution to this problem, and it comes in the form of prefix notation. Instead of writing expressions with brackets, prefix notation uses operators before the operands, eliminating the need for parentheses altogether. This may seem like a weird concept at first, but once you get the hang of it, prefix notation can simplify the queries and also make them easier to parse for computers. In the following sections, we will explore the prefix and postfix notation and how it can be used to create efficient mathematical expressions.

via GIPHY

Normally, for common operators like "+ - / *", we use infix notation meaning the operator is placed between two operands. For example 2 + 3, here the plus sign is in between 2 and 3. But in the prefix notation, the operator comes before the operands. So the same expression will be written as + 2 3. This might seem strange at first, but think about how we write functions in most programming languages: we put the function name before the parameters. Like add(2,3). And as long as the number of parameters is fixed, we don't need to use brackets.

This Prefix Notation is also known as the Polish Notation, named after the nationality of Jan Łukasiewicz, the mathematician who invented it. Guess the country where he is from…

When we read a prefix expression from left to right, we can apply the operator to the next two elements in the expression if they are operands. For example, the expression + 2 - 5 1 becomes + 2 4, which equals 6. It's important to note that the minus sign here is an operator and not representing a negative number.

It is important to note that for the non-commutative operators, the order of oparands matters in prefix notation. For example in - 6 3, 3 is subtracted from 6 and / 10 5 10 is divided by 5.

via GIPHY

In our case, we can transform the expression obi AND kenobi in prefix notation as AND obi kenobi where AND is the operator and obi and kenobi are the operands. Even better, we can take the expression ((old AND ben) OR (obi AND van) OR general) AND kenobi and write it in prefix notation as AND OR OR AND old ben AND obi van general kenobi. That's right, we just solved two problems with infix notation: no more need for pesky parentheses and no more repeated expressions! Can I get a virtual high-five? 🙌🏼

Here are some nice observations about prefix notation:

• Expression always starts with an operator and ends with an operand.
• The operators are more concentrated towards the left side of the expression.
• The operands are concentrated towards the right side of the expression.
• The order of the operation is from right to left, i.e. the right-most operator is evaluated first, then the next and then the next…

This makes the implementation of a computer program to evaluate such expressions quite simple. Neither you need brackets nor do you need a priority of which operator gets precedence over the other. The evaluation algorithm, with the use of a memory stack, can be explained like this:

• Break the string expression in tokens and start from the rightmost token.
• If the token is an operand, push it to the stack.
• If the token is an operator and that operator needs N operands to work on then:
  • Pop the last N operands from the stack.
  • Apply the operation by maintaining the order of the operands.
  • Push the result back on the stack.
• Repeat until all of the tokens are used up.
• The last remaining value on the stack is the answer.

Simple as that. To make sure that the operands are in correct order, start with the operator and write the popped elements from left to right. Let's look at an example here. Consider the expression in infix notattion ((9 - 5) * 8 / 2) + (6 - 3) * 2 * 2, which evaluates to 28. We can solve this in prefix notation, using the above algorithm, as follows:

Prefix Notation: + / * - 9 5 8 2 * * - 6 3 2 2
Step  1: 2                              push     2   to stack Stack= 2
Step  2: 2                              push     2   to stack Stack= 2 2
Step  3: 3                              push     3   to stack Stack= 2 2 3
Step  4: 6                              push     6   to stack Stack= 2 2 3 6
Step  5: - pop  6 and  3 from stack and push - 6 3   to stack Stack= 2 2 3    # Note the order of poped tokens
Step  6: * pop  3 and  2 from stack and push * 3 2   to stack Stack= 2 6
Step  7: * pop  6 and  2 from stack and push * 6 2   to stack Stack= 12
Step  8: 2                              push     2   to stack Stack= 12 2
Step  9: 8                              push     8   to stack Stack= 12 2 8
Step 10: 5                              push     5   to stack Stack= 12 2 8 5
Step 11: 9                              push     9   to stack Stack= 12 2 8 5 9
Step 12: - pop  9 and  5 from stack and push - 9 5   to stack Stack= 12 2 8 4
Step 13: * pop  8 and  4 from the stack push * 8 4   to stack Stack= 12 2 32
Step 14: / pop 20 and  2 from the stack push / 32 2  to stack Stack= 12 16
Step 15: + pop 12 and 16 from stack and push + 12 16 to stack Stack= 28

Simple as that. If we have to implement an algo for infix notation, we would have to go over the whole expression back and forth to find the operator with the highest precedence to evaluate before the rest (based on the famous BODMAS rule). It will be way more complicated to implement this using a memory stack. On the other hand, in the prefix notation; we go over the expression, one token at a time, from right to left and only once. No more hidden steps. Easy peasy.

via GIPHY

Now, assume that we want to extend the above expression and add + * 2 3 1 to it. In that case we can prepend a + + * 2 3 1 to the original expression resulting in + + * 2 3 1 + / * - 9 5 8 2 * * - 6 3 2 2. And as we are evaluating it from right to left, we do not have to restart the algo even if we update the expression in the middle. We will see that in the next section, where we'll learn about The Postfix Notation.

Let me introduce the hippy cousin of Polish notation, the Reverse Polish Notation. It is just Polish notation but in reverse. As opposed to the prefix notation, in postfix, we write the operator after the operands for example the infix expression 2 + 3 will become 2 3 + in postfix. And our logical expression ((old AND ben) OR (obi AND van) OR general) AND kenobi in postfix will become old ben AND obi van AND OR general OR kenobi AND. Notice that in the postfix expression

• Expression always starts with an operand and ends with an operator.
• The operators are more concentrated towards the right side of the expression.
• The operands are concentrated towards the left side of the expression.
• The order of evaluation of operators is from left to right.

Left to right!!! Makes more sense now. We also read left to right (in most languages). Exactly the reverse of prefix notation. There is a reason it is called Reverse Polish Notation. The algorithm to evaluate postfix expression is very similar to that of prefix expression, just reverse the order:

• Break the string expression in tokens and start from the left.
• The rest is the same as before 😉

Here also, the order of operands matter when using non-commutative operators. When popping tokens from stack, write the operator first and go right to left with operands. That way you make sure the order is correct. Let us look at the same example of infix expression ((9 - 5) * 8 / 2) + (6 - 3) * 2 * 2 and solve it in postfix:

Prefix Notation: 9 5 - 8 * 2 / 6 3 - 2 * 2 * +
Step  1: 9                              push     9   to stack Stack= 9       #Like step 11 
Step  2: 5                              push     5   to stack Stack= 9 5     #Like step 10
Step  3: - pop  9 and  5 from stack and push 9 5 -   to stack Stack= 4       #Like step 12  # Note the order of poped tokens
Step  4: 8                              push     8   to stack Stack= 4 8     #Like step 9
Step  5: * pop  8 and  4 from stack and push 8 4 *   to stack Stack= 32      #Like step 13
Step  6: 2                              push     2   to stack Stack= 32 2    #Like step 8
Step  7: / pop 32 and  2 from stack and push 32 2 /  to stack Stack= 16      #Like step 14
Step  8: 6                              push     6   to stack Stack= 16 6    #Like step 4
Step  9: 3                              push     3   to stack Stack= 16 6 3  #Like step 3
Step 10: - pop  6 and  3 from stack and push 6 3 -   to stack Stack= 16 3    #Like step 5
Step 11: 2                              push     2   to stack Stack= 16 3 2  #Like step 1
Step 12: * pop  3 and  2 from stack and push 3 2 *   to stack Stack= 16 6    #Like step 6
Step 13: 2                              push     2   to stack Stack= 16 6 2  #Like step 2
Step 14: * pop  6 and  2 from stack and push 6 2 *   to stack Stack= 16 12   #Like step 7
Step 15: + pop 16 and 12 from stack and push 16 12 + to stack Stack= 28      #Like step 15

Notice how similar it is to the steps of prefix notation. Only the stack looks different and the order of operation is jumbled up. Now let's say that we already evaluated till step 14 and we want to add the expression 2 3 * 1 + (i.e. 2*3 + 1 in infix), we just update the expression and continue our steps without having to restart:

Prefix Notation: 9 5 - 8 * 2 / 6 3 - 2 * 2 * +
Step 14: * pop  6 and  2 from stack and push * 6 2   to stack Stack= 16 12
Updated Expression: 9 5 - 8 * 2 / 6 3 - 2 * 2 * + 2 3 * 1 + +
Step 15: + pop 16 and 12 from stack and push + 16 12 to stack Stack= 28
Step 16: 2                              push     2   to stack Stack= 28 2
Step 17: 3                              push     3   to stack Stack= 28 2 3
Step 18: * pop  2 and  3 from stack and push * 2 3   to stack Stack= 28 6
Step 19: 1                              push     1   to stack Stack= 28 6 1
Step 20: + pop  6 and  1 from stack and push + 6 1   to stack Stack= 28 7
Step 21: + pop 28 and  7 from stack and push + 28 7  to stack Stack= 35

That is the magic of prefixes and postfix notation. Super simple implementation algorithm that we can stop in the middle, update the expression and continue. But wait, there is still desert 😋.

Did you know about the additional benefits the prefix and postfix notation have? They allow for Currying. Currying is a concept from functional programming that lets us apply functions (in our case operators) partially and create new functions from it. Here's an example: In prefix notation, let's define X = + 3. This means that X is an operator that takes one operand and adds 3 to it. So X 2 would be equal to + 3 2 which is equal to 5. We can use X as a partially applied addition. In postfix notation, this would be written as X = 3 + and 2 X would be 2 3 + which is 5. Unfortunately, this isn't possible in infix notation. As Łukasiewicz said, prefix notation makes it easier to write and prove theorems! True that.

So, there we have it. A different way of writing mathematical expressions that:

1. Do not require any brackets.
2. Avoids repetition of terms.
3. Easy to implement parsing algorithm.
4. Easy to adapt to modification of the expression on the fly.
5. Allows partial application of operator or Currying.
6. And difficult to write and comprehend by humans. Wait. Noooooooo.

Our human brains have become so accustomed to using brackets in math expressions that it would be difficult to switch to prefix or postfix notations overnight. After all, the majority of the world uses infix notation, and it's what most people are comfortable with. It's intuitive and easier to understand, especially for those without a strong math background. So for my use case, instead of forcing users to adopt postfix or prefix notation, we can stick to the infix notation but without brackets. That way it will be easier for users to understand and write and simple for computers to parse. The only downside is that the user has to write a query in an expanded form. I guess that is okay. We cannot have our cake and eat it too.

Speaking of eating, I'm trying to decide what to eat for dinner tonight. The restaurant next to my house serves and and and burgers fries milkshakes not and salads sushi 😉