Evaluate Reverse Polish Notation

Problem

https://leetcode.com/problems/evaluate-reverse-polish-notation/

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.

• Each operand may be an integer or another expression.

• The division between two integers always truncates toward zero.

• There will not be any division by zero.

• The input represents a valid arithmetic expression in a reverse polish notation.

• The answer and all the intermediate calculations can be represented in a 32-bit integer.

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

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

• 1 <= tokens.length <= 10:sup:`4`

• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Pattern

Array, Math, Stack

Approaches

Stack

Code

from collections import deque


def exec_op(x, y, op_token):
    match op_token:
        case "+":
            return x + y
        case "-":
            return x - y
        case "*":
            return x * y
        case "/":
            return int(float(x) / y)


def evalRPN(tokens: list[str]) -> int:
    num_stack = deque()
    operators = {"+", "-", "*", "/"}
    for token in tokens:
        if token in operators:
            y = num_stack.pop()
            x = num_stack.pop()
            result = exec_op(x, y, token)
            num_stack.append(result)
        else:
            num_stack.append(int(token))

    return num_stack.pop()

Test

>>> from evaluate_reverse_polish_notation__stack import evalRPN
>>> evalRPN(["2", "1", "+", "3", "*"])
9
>>> evalRPN(["4", "13", "5", "/", "+"])
6
>>> evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])
22

evaluate_reverse_polish_notation__stack.exec_op(x, y, op_token)

evaluate_reverse_polish_notation__stack.evalRPN(tokens: list[str]) → int