LeetCode - 150. Evaluate Reverse Polish Notation

Thoughts:

I choose stack to solve this problem.

Reverse Polish Notation means calculating top 2 numbers in a stack with an operator.

The time complexity will be O(n).

Thoughts visuzlization:

if encounter number, just push to stack

if encounter operator
pop top 2 numbers from the stack and use the operator for calculating a result
and the problem says the number should be trancated when divide them
then push to stack

tokens = ["4","13","5","/","+"]

stack = []
stack = [4]
stack = [4, 13]
stack = [4, 13, 5]
stack = [4, 2]
stack = [6]

Code:

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
  const stack = [];
  for (let token of tokens) {
    if (token === '+') {
      const num1 = stack.pop();
      const num2 = stack.pop();
      stack.push(num1 + num2);
    } else if (token === '-') {
      const num1 = stack.pop();
      const num2 = stack.pop();
      stack.push(num2 - num1);
    } else if (token === '*') {
      const num1 = stack.pop();
      const num2 = stack.pop();
      stack.push(num1 * num2);
    } else if (token === '/') {
      const num1 = stack.pop();
      const num2 = stack.pop();
      stack.push(Math.trunc(num2 / num1));
    } else {
      stack.push(parseInt(token));
    }
  }
  return stack.pop();
};

Reference

Original link

Stack data structure intro

Reverse Polish Notation