282.Expression Add Operators
Tags: [recursion], [evaluation], [expression], [math]
SubTags: <postorder>, <postorder_traversal>, <postorder_expression>, <expression_tree>
Com: {fb}
Link: https://leetcode.com/problems/expression-add-operators/#/description
Given a string that contains only digits0-9and a target value, return all possibilities to add binary operators (not unary)+,-, or*between the digits so they evaluate to the target value.
Examples:
"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []
Solution: Recursion, Expression, Math
class Solution(object):
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
if not num or target is None:
return []
result = []
self.add_operators_helper(num, target, 0, '', 0, 0, result)
return result
def add_operators_helper(self, num, target, index, expression, expression_eval_val, prev_num, result):
# base case.
if index >= len(num):
if expression_eval_val == target:
result.append(expression)
return
for i in xrange(index, len(num)):
if num[index] == '0' and i > index:
break
curr_segment = num[index:i + 1]
curr = int(curr_segment)
if index == 0:
self.add_operators_helper(num, target, i + 1, curr_segment, curr, curr, result)
continue
self.add_operators_helper(num, target, i + 1, expression + '+' + curr_segment,
expression_eval_val + curr, curr, result)
self.add_operators_helper(num, target, i + 1, expression + '-' + curr_segment,
expression_eval_val - curr, -curr, result)
self.add_operators_helper(num, target, i + 1, expression + '*' + curr_segment,
expression_eval_val - prev_num + prev_num * curr, prev_num * curr, result)
Revelation:
假设当前的expression是1+2 = 3， 那么我们现在想 +3 (来计算 1+2+3)， 那么我们应该用1+2的结果3来加3 3+3 = 6，
假设当前的expression是1+2+3 = 6, 那么我们现在想 *4 (来计算 1+2+3*4)， 那么我们应该用6 -3 = 3， 然后在3*4 = 12， 然后在3 + 12 = 15.
假设当前的expression是1+2+3*4 = 15， 那么我们现在想 *5 (来计算 1+2+3*4*5)，那么我们应该用15 - 3*4 = 3， 然后在3*4*5 = 60， 然后在3 + 60 = 63.
- 由此可见，对于本次recursion，是加法和减法的运算很简单，我们只需要用之前的结果加上或减去curr即可，但对于乘法有些不好处理，我们的办法是，用一个变量一直记住连续乘法的积(在上面的算法里就是prev_num)，然后用expression_eval_val - prev_num + prevnum * curr来获得新表达式的值，然后把prev_num * curr传递给下一次recursion。如果本次recursion是加法或减法，则prev_num = curr.
Note:
- Time complexity = O(n!), n is the length of the given num.
Time Limited Exceeded: Expression Tree, Postorder Expression Evaluation
class Solution(object):
class TreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
if not num or target is None:
return []
result = []
operators = ['+', '-', '*'] # ordered by the priority from low to high,
expression = ''
self.add_operators_helper(num, target, 0, operators, expression, result)
return result
def add_operators_helper(self, num, target, index, operators, expression, result):
# base case.
if index >= len(num):
if self.eval_expression(expression, operators) == target:
result.append(expression)
return
for i in xrange(index, len(num)):
if i > index and num[index] == '0':
break
curr_segment = num[index:i + 1]
if index == 0:
self.add_operators_helper(num, target, i + 1, operators, curr_segment, result)
continue
self.add_operators_helper(num, target, i + 1, operators, expression + '+' + curr_segment, result)
self.add_operators_helper(num, target, i + 1, operators, expression + '-' + curr_segment, result)
self.add_operators_helper(num, target, i + 1, operators, expression + '*' + curr_segment, result)
def eval_expression(self, expression, operators):
if not expression:
return 0
expression_tree_root = self.build_expression_tree(expression, 0, len(expression) - 1, operators)
postorder_expression = self.postorder_traversal(expression_tree_root)
return self.eval_postorder_expression(postorder_expression, set(operators))
def build_expression_tree(self, expression, start, end, operators):
# base case.
if start > end:
return None
root_val_index = -1
# search operator from lower priorty to high priority
for o in operators:
try:
root_val_index = expression.index(o, start, end + 1)
break
except ValueError, e:
pass
if root_val_index < 0:
return self.TreeNode(expression[start:end + 1])
root = self.TreeNode(expression[root_val_index])
root.left = self.build_expression_tree(expression, start, root_val_index - 1, operators)
root.right = self.build_expression_tree(expression, root_val_index + 1, end, operators)
return root
def postorder_traversal(self, root):
if not root:
return []
result = []
stack = [root]
while stack:
curr = stack[-1]
if not curr.left and not curr.right:
stack.pop()
result.append(curr.val)
else:
if curr.right:
stack.append(curr.right)
curr.right = None
if curr.left:
stack.append(curr.left)
curr.left = None
return result
def eval_postorder_expression(self, tokens, operators):
if not tokens:
return 0
stack = []
for token in tokens:
if not stack or token not in operators:
stack.append(int(token))
else:
operand2 = stack.pop()
if not stack:
raise ValueError('the input expression is invalid')
operand1 = stack.pop()
sub_result = None
if token == '+':
sub_result = operand1 + operand2
elif token == '-':
sub_result = operand1 - operand2
elif token == '*':
sub_result = operand1 * operand2
if sub_result is None:
raise ValueError('the current operator is not +, -, or *')
stack.append(sub_result)
if not stack:
raise ValueError('the input expression is invalid')
return stack.pop()
Revelation:
- When we building the expression tree, our recursion from top to bottom to build the tree, we try to put the lower priority operator on the upper level of the tree.
Note:
- Time complexity = O(n! * (3*n)), n is the length of the given num.
- When we use iteration to do postorder traversal, we break the tree structure.