LeetCode 224. Basic Calculator

November 14, 2024

Final stack problem for this practice set is a hard question. Took me an hour and a half to come up with this convoluted method. Parsing numbers character by character was my first mistake.

Solution

1class Solution:
2    def calculate(self, s: str) -> int:
3        parsed = []
4        num = ''
5        for token in s:
6            if token in ['(', ')', '+', '-', ' ']:
7                if num:
8                    parsed.append(num)
9                    num = ''
10                parsed.append(token)
11            else:
12                num += token
13        if num:
14            parsed.append(num)
15
16        s = parsed
17        nums = []
18        ops = []
19        total = 0
20        for token in s:
21            match token:
22                case '(':
23                    ops.append('(')
24                    nums.append('(')
25                case ')':
26                    ops.pop()
27                    right = nums.pop()
28                    nums.pop()
29                    if ops and ops[-1] != '(' and right != '(':
30                        op = ops.pop()
31                        if op == '+':
32                            total = nums.pop() + right
33                        elif op == '-':
34                            if nums and nums[-1] != '(':
35                                total = nums.pop() - right
36                            else:
37                                total = right * -1
38                        nums.append(total)
39                        total = 0
40                    else:
41                        nums.append(right)
42                case '-':
43                    ops.append('-')
44                case '+':
45                    ops.append('+')
46                case ' ':
47                    pass
48                case _:
49                    if not ops or ops[-1] == '(':
50                        total += int(token)
51                    else:
52                        op = ops.pop()
53                        if op == '+':
54                            total = int(token) + nums.pop()
55                        elif op == '-':
56                            if nums and nums[-1] != '(':
57                                total = int(nums.pop()) - int(token)
58                            else:
59                                total = -1 * int(token)
60                    nums.append(total)
61                    total = 0
62        return nums[-1]

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

LeetCode 150. Evaluate Reverse Polish Notation

LeetCode 138. Copy List with Random Pointer