philosyang.com

150. Evaluate Reverse Polish Notation

this is a straightforward stack problem without much to talk about.

 1class Solution:
 2    def evalRPN(self, tokens: List[str]) -> int:
 3        if len(tokens) < 2:
 4            return int(tokens[0])
 5        stack = [tokens[0], tokens[1]]
 6        operator = set(["+", "-", "*", "/"])
 7
 8        for token in tokens[2:]:
 9            if token in operator:
10                if len(stack) < 2:
11                    return False
12                b = stack.pop()
13                a = stack.pop()
14
15                if token == "+":
16                    stack.append(int(a) + int(b))
17                elif token == "-":
18                    stack.append(int(a) - int(b))
19                elif token == "*":
20                    stack.append(int(a) * int(b))
21                else:
22                    stack.append(int(int(a) / int(b)))
23            else:
24                stack.append(token)
25        return stack[0]

key takeaways:

  1. “The division between two integers always truncates toward zero” does not translate to a//b in python:
    for example, -1 // 2 == -1 but we want 0. Use int(a/b) instead.
  2. remember to handle corner cases such as tokens = ["18"].

#Neetcode150 #Array #Math #Stack #Python