Evaluate Reverse Polish Notation — LeetCode 150 Python Solution

The problem

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

Example

Input

tokens = ["2","1","+","3","*"]

Output

9

Explanation

((2 + 1) * 3) = 9

Python solution

import operator


class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        opt = {
            "+": operator.add,
            "-": operator.sub,
            "*": operator.mul,
            "/": operator.truediv,
        }
        s = []
        for token in tokens:
            if token in opt:
                s.append(int(opt[token](s.pop(-2), s.pop(-1))))
            else:
                s.append(int(token))
        return s[0]

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 150. Evaluate Reverse Polish Notation is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems