Evaluate Reverse Polish Notation medium

Problem Statement

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

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

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide 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

Steps

1. Initialize a stack: We'll use a stack to store operands.
2. Iterate through tokens: For each token:
   • If it's an operand (number), push it onto the stack.
   • If it's an operator (+, -, *, /):
     • Pop the top two operands from the stack (let's call them operand2 and operand1, where operand1 is the topmost element).
     • Perform the operation (operand1 operator operand2).
     • Push the result back onto the stack.
3. Return the final result: After iterating through all tokens, the only element left in the stack will be the final result.

Explanation

Reverse Polish Notation (RPN), also known as postfix notation, is a way of writing mathematical expressions where the operator comes after the operands. This eliminates the need for parentheses and operator precedence rules. Our algorithm directly implements the evaluation of RPN by using a stack. The stack keeps track of operands until an operator is encountered, at which point the necessary operands are popped and the operation is performed. The result is then pushed back onto the stack.

Code

function evalRPN(tokens: string[]): number {
    const stack: number[] = [];

    for (const token of tokens) {
        if (isNaN(Number(token))) { //Check if it's an operator
            const operand2 = stack.pop()!;
            const operand1 = stack.pop()!;
            let result: number;

            switch (token) {
                case '+': result = operand1 + operand2; break;
                case '-': result = operand1 - operand2; break;
                case '*': result = operand1 * operand2; break;
                case '/': result = Math.trunc(operand1 / operand2); break; // Integer division
            }
            stack.push(result);
        } else { //It's an operand
            stack.push(Number(token));
        }
    }

    return stack[0];
}

Complexity

• Time Complexity: O(n), where n is the number of tokens. We iterate through the tokens once.
• Space Complexity: O(n) in the worst case, because the stack could potentially hold all the operands if the expression consists of only operands before any operator is encountered. In the average case, the stack space will be significantly smaller.