LeetCode 150. Evaluate Reverse Polish Notation¶
- In order to apply the recursive solution:
- Find the pattern that’s repeative
- Think about the return type (return value or update a global variable)
- Come up with the Base case
- Add more conditions to the base case
Recursive:
def evalRPN(self, tokens):
if not tokens:
return 0
def helper(tokens):
if tokens and tokens[-1] not in ('+', '-', '/', '*'):
return int(tokens.pop())
else:
op = tokens.pop()
right = helper(tokens)
left = helper(tokens)
if op == '+':
return left + right
elif op == '-':
return left - right
elif op == '*':
return left*right
elif op == '/':
return int(float(left)/right)
return helper(tokens)
Stack solution Link__ http://scriptasylum.com/tutorials/infix_postfix/algorithms/postfix-evaluation/
def evalRPN(self, tokens):
stack = []
for t in tokens:
if t not in ["+", "-", "*", "/"]:
stack.append(int(t))
else:
r, l = stack.pop(), stack.pop()
if t == "+":
stack.append(l+r)
elif t == "-":
stack.append(l-r)
elif t == "*":
stack.append(l*r)
else:
# here take care of the case like "1/-22",
# in Python 2.x, it returns -1, while in
# Leetcode it should return 0
stack.append(int(float(l)/r))
return stack.pop()
LeetCode 241. Different Ways to Add Parentheses¶
Recursive:
def diffWaysToCompute(self, input):
"""
:type input: str
:rtype: List[int]
"""
if input.isdigit():
return [int(input)]
res = []
for i in range(len(input)):
op = input[i]
if op in ('+', '-', '*'):
left = self.diffWaysToCompute(input[:i])
right = self.diffWaysToCompute(input[i+1:])
for i in left:
for j in right:
res.append(self.ops[op](i, j))
return res
LeetCode 224. Basic Calculator I II III IV¶
- Parenthesis would make everything more complex
- Without Parenthesis, the basic operator can be handled in one stack or one call with prev&curr variables
- Parenthesis can be treated using Stack or Recusion call
- We can use 2 stack solution to cover all possible cases!
Recursive:
def calculate(self, s):
def helper(s, curr_pos):
# we need 2 values before and after the Operator
# we also need one variable to record the curr idx
res = 0
curr = 0
op = 1
i = curr_pos
# since i is changing between different levels, we will use while instead of for
while i < len(s):
if s[i].isdigit():
curr = curr*10 + int(s[i])
elif s[i] == '+':
res += op*curr
op = 1
curr = 0
elif s[i] == '-':
res += op*curr
op = -1
curr = 0
elif s[i] == '(':
val, i = helper(s, i + 1)
res += op*val
op = 1
elif s[i] == ')':
res += op*curr
curr_pos = i
break
i += 1
return res, curr_pos
return helper('(' + s + ')', 0)[0]
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
For general purpose, just convert all the operators into Reversive Polish Notation:
class Solution(object):
def evalRPN(self, tokens):
if not tokens:
return 0
def helper(tokens):
if tokens and tokens[-1] not in ('+', '-', '/', '*'):
return int(tokens.pop())
else:
op = tokens.pop()
right = helper(tokens)
left = helper(tokens)
if op == '+':
return left + right
elif op == '-':
return left - right
elif op == '*':
return left*right
elif op == '/':
return int(float(left)/right)
return helper(tokens)
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
def rank(op):
if op == '+':
return 1
elif op == '-':
return 1
elif op == '*':
return 2
elif op == '/':
return 2
else:
return 0
def convertRPN(s):
output = [] # output queue
stack = [] # operator stack
i = 0
while i < len(s):
char = s[i]
if char.isdigit():
j = i+1
while j < len(s) and s[j].isdigit():
j += 1
num = s[i:j]
output.append(num)
i = j
elif char == ' ':
i += 1
elif char == '(':
stack.append('(')
i += 1
elif char == ')':
# keep pushing the stack
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop() # remove '('
i += 1
else:
op = s[i]
while stack and rank(op) <= rank(stack[-1]):
output.append(stack.pop())
stack.append(op)
i += 1
while stack:
output.append(stack.pop())
return output
return self.evalRPN(convertRPN(s))
LeetCode 282. Expression Add Operators¶
Similar to Basic calculator, you need to construct a recursive call to construct all path from top to bottom:
class Solution(object):
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
def helper(nums, path, prev, sofar, target, res):
if not nums and sofar == target:
res.append(path)
return
for i in range(1, len(nums)+1):
val = nums[:i]
if i == 1 or (i > 1 and nums[0] != "0"):
helper(nums[i:], path + '+' + val, int(val), sofar + int(val), target, res)
helper(nums[i:], path + '-' + val, -int(val), sofar - int(val), target, res)
helper(nums[i:], path + '*' + val, prev*int(val), sofar - prev + prev*int(val), target, res)
res = []
for i in range(1, len(num)+1):
if len(num[:i]) != len(str(int(num[:i]))):
continue
helper(num[i:], num[:i], int(num[:i]), int(num[:i]), target, res)
return res
LeetCode 679. 24 Game¶
My own solution:
class Solution(object):
def judgePoint24(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
def dfs(nums, path):
if len(nums) == 1 and nums[0] == 24:
res.append(path[-1])
return
for i in range(len(nums)):
remaining = nums[:i] + nums[i+1:]
remaining_path = path[:i] + path[i+1:]
for j in range(len(remaining)):
dfs(remaining[:j] + remaining[j + 1:] + [nums[i] + remaining[j]], remaining_path[:j] + remaining_path[j+1:] + ['('+str(path[i]) + '+'+str(remaining_path[j]) + ')'])
dfs(remaining[:j] + remaining[j + 1:] + [nums[i] * remaining[j]], remaining_path[:j] + remaining_path[j+1:] + [str(path[i]) + '*'+str(remaining_path[j])])
dfs(remaining[:j] + remaining[j + 1:] + [nums[i] - remaining[j]], remaining_path[:j] + remaining_path[j+1:] + ['('+str(path[i]) + '-'+str(remaining_path[j]) + ')'])
if float(remaining[j]) == 0:
continue
dfs(remaining[:j] + remaining[j + 1:] + [float(nums[i]) / float(remaining[j])], remaining_path[:j] + remaining_path[j+1:] + [str(path[i]) + '/'+str(remaining_path[j])])
res = []
path = [str(num) for num in nums]
dfs(nums, path)
return res