Mastering the Order of Operations in Programming

As programmers, we have the power to make computers execute our commands. However, even when we’re in control, there’s often invisible magic happening within the code, especially when working with high-level languages that offer pre-built functions, as most of us do.

In this article, we’ll take a closer look at a concept you’ve probably used before: the order of operations.

Imagine you want to evaluate this example expression:

5 + 10 * 3

According to the mathematical order of operations, you would first multiply 10 by 3 and then add 5 to the product. But how exactly would you teach a computer to do this? There are various ways to parse this expression, but some require more background knowledge than others.

This tutorial will transform the expression into the right format. Once it’s in a machine-readable form, you can feed it into your parsing algorithm, which will compute it. This tutorial focuses on four operators: addition, subtraction, multiplication, and division.

Understanding Infix Notation

You might not have noticed it, but you’re probably already familiar with infix notation. The example expression is written in infix notation:

5 + 10 * 3<

This means that operators are placed between the operands they operate on.

What is Postfix Notation?

As mentioned earlier, you need to convert the expression into a format that the computer can understand. This format is called postfix notation. Expressions written in postfix notation have all operators following their operands. This is crucial because when the machine reads expressions in this format, it will never encounter an operator before encountering the operands it operates on, meaning it doesn’t need to backtrack.

The example expression:

5 + 10 * 3

is transformed into:

5 10 3 * +

It might look unusual, but there’s a methodology to arrive at this result.

User-Friendly Conversion from Infix to Postfix

Insert parentheses in order of precedence:

(5 + (10 * 3))

Move each operator to the right, directly in front of its closing parenthesis:

(5 (10 3 *) +)

Remove the parentheses, and you get the expression in postfix notation:

5 10 3 * +

Here’s another example to show that operators don’t necessarily always come at the end:

8 * 4 + 2

((8 * 4) + 2)

((8 4 *) 2 +)

8 4 * 2 +

This is not ideal for the computer either. It still wouldn’t know where to place the parentheses. Fortunately, there’s an algorithm to achieve the same results.

Applying the Shunting Yard Algorithm

The Shunting Yard Algorithm was developed by Dijkstra to convert infix notation to postfix notation. Before moving forward, let’s briefly review the two data structures you’ll be using here: a stack and a queue. You can use an array to store both data sets. The main difference lies in the order in which you add and remove data.

Queue:

When you insert data into a queue, you add it to the back. Think of it as standing in a line for an event, and each person in line is an element in the queue. When you join the line, you automatically get added to the back. When the event starts, and people are let into the event (elements are removed from the queue), they are pulled from the front of the line because those people have been waiting 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 goes on top (or at the front) rather than the back. When you want to remove an element from the stack, you pop off the top element. Since new elements always end up on top, they are the first to be removed when you want to take something off. This can be remembered with the acronym LIFO: “Last In, First Out.”

Note: The rest of this tutorial will use the terms “push” and “pop” for stacks. A “push” action refers to adding a new element on top of the stack, and a “pop” action refers to removing the most recently added element from the top of the stack.

For this algorithm, you’ll assume that you have a source (or input) expression in infix notation, a stack to hold operators, and a queue for the output. The goal is to read the input expression, manipulate the operators with the stack, and produce an output in postfix notation in the queue.

However, you will not be implementing the actual algorithm here. For that, you would require a much more detailed guide or reference to the algorithm.

Wrapping up

The Shunting Yard Algorithm is a powerful tool that simplifies the task of converting infix expressions into postfix notation. While the initial introduction to postfix may seem a bit odd to those accustomed to infix, the logic behind it is sound and has been used in many computer systems over the years. As always, the key is practice and understanding the underlying principles, and then the application becomes much easier.

So, the next time you find yourself working with expressions, remember this algorithm and the simple logic behind the transformation. Good luck and happy coding! Mastering the Order of Operations