Parse With The Shunting Yard Algorithm Using JavaScript

Anyone who knows how to program can probably solve a mathematical equation such as 5 + 3 * 6 - ( 5 / 3 ) + 7, but how might you get a computer to understand the appropriate order of operations? The equation I listed is in a format known as Infix Notation.

Infix Notation via Wikipedia:

Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands.

This format is not the most ideal to work with when attempting to solve.

Instead it is more appropriate to use format such as 5 3 6 * + 5 3 / - 7 + which is more commonly known as Postfix Notation or Reverse Polish Notation (RPN). This conversion can be accomplished by what is known as the Shunting Yard algorithm.

Shunting Yard via Wikipedia:

A method for parsing mathematical expressions specified in infix notation. It can be used to produce output in Reverse Polish notation (RPN).

We’re going to explore how to implement this algorithm using JavaScript. However, we won’t be solving the Reverse Polish Notation result in this article. We will only be parsing to RPN or Postfix Notation.

The logic behind this algorithm will be as follows:

1. Split the infix string based on any operator
2. Loop through the split infix token array
3. If the token is numeric add it to the postfix string
4. If the token is a ^*/+- operator check its level of precedence compared to the last found operator and pop from the operator stack appropriately
5. If the token is an opening parenthesis add it to the operator stack
6. If the token is a closing parenthesis, pop all operators from the stack up to the opening parenthesis
7. Pop all remaining operators into the postfix result string

In JavaScript we’re missing a few required functions, so it is a good idea to add them before we do anything:

String.prototype.isNumeric = function() {
    return !isNaN(parseFloat(this)) && isFinite(this);
}

The above code will check to see if the string is a numeric value. This is necessary in step 2a of our logic.

The next prototype we want to add is for cleaning up an array, removing indices with empty values:

Array.prototype.clean = function() {
    for(var i = 0; i < this.length; i++) {
        if(this[i] === "") {
            this.splice(i, 1);
        }
    }
    return this;
}

The above code is necessary because as you’ll see the splitting we’ll accomplish based on operators will leave a few empty values in the array. This will clean things up.

Now to take care of business. We’re going to create a MathSolver class with an infixToPostfix(equation) function:

function MathSolver() {

    this.infixToPostfix = function(infix) {
        var outputQueue = "";
        var operatorStack = [];
        var operators = {
            "^": {
                precedence: 4,
                associativity: "Right"
            },
            "/": {
                precedence: 3,
                associativity: "Left"
            },
            "*": {
                precedence: 3,
                associativity: "Left"
            },
            "+": {
                precedence: 2,
                associativity: "Left"
            },
            "-": {
                precedence: 2,
                associativity: "Left"
            }
        }
        infix = infix.replace(/\s+/g, "");
        infix = infix.split(/([\+\-\*\/\^\(\)])/).clean();
        for(var i = 0; i < infix.length; i++) {
            var token = infix[i];
            if(token.isNumeric()) {
                outputQueue += token + " ";
            } else if("^*/+-".indexOf(token) !== -1) {
                var o1 = token;
                var o2 = operatorStack[operatorStack.length - 1];
                while("^*/+-".indexOf(o2) !== -1 && ((operators[o1].associativity === "Left" && operators[o1].precedence <= operators[o2].precedence) || (operators[o1].associativity === "Right" && operators[o1].precedence < operators[o2].precedence))) {
                    outputQueue += operatorStack.pop() + " ";
                    o2 = operatorStack[operatorStack.length - 1];
                }
                operatorStack.push(o1);
            } else if(token === "(") {
                operatorStack.push(token);
            } else if(token === ")") {
                while(operatorStack[operatorStack.length - 1] !== "(") {
                    outputQueue += operatorStack.pop() + " ";
                }
                operatorStack.pop();
            }
        }
        while(operatorStack.length > 0) {
            outputQueue += operatorStack.pop() + " ";
        }
        return outputQueue;
    }

}

To demo this class you can do the following in a very simple index.html file:

<html>
    <head>
        <script src="app.js"></script>
        <script>
            var ms = new MathSolver();
            console.log(ms.infixToPostfix("5 + 3 * 6 - ( 5 / 3 ) + 7"));
        </script>
    </head>
    <body></body>
</html>

Play around with it and see it in action.

Conclusion

The Shunting Yard algorithm is a very good way to prepare mathematical equations for solving. It will convert your Infix Notation string into a more readable Postfix Notation / Reverse Polish Notation string. If you’re looking for a job in software engineering, this is also a very good interview question for an onsite interview because it will thoroughly test your problem solving skills.

If you think you can beat my version of the algorithm or have been asked a variant of this in an interview, I encourage you to share in the comments section.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.