LeetCode 150. Evaluate Reverse Polish Notation

November 13, 2024

Now I'm on to stacks. I had to rethink my strategy of going from right to left, to left to right. I was overcomplicating it.

Solution

1class Solution:
2    def evalRPN(self, tokens: List[str]) -> int:
3        stack = []
4        for token in tokens:
5            if token in ['+', '/', '+', '-', '*']:
6                right = int(stack.pop())
7                left = int(stack.pop())
8                match token:
9                    case '+':
10                        res = left + right
11                    case '/':
12                        res = left / right
13                    case '+':
14                        res = left + right
15                    case '-':
16                        res = left - right
17                    case '*':
18                        res = left * right
19                stack.append(res)
20            else:
21                stack.append(token)
22        return int(stack[-1])

O(n) = n since we iterate over all elements once. Space complexity also O(n) = n for the stack.

LeetCode 57. Insert Interval

LeetCode 224. Basic Calculator