Learning Journal

3/1/2024

Evaluate Reverse Polish Notation

function evalRPN(tokens: string[]): number {
    let result = 0;
    const arithQueue = new ArithQueue();

    for(let i = 0; i < tokens.length; i++){
        result = arithQueue.push(tokens[i]);
    }

    return result;
};

class ArithQueue {
    private arr:number[] = [];

    push(token:string):number {
        if(this.isOperator(token)){
            const val = this.calculate(token);
            this.arr.push(val);

            return val;
        }
        else {
            this.arr.push(Number(token));
            return Number(token);
        }
    }

    isOperator(token:string) {
        return token === "+" || token === "-" || token === "/" || token === "*";
    }

    calculate(token:string):number {
        let result:number|null = null;

        const op1 = this.arr.pop();
        const op2 = this.arr.pop();

        switch(token) {
            case "+":
                result = op1 + op2;
            break;
            case "-":
                result = op2 - op1;
            break;
            case "/":
                const res = op2/op1;
                result = res > 0 ? Math.floor(op2 / op1): Math.ceil(op2/op1);
            break;
            case "*":
                result = op1 * op2;
            break;
            default:
                throw new Error("Invalid Token")
        
        }

        return result;
    }


}function evalRPN(tokens: string[]): number {
    let result = 0;
    const arithQueue = new ArithQueue();

    for(let i = 0; i < tokens.length; i++){
        result = arithQueue.push(tokens[i]);
    }

    return result;
};

class ArithQueue {
    private arr:number[] = [];

    push(token:string):number {
        if(this.isOperator(token)){
            const val = this.calculate(token);
            this.arr.push(val);

            return val;
        }
        else {
            this.arr.push(Number(token));
            return Number(token);
        }
    }

    isOperator(token:string) {
        return token === "+" || token === "-" || token === "/" || token === "*";
    }

    calculate(token:string):number {
        let result:number|null = null;

        const op1 = this.arr.pop();
        const op2 = this.arr.pop();

        switch(token) {
            case "+":
                result = op1 + op2;
            break;
            case "-":
                result = op2 - op1;
            break;
            case "/":
                const res = op2/op1;
                result = res > 0 ? Math.floor(op2 / op1): Math.ceil(op2/op1);
            break;
            case "*":
                result = op1 * op2;
            break;
            default:
                throw new Error("Invalid Token")
        
        }

        return result;
    }


}

THE PROBLEM

This problem is fairly simple. You use a stack to push operands and when you reach operator, you pop 2 last operands from the stack, then operate the operator on those operands, then push the result back to the stack. The catch here is you need to round toward 0. This requirement only affects division. So, after divide 2 operands, if the result is negative, you round up and if otherwise, you round down. Another catch here is the order of operands when you perform subtraction and division.

Revised by ChatGPT

The challenge of the "Evaluate Reverse Polish Notation" problem lies in correctly calculating the value of an arithmetic expression written in reverse Polish notation. The solution employs a stack-based approach for its simplicity and efficiency in handling such expressions.

Key Solution Strategy:

Stack Utilization: Operands are pushed onto the stack until an operator is encountered. At this point, the top two operands are popped from the stack. The operator is applied to these operands, and the result is pushed back onto the stack.
Division and Rounding: A notable requirement is to round the division result toward zero. This affects the division operation's outcome, particularly when dealing with negative numbers. To comply, if the result of a division is negative, it is rounded up, whereas positive results are rounded down to the nearest integer.
Operand Order: Special attention must be paid to the order of operands when performing subtraction and division operations to ensure accuracy, as reversing the operands can lead to incorrect results.

Implementation Highlights:

The ArithQueue class manages the stack and arithmetic operations. It includes methods for:

Determining if a token is an operator (isOperator).
Performing arithmetic operations based on the operator encountered (calculate).
Managing the stack of operands and ensuring correct application of operators (push).

This problem not only tests one's understanding of stack operations but also their attention to detail in implementing division rounding and operand ordering correctly. It's an excellent exercise for developing a deeper understanding of both data structure usage and the nuances of arithmetic operation implementation.