Problem statement

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

Solution

This problem is ideal for recursion or stack. All we need to do is to understand logic: if we see new number, put it into stack, if we see operation, extract the last two numbers and apply this operation. Also be careful with shrinking towards zero: I spent some time before realized that it is just int(b/a) meant here.

Complexity

Time and space complexity is just O(n), because we can put an remove each element from stack only once. Potentially we can have upty n//2 elements in our stack.

Code

class Solution:
    def evalRPN(self, tokens):
        stack = []
        def f(a, b, c):
            if c == "+": return a+b
            if c == "-": return b-a
            if c == "*": return a*b
            if c == "/": return int(b/a)
            
        for token in tokens:
            if token in "*/+-":
                stack.append(f(stack.pop(), stack.pop(), token))
            else:
                stack.append(int(token))
        return stack[-1]