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

Explanation

Reverse Polish notation is a postfix notation where we want to apply the operation on the two immediately preceeding values. This naturally maps to a stack which always retrieves values in the reverse order they were seen.

Create an empty stack to store the values. Whenever we encounter a value, push it onto the stack. When we encounter an operation, pop the top two values and execute op(val1, val2) and push the result back onto the stack. When the expression finishes, the result is the top value on the stack.

Code

from collections import deque


def exec_op(x, y, op_token):
    """Execute operation ``op_token`` on ``x`` and ``y``."""
    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:
    """Evaluate the arithmetic expression in reverse Polish notation."""
    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

Complexity

\(n\) is the number of tokens in tokens

Measure

Complexity

Notes

Time

\(O(n)\)

one pass through the array

Auxiliary Space

\(O(n)\)

in the worst case where all operations are at the end of the expression, the stack can contain \(\approx n/2\) tokens.
evaluate_reverse_polish_notation__stack.exec_op(x, y, op_token)

Execute operation op_token on x and y.

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

Evaluate the arithmetic expression in reverse Polish notation.