While this tutorial has content that we believe is of great benefit to our community, we have not yet tested or edited it to ensure you have an error-free learning experience. It's on our list, and we're working on it! You can help us out by using the "report an issue" button at the bottom of the tutorial.

Introduction

As a coder, you’re 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’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. According to the mathematical order of operations, 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, you’ll see how 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 four 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 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 in the previous example, 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

  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 postfix 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 +

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 an algorithm to produce the same results.

Shunting Yard Algorithm

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 four 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:

    a. If the operator stack is empty, push the incoming operator onto the operator stack.

    b. 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.

    c. If the incoming operator has equal precendence, pop the top operator from the stack, output it to the queue, and push the incoming operator onto the stack.

    d. 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 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 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 Postfix Expression

We finally have our expression in Postfix Notation. Now we can use this format to 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. (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 our example, we’re only dealing with binary operators, so we can just always pop off two 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.

Prefix Notation

The algorithm for evaluating an expression in 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 prefix 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 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.

0 Comments

Creative Commons License