# Links

Go to my solution

Go to the question on LeetCode

# My Thoughts

**What Went Well**

I immediately knew how to implement the solution and optimized my code quickly.

**What Went Wrong**

I got stuck on one requirement because the floor operation kept returning -1 for some edge cases.

**What I Learned**

I learned that when the divisor is greater than the dividend and you use the floor operator, it returns -1. I also learned that the int() function rounds the input towards 0 and not to the nearest whole number.

**How I Can Improve**

I could review the documentation for operators and dive into their more fine details, such as above.

**Comments**

I initially attempted to make my solution smaller by adding the function, but it obviously had the opposite effect. Thankfully after looking at the solution statistics, I realized I had to optimize my solution and did so accordingly. The optimal solution is much more streamlined and type-safe.

# Data Structure Description

**Stack -** A stack is similar to an array, except you are only allowed to push/pop (add/remove) from the end of the stack. A stack follows the first in, last out, or FILO theme.

Since Python already has O(1) push (append) and pop (pop) operations, we do not need to use any libraries.

**Visual Examples**

Visual of a stack being mutated, click to view

# Solution Statistics For Optimal Solution

**Time Spent Optimizing**

10 minutes

**Time Complexity**

O(n) - We must iterate through each element in the tokens list, resulting in the O(n) time complexity. Since we do not perform any operations larger than O(1), the time complexity does not increase.

**Space Complexity**

O(1) - There are never more elements in the num_stack than in the tokens list. num_stack is just an intermediary which increases and decreases throughout the execution of the for loop, resulting in the O(1) space complexity.

**Runtime Beats**

93.75% of other submissions

**Memory Beats**

92.13% of other sumbissions

# Optimized Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
def evalRPN(self, tokens: List[str]) -> int:
num_stack = []
# Iterate through each token
for tok in tokens:
match tok:
# If the token matches any of the following, perform the
# corresponding operation
case "*":
num_stack.append(num_stack.pop() * num_stack.pop())
case "+":
num_stack.append(num_stack.pop() + num_stack.pop())
# The order of the elements matters, so we must place each
# element in an intermediary and then perform the operation
case "-":
r, l = num_stack.pop(), num_stack.pop()
num_stack.append(l - r)
case "/":
r, l = num_stack.pop(), num_stack.pop()
num_stack.append(int(l/r))
# If it does not match any of the following, it is an integer,
# append it to the stack after converting it to an integer
case _:
num_stack.append(int(tok))
return num_stack[0]

# Solution Statistics For Original Solution

**Time Spent Coding**

23 minutes

**Time Complexity**

O(n^{2}) - We must iterate through each element in the tokens list and perform one O(n) operation in the for loop, which increases our time complexity to O(n^{2}).

**Space Complexity**

O(1) - There are never more elements in the num_stack than in the tokens list. num_stack is just an intermediary that increases and decreases throughout the execution of the for loop, resulting in the O(1) space complexity. Although the same space complexity, the function creates a lot more intermediary values which causes the awful space complexity.

**Runtime Beats**

11.74% of other submissions

**Memory Beats**

10.33% of other sumbissions

# Original Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
def evalRPN(self, tokens: List[str]) -> int:
def eval(join):
opL, op, opR = join
match op:
case "*":
return opL * opR
case "-":
return opL - opR
case "/":
return int(opL/opR)
case "+":
return opL + opR
num_stack = []
for tok in tokens: # O(n)
if tok not in {"+","-","*","/"}:
num_stack.append(int(tok))
else:
join = [tok]
join.append(num_stack.pop())
join.insert(0,num_stack.pop()) # O(n)
num_stack.append(eval(join))
return int(num_stack[0])