Evaluate Reverse Polish Notation

Problem Source: Leetcode

Problem Description

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.

tests

def test(fn):
    tokens = ["2","1","+","3","*"]
    assert 9 == fn(tokens)

    tokens = ["4","13","5","/","+"]
    assert 6 == fn(tokens)

    tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
    assert 22 == fn(tokens)

Solution

• Time Complexity: O(n)
• Space Complexity: O(n)

from typing import List
from operator import add, mul, sub, truediv
def evalRPN(tokens: List[str]) -> int:
    stack = []
    # Map each valid operator to a callable
    operators = {'+': add, '*': mul, '-': sub, '/': lambda x,y: int(truediv(x,y))}
    
    for t in tokens:
        # For every operator in tokens calculate res of last 2 with that operator
        if t in operators:
            f,s = stack.pop(),stack.pop()
            stack.append(operators[t](s,f))
        else:
            # if it's not an operator add the value to the stack
            stack.append(int(t))
    return stack.pop() # Last value remaining is the answer

test(evalRPN)