Programming

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 Type Handling is Critical Ensure all numbers are Number, not strings (Number(token)). Explicitly return Number(myStack.pop()) to avoid type errors. 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`. Handling Integer Division JS division (/) results in float, but integer division is expected. Use Math.trunc(b / a) to truncate towards zero. 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 };

Mar 21, 2025 - 12:14

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

Type Handling is Critical
- Ensure all numbers are Number, not strings (Number(token)).
- Explicitly return Number(myStack.pop()) to avoid type errors.
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`.

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

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
};