Understanding Order of Operations in Programming

Introduction

As a coder, you are probably used to telling computers what to do. Type up some code, run it, and the computer gets to work executing whatever command you gave it.

Even though we have this powerful reign over computers, there’s still a lot of magic constantly occurring in our code that we tend to overlook. This is especially true if you’re working with high-level languages with pre-built functions, as most of us are. And, of course, while there is no real reason to reinvent the wheel or try to implement these helpful functions on your own, it is still fun to take a peek under the hood and see what’s going on!

In this article, you will take a closer look at one of these concepts that you have probably all used at one point or another: the order of operations.

Say you want to evaluate this sample expression:

5 + 10 * 3

According to the mathematical order of operations, you would multiply 10 by 3 first and then add 5 to the product of that, but how exactly would you tell a computer to do this?

There are different ways you can parse this equation, but some require a little more background than others.

This tutorial will convert the equation into the correct format. Once it’s in a more machine-readable form, then you can feed it through your parsing algorithm which will calculate it. This tutorial will focus on four operators: addition, subtraction, multiplication, and division.

Understanding Infix to Postfix

Even though you may not realize it yet, you are probably already familiar with infix notation. The sample expression is written in infix notation:

5 + 10 * 3

It means the operators fall in between the operands that they’re acting upon.

What is Postfix Notation?

As mentioned earlier, you need to convert the equation into a format that the computer can understand. This format is called postfix notation.

Expressions written in postfix notation will have all operators following their operands.

This is important because when the machine is reading expressions in this format, it will never encounter an operator before the operands it’s acting on, which means it won’t have to go back and forth.

So the sample expression:

5 + 10 * 3

Becomes:

5 10 3 * +

This may look unusual, but there’s a methodology to arrive at this.

Human-Friendly Way to Convert from Infix to Postfix

Add in parentheses in order of precedence:

    (5 + (10 * 3))

Move every operator to the right, directly before its closing parenthesis:

    (5 (10 3 *) +)

Now drop the parentheses altogether, which leaves you with the expression in postfix notation:

    5 10 3 * +

Here is another example to show that the operators won’t necessarily always be at the end:

	8 * 4 + 2
	((8 * 4) + 2)
	((8 4 *) 2 +)
	8 4 * 2 +

Again, this is not ideal for the computer to do. It still wouldn’t know where to put the parentheses. Luckily, there is an algorithm to produce the same results.

Applying the Shunting Yard Algorithm

The Shunting Yard Algorithm was developed by Dijkstra as a means to convert infix notation to postfix notation.

Before you go any further, let’s quickly review the two data structures you’re going to be using here: a stack and a queue. You can use an array to hold both of these sets of data. The main difference comes from the order you’re adding and removing the data.

Queue: When you add data to a queue, you’re pushing it onto the back. Just imagine you’re getting in line for an event and every person in line is an element in the queue. When you walk up to the line, you’re automatically inserted into the back of the line. As the event starts letting people in (removing elements from the queue), they pull from the front of the line since those people have been there longer. You can remember this with the acronym FIFO: first in, first out.

Stack: Every time you add a new element to the stack, it will be put on top (or at the front) instead of in the back. When you want to remove an item from the stack, you’ll pop off the top item. Because new elements always go on top, those new ones will always be popped off first when you need to remove something. This can be remembered with the acronym LIFO: last in, first out.

For this algorithm, assume you have one temporary stack to hold the operators (operator stack) and one queue that will hold the final result.

How It Works

The Shunting Yard Algorithm follows four basic steps:

1. Parse the expression from left to right.
2. If you see an operand, output it to the results queue immediately.
3. If you see an operator:
   • If the operator stack is empty, push the incoming operator onto the operator stack.
   • If the incoming operator has higher precedence than what’s currently at top of the operator stack, push the incoming operator onto the top of the stack.
   • If the incoming operator has equal precedence, pop the top operator from the stack, output it to the queue, and push the incoming operator onto the stack.
   • If the incoming operator has lower precedence pop the top operator from the stack, output it to the queue, and test the incoming operator with the new top of the stack.
4. Once you have parsed the whole expression, pop all remaining tokens from the operator stack.

Evaluating an Infix Expression with the Shunting Yard Algorithm

It’s hard to make sense of those steps without seeing it in action, so let’s walk through the previous example and try to format it with the algorithm!

Convert this equation from infix notation to postfix notation:

5 + 10 * 3

Let’s set up your two arrays: one for the results output and one for the temporary operator stack:

    expression = 5 + 10 * 3
    output = []
    operator stack = []

First, you start reading the expression from left to right. So first up you have 5. Since this is an operand, you can output it immediately:

    expression = + 10 * 3
    output = [5]
    operator stack = []

Next, you see the +. The operator stack is empty, so you can push it there:

    expression = 10 * 3
    output = [5]
    operator stack = [+]

Next up is 10, so you’ll output immediately:

    expression = * 3
    output = [5, 10]
    operator stack = [+]

Now you hit another operator, *. Since the operator stack isn’t empty, you have to compare it to the current top of the operator stack to see which has higher precedence.

The current top of the stack is +. So comparing the two, you know multiplication has higher precedence than addition.

This means you can push it onto the top of the stack, which gives you:

    expression = 3
    output = [5, 10]
    operator stack = [*, +]

Now you hit your final value, 3. Since this isn’t an operator, you can output it immediately:

    expression is now empty
    output = [5, 10, 3]
    operator stack = [*, +]

Since the expression is now empty, all that remains is to pop all tokens from the operator stack and output them immediately. When you pop from the stack, you’re grabbing from the top, so first, you’ll take the * to push to the end of the queue, and then you’ll take the +.

    output = [5, 10, 3, *, +]

And that’s it! As you can see, it matches the previous method where you add parentheses, but this way is much easier for a computer to do.

Precedence Rules

You may have noticed there was one point where instead of using the algorithm to decide, you relied on our own knowledge to make a choice between what to do next: determining which operator had higher precedence.

It’s not important right now while you are understanding the concepts behind the algorithm, but when you’re writing the actual code to solve this, you’re going to have to build in some precedence rules.

You have to create an object that will essentially rank each operator. You’ll give the multiplication and division operators a rank of 2 and the addition and subtraction operators a rank of 1.

When you code it up, you’ll compare two operators by comparing their numerical rank. The actual numbers 1 and 2 here are arbitrary, so don’t get too caught up in that. Grasp the concept that multiplication ranks higher than addition, so it has a higher number.

    const precedence = {
        "*": 2,
        "/": 2,
        "+": 1,
        "-": 1
    };

Evaluating a Postfix Expression

You finally have the expression in postfix notation. Now, you can use this format to evaluate it.

Algorithm to Evaluate the Expression

Here’s how you’ll do it:

1. Start with an empty stack.
2. Parse the first token in the expression.
3. If it’s an operand, push it onto the stack.
4. If it’s an operator, pop off the appropriate number of operands from the stack into temporary variables. (For example, multiplication is a binary operator, so if you are parsing and you hit a multiplication operator, then you know to pop off two operands.)
5. Evaluate that expression using the current operator and the two operands that were popped.
6. Push that result to the top of the stack.
7. Repeat 2-7 until the expression is empty.

In the example, you’re only dealing with binary operators, so you can always pop off two operands when you see an operator. If you wanted to expand the example to handle all operators, you’d have to handle unary operators such as !.

Walking Through the Algorithm

Let’s walk through some pseudo-code where we use the algorithm to evaluate the sample postfix notation expression:

5 10 3 * +

First, you start by pushing every operand onto the stack until you hit an operator:

    expression = [5, 10, 3, *, +]

    - push 5
    - push 10
    - push 3

    stack = [3, 10, 5]

So now you get to your first operator, *, which means it’s time to start popping. You pop until you have two values:

    - pop 3
    - pop 10

Alright now you have your two operands, 3 and 10, so you will combine this with your operator, *, leaving you with 10 * 3:

    expression = [+]
    stack = [5]

    tempOperand1 = 3
    tempOperand2 = 10

	tempOperator = *

	eval(tempOperand1 + tempOperator + tempOperand2) // 3 * 10

You evaluate that, get 30, and then push this back onto the stack. You now have the following:

    expression = [+]
    stack = [30, 5]

So you start parsing the expression again and you immediately hit an operator. Again, you have to pop from the stack until you have two operands:

    expression = []
    stack = []

    tempOperand1 = 30
    tempOperand2 = 5

    tempOperator = + 

	eval(tempOperand1 + tempOperator + tempOperand2) // 30 + 5

You pop 30 and the 5 and you are ready to evaluate again. 5 + 30 gives you 35 and you can now push this back onto the stack.

Going back to your original expression to parse for the next token, you find that it’s empty!

    expression = []
    stack = [35]

This either means that you are done or that the original expression was malformed.

Let’s check by looking at your stack. It only has one value in it, so this means you are done and 35 is the final output of the original expression, 5 + 10 * 3.

Understanding Prefix Notation

The algorithm for evaluating an expression in prefix notation is essentially the same, except this time you will read from right to left. A small modification to the code and we can also evaluate for prefix notation.

If you go back to your original method of adding parentheses and moving operators, you can convert to prefix notation in the same way you did postfix. Instead of moving the operators to the end of their operands, you’ll move them to the beginning. Once you’ve done that, you can drop the parentheses altogether and then you have your prefix notation expression!

    5 + 10 * 3
    (5 + (10 * 3))
    (+ 5 (* 10 3))
    + 5 * 10 3

If you want to put your knowledge to the test, try to figure out how you’d do this algorithmically with a small modification to the Shunting Yard Algorithm.

Conclusion

In this tutorial, you’ve created an algorithm for converting expressions to postfix notation and tested it by evaluating an expression.