Leetcode - 150. Evaluate Reverse Polish Notation

Evaluating Reverse Polish Notation (RPN) – Approach & Learnings

Approach

• Use a stack to process the tokens in a single pass.
• If the token is a number, push it onto the stack.
• If the token is an operator (+, -, *, /):
  • Pop two elements from the stack (a = pop(), b = pop()).
  • Apply the operator in the correct order (b op a).
  • Push the result back onto the stack.
• The final value left in the stack is the result.

Time Complexity

• O(N), where N is the number of tokens.
  • Each token is processed exactly once.
  • Stack operations (push/pop) take O(1) time each.

Key Learnings

1. Type Handling is Critical

   • Ensure all numbers are Number, not strings (Number(token)).
   • Explicitly return Number(myStack.pop()) to avoid type errors.

2. Correct Order of Operations

   • Since the stack is LIFO, pop order matters:

    let a = stack.pop();
    let b = stack.pop();
   

 - For subtraction and division, **order is crucial**: `b - a`, `b / a`.  

1. Handling Integer Division

   • JS division (/) results in float, but integer division is expected.
   • Use Math.trunc(b / a) to truncate towards zero.

2. Cleaner Operator Handling

   • Use a function dictionary for better readability:

    let operations = {
        "+": (a, b) => a + b,
        "-": (a, b) => b - a,
        "*": (a, b) => a * b,
        "/": (a, b) => Math.trunc(b / a)
    };
   

Code Implementation

var evalRPN = function(tokens) {
    let stack = [];

    let operations = {
        "+": (a, b) => b + a,
        "-": (a, b) => b - a,
        "*": (a, b) => b * a,
        "/": (a, b) => Math.trunc(b / a)  // Truncate towards zero
    };

    for (let token of tokens) {
        if (operations[token]) {
            let a = stack.pop();
            let b = stack.pop();
            stack.push(operations[token](Number(a), Number(b)));
        } else {
            stack.push(Number(token));
        }
    }
    return Number(stack.pop());  // Ensure correct return type
};