Evaluate Reverse Polish Notation

Loading...LeetCode

Problem

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

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

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example 1:

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

Example 2:

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

Example 3:

Input: tokens = ["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

Pseudocode

- first thing is to understand how RPN works
    - takes in an operation
    - then takes following two values
    - perform operation
    - return result
- use a stack to store values until operand is encountered
- use a map with operand as a key and associated operation as a function

Solution

// from solutions
// https://leetcode.com/problems/evaluate-reverse-polish-notation/solutions/486566/javascript-stack-solution/
// using stack to parse out numbers, when an operand is encountered, pop off two values from the stack and execute the function assigned in the object
// after performing the operation, the value is pushed back into the stack and repeated until the loop ends
function evalRPN(tokens) {
  const stack = [];
  const ops = {
    "+": (a, b) => a + b,
    "-": (a, b) => a - b,
    "*": (a, b) => a * b,
    "/": (a, b) => (a / b >= 0 ? Math.floor(a / b) : Math.ceil(a / b)),
  };

  for (const el of tokens) {
    if (ops[el]) {
      const secondVal = stack.pop();
      const firstVal = stack.pop();
      const operation = ops[el](firstVal, secondVal);
      stack.push(operation);
    } else {
      stack.push(Number(el));
    }
  }

  return stack.pop();
}

Time and Space Complexity

Time

• What did the code do

• Total -

Space

• What did the code do

• Total -