Evaluate Reverse Polish Notation Using Javascript

Sunday, 24 May 2015 | Posted by

Problem

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression.

For example:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Naive Approach

It can be solved using Stack
  1. Read array
  2. Push item into stack if it is number
  3. Pop numbers from stack, if item is operator, do the operation for those numbers and push into the stack
function evalRPN(tokens) {
    var returnValue = 0;
    var operators = "+-*/";

    var stack = [];
        for (var i=0; i<tokens.length; i++) {
                if (operators.indexOf(tokens[i]) == -1) {
            stack.push(tokens[i]);
        } else {
            var a = parseInt(stack.pop());
            var b = parseInt(stack.pop());
            switch (tokens[i]) {
            case "+":
                stack.push(a + b);
                break;
            case "-":
                stack.push(b - a);
                break;
            case "*":
                stack.push(a * b);
                break;
            case "/":
                stack.push(b / a);
                break;
            }
        }
    }

    returnValue = parseInt(stack.pop());

    return returnValue;
}

console.log(evalRPN(['2','1','+','3','*']));

Complexity

This algorithm takes O(n) space and O(n) time
Labels:,,

1 comment:

Subscribe to: Post Comments (Atom)

Blogroll

Popular Posts