0150. Evaluate Reverse Polish Notation

leetcode

Problem Overview

The problem involves evaluating an arithmetic expression in Reverse Polish Notation (RPN). In RPN, operators follow their operands, which eliminates the need for parentheses to denote operation precedence. The task is to evaluate the expression using a stack data structure.

Solution Outline

Preferred Structure: Utilize a stack to keep track of numbers.
Brute Force vs Optimal Solution:
- Brute Force: Directly evaluate using multiple passes or without using a stack.
- Optimal: Use a single stack to efficiently process the expression in one pass.
Algorithm Choice: A stack-based approach ensures O(n) time complexity where n is the number of tokens in the input.

/**
 * Evaluate the value of an arithmetic expression in Reverse Polish Notation.
 * @param {string[]} tokens - An array of strings representing the RPN expression.
 * @returns {number} - The result of the expression.
 */
function evalRPN(tokens) {
    const stack = [];

    tokens.forEach(token => {
        if (!isNaN(token)) {
            stack.push(Number(token));
            console.log(`Push => ${tokens}`)
        } else {
            const b = stack.pop();
            const a = stack.pop();
            console.log(``);
            switch (token) {
                case '+':
                    const summ = a + b;
                    console.log(`summ = ${summ}`);
                    stack.push(summ);
                    break;
                case '-':
                   const summ2 = a - b;
                   console.log(`summ2 = ${summ2}`);
                   stack.push(summ2);
                    break
                ;
                case '*':
                    const mul = a * b;
                    console.log(`mul = ${mul}`);
                    stack.push(mul);
                    break;

                case '/':
                    const div = (a / b) | 0;
                    console.log(`div = ${div}`);
                    stack.push(div);
                    break;
                default:
                throw "bleah!";
            }
        }
    });

    // The result is the last item in the stack
    if (stack.length === 0) {
        throw "bleh, no item on stack.";
    }
    return stack.pop();
}

// Test cases
const testCases = [
    { tokens: ["2", "1", "+", "3", "*"], expected: 9 },
    { tokens: ["4", "13", "5", "/", "+"], expected: 6 },
    { tokens: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"], expected: 22 },
];

testCases.forEach((test, index) => {
    const result = evalRPN(test.tokens);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});

Solution Analysis

Time Complexity: O(n), where n is the number of tokens, as each token is processed once.
Space Complexity: O(n), as the stack may hold up to n/2 elements in the worst case.