Byte Sized Computer Science: Order of Operations

Celý článek

As a coder, you're probably pretty 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's no real reason to reinvent the wheel or try to implement these helpful functions on your own, it's still fun to take a peek under the hood and see what's going on!

Today we're going to take a closer look at one of these seemingly obvious concepts that we've probably all used at one point or another: the order of operations.

Say you want to evaluate this expression: 5 + 10 * 3. Of course you know that you should 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 a few different ways we can parse this equation, but some require a little more background than others.

In this tutorial, I'll show you one simple way to go about solving this.

This method requires that we first convert our equation into the correct format. Once it's in a more machine readable form, then we can go ahead and feed it through our parsing algorithm which will actually calculate it.

First I'll show you how to get the correct format so we can see what the end result should look like, then I'll walk you through the actual algorithm used to evaluate the expression. Just to keep things simple, we'll only be dealing with 4 operators in this example: addition, subtraction, multiplication, and division.

INFIX TO POSTFIX

Even though you may not realize it yet, most of you are probably already familiar with infix notation. The above expression, 5 + 10 * 3, is written in infix notation. It just means the operators fall in between the operands that they're acting upon.

What is Postfix Notation?

As mentioned earlier, we need to convert our equation into a format that the computer can easily understand. This format is called Reverse Polish Notation (also known as postfix notation).

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

This is important because when the machine is reading it, 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 in the previous example, 5 + 10 * 3 becomes 5 10 3 * +.

Now this may look weird and complicated, but there's actually a pretty simple way to arrive at this.

Human friendly way to convert from infix to postfix

1. Add in parentheses in order of precedence

    (5 + (10 * 3))

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

    (5 ( 10 3 *)+)

1. Now just drop the parentheses altogether, which leaves us with our expression in Reverse Polish Notation

    5 10 3 * +

Another example, just to show that the operators won't necessarily always be at the very end:

    8 _ 4 + 2
    ((8 _ 4) + 2)
    ((8 4 _) 2 +)
    8 4 _ 2 +

But again, this isn't really ideal for the computer to do! It still wouldn't know where to put the parentheses. Luckily for us, we have a pretty cool algorithm to produce the same results.

SHUNTING YARD ALGORITHM

What is it?

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

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

Queue - When we add data to a queue, we'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 we add a new element to the stack, it will be put on top (or at the front) instead of in the back. When we want to remove an item from the stack, we'll pop off the top item. Because new elements always go on top, those new ones will always be popped off first when we need to remove something. This can be remembered with the acronym LIFO -- last in, first out.

For this algorithm, assume we have one temporary stack to hold the operators (we'll call it "operator stack") and one queue that will hold the final result.

How it works

The Shunting Yard Algorithm follows 4 basic steps:

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

Evaluating our 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 our 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 our two arrays: one for the results output and one for the temporary operator stack.

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

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

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

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

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

Next up is 10, so we'll output immediately.

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

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

If we look above, we see the current top of the stack is +. So comparing the two, we know multiplication has higher precedence than addition.

This means we can just push it onto the top of the stack, which gives us:

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

Now we hit our final value, 3. Since this isn't an operator, we can just output it immediately.

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

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

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

And that's it! As you can see, it matches the above method where we just 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, we relied on our own meat brain's knowledge to make a choice between what to do next: determining which operator had higher precedence.

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

All we have to do is create an object that will essentially rank each operator. We'll give the multiplication and division operators a rank of 2 and the addition and subtraction operators a rank of 1.

When we code it up, we'll just 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. Just know that multiplication ranks higher than addition, so it has a higher number.

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

EVALUATING OUR REVERSE POLISH NOTATION (POSTFIX) EXPRESSION

We did it! We finally have our expression in Postfix Notation! So...now what?

Now we can use this format to actually EVALUATE it.

Algorithm to evaluate our expression

Here's how we'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* (see note)
5. Evaluate that expression using the current operator and the 2 operands that were popped
6. Push that result to the top of the stack
7. Repeat 2-7 until the expression is empty

Note - For example, multiplication is a binary operator, so if you are parsing and you hit a , then you know to pop off two operands. In our example, we're only dealing with binary operators, so we can just always pop off 2 operands when we see an operator. If we wanted to expand our example to handle all operators, we'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 above postfix notation expression: 5 10 3 * +.

First we start by pushing every operand onto the stack until we hit an operator.

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

    - push 5
    - push 10
    - push 3

    stack = [3, 10, 5]

So now we get to our first operator, *, which means it's time to start popping. We pop until we have two values.

    - pop 3
    - pop 10

Alright now we have our two operands, 3 and 10, so we will combine this with our operator, *, leaving us with 10 * 3.

    expression = [+]
    stack = [5]

    tempOperand1 = 3
    tempOperand2 = 10

    tempOperator = _

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

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

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

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

    expression = []
    stack = []

    tempOperand1 = 30
    tempOperand2 = 5

    tempOperator = + 

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

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

Going back to our original expression to parse for the next token, we find that it's empty!

    expression = []
    stack = [35]

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

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

BONUS ROUND

Polish Notation (Prefix notation)

The algorithm for evaluating an expression in Polish or Prefix Notation is essentially the same as above, except this time you will read from right to left. All we need is a small modification to the code and we can also evaluate for Polish Notation.

If we go back to our original method of adding parentheses and moving operators, we can convert to prefix notation in the same way we did postfix. Instead of moving the operators to the end of their operands, we'll move them to the beginning. Once we've done that, we can drop the parentheses altogether and then we have our Polish 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.

WRAP UP & WHAT'S NEXT?

I know following this stuff is tedious and sometimes hard to wrap your mind around, but I hope I was able to lay it out in an approachable way.

In the next article, we'll build out the calculator that converts from infix to postfix as well as a calculator that solves the postfix expression.

Let me know if you have any questions and thank you for following along!

Stay curious, friends!