Evaluate Reverse Polish Notation

Question

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

Return the integer that represents the evaluation of the expression.

• The operands may be integers or the results of other operations.
• The operators include '+', '-', '*', and '/'.
• Assume that division between integers always truncates toward zero.

Example 1:

Input: tokens = ["1","2","+","3","*","4","-"]

Output: 5

Explanation: ((1 + 2) * 3) - 4 = 5

Constraints:

• 1 <= tokens.length <= 1000.
• tokens[i] is "+", "-", "*", or "/", or a string representing an integer in the range [-200, 200].

Solution

Intuition

We can add everything into a stack, whenever we see an operation, we can calculate it right away, for example:

Implementation

from typing import *

class Application:
    OPERATIONS = {"+", "-", "*", "/"}
    
    def evalRPN(self, tokens: List[str]) -> int:
        memory = []

        for token in tokens:
            if token in self.OPERATIONS:
                b = int(memory.pop())
                a = int(memory.pop())
                memory.append(self._op(token, a, b))
            else:
                memory.append(token)
        
        return int(memory[0])
    
    def _op(self, token: str, a: int, b: int):
        if token == "+": return a + b
        if token == "-": return a - b
        if token == "/": return a / b
        if token == "*": return a * b

Time complexity

Time complexity: O(n) — n is the length of the input
Space complexity: O(n) — n is the length of the input