150. Evaluate Reverse Polish Notation

Difficulty:
Related Topics:
Similar Questions:

Problem

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Solution

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
  var stack = [];
  var len = tokens.length;
  var n1 = 0;
  var n2 = 0;
  var n3 = 0;
  var token = '';
  for (var i = 0; i < len; i++) {
    token = tokens[i];
    switch (token) {
      case '+':
        stack.push(stack.pop() + stack.pop());
        break;
      case '-':
        n1 = stack.pop();
        n2 = stack.pop();
        stack.push(n2 - n1);
        break;
      case '*':
        stack.push(stack.pop() * stack.pop());
        break;
      case '/':
        n1 = stack.pop();
        n2 = stack.pop();
        n3 = n2 / n1;
        stack.push(n3 > 0 ? Math.floor(n3) : Math.ceil(n3));
        break;
      default:
        stack.push(Number(token));
    }
  }
  return stack.pop();
};

Explain:

nope.

Complexity: