Our website is made possible by displaying online advertisements to our visitors. Please consider supporting us by disabling your ad blocker.

Evaluate A Reverse Polish Notation Equation With JavaScript

TwitterFacebookRedditLinkedInHacker News

Previously, I demonstrated how to convert an Infix Notation expression into Reverse Polish Notation using JavaScript, but I never explained how to evaluate the expression.

Reverse Polish Notation via Wikipedia:

A mathematical notation in which every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position. It is also known as postfix notation and is parenthesis-free as long as operator arities are fixed.

In this phase two article, we’re going to look at how to solve a mathematical expression that has been parsed into Reverse Polish Notation (RPN).

As a refresher, an Infix Notation expression looks like 5 + 3 * 6 - ( 5 / 3 ) + 7 which you’re probably familiar with from your time in school. Postfix Notation of the same expression can be seen as 5 3 6 * + 5 3 / - 7 + which we’re going to see is a little easier to solve than Infix.

To start things off, let’s go ahead and re-use the isNumeric() prototype we created in the Infix to Postfix tutorial.

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

Of course the above code isn’t a necessity depending on your implementation, but since it is available, we’re going to use it.

Now for the general logic behind evaluating RPN:

  1. Loop through all Postfix tokens
  2. If token is a numeric, then add to a stack
  3. If token is an operator, then pop two numerics from the stack and evaluate
  4. Push the evaluated value back into the stack
  5. If more than one value exists in the stack, our RPN expression is incorrect and return so
  6. If one value exists, return it because it is our solution

There really isn’t anything more to it.

function MathSolver() {

    this.solvePostfix = function(postfix) {
        var resultStack = [];
        postfix = postfix.split(" ");
        for(var i = 0; i < postfix.length; i++) {
            if(postfix[i].isNumeric()) {
                resultStack.push(postfix[i]);
            } else {
                var a = resultStack.pop();
                var b = resultStack.pop();
                if(postfix[i] === "+") {
                    resultStack.push(parseInt(a) + parseInt(b));
                } else if(postfix[i] === "-") {
                    resultStack.push(parseInt(b) - parseInt(a));
                } else if(postfix[i] === "*") {
                    resultStack.push(parseInt(a) * parseInt(b));
                } else if(postfix[i] === "/") {
                    resultStack.push(parseInt(b) / parseInt(a));
                } else if(postfix[i] === "^") {
                    resultStack.push(Math.pow(parseInt(b), parseInt(a)));
                }
            }
        }
        if(resultStack.length > 1) {
            return "error";
        } else {
            return resultStack.pop();
        }
    }

}

Again we’re using a the MathSolver class we used in the previous tutorial.

As you can see it was incredibly simple because we didn’t need to worry about order of operations or anything we took care of in the Infix conversion.

Conclusion

We previously saw how to create a Reverse Polish Notation expression, and now we’ve seen how to solve one. Next time we might visit how to create a calculator application using the things we learned. If you’re interviewing for a software engineering position, this could very well be one of the questions asked because it demonstrates your ability to think logically and creatively.

If you think you can beat my implementation or were asked about something similar in an interview, share your experience in the comments section.

A video version of this article can be seen below.

Nic Raboy

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.