# Use DFS but TLE

• I use DFS in my algorithm, just like many solutions. I use a queue to store all possible expansion and continue to expand until the queue is empty. In each element in the queue, there are an index pointing to the character in input number and a stack for representing current expression. The evaluate() function is used to evaluate the stack. I don't understand what is the difference between my algorithm and others, since I am clearly using DFS here.

``````from collections import deque

class Solution(object):
def evaluate(self, opStack):
stack = []
#print "============"
#print opStack
idx = 0
while idx < len(opStack):
val = opStack[idx]
if val == '-' or val == '+':
if len(stack) != 1:
temp1 = stack.pop()
op = stack.pop()
temp2 = stack.pop()
if op == '-':
stack.append(temp2-temp1)
else:
stack.append(temp1+temp2)
stack.append(val)
elif val == '*':
temp1 = stack.pop()
stack.append(temp1*opStack[idx+1])
idx = idx + 1
else:
# number
stack.append(val)
idx = idx + 1

if len(stack) != 1:
temp1 = stack.pop()
op = stack.pop()
temp2 = stack.pop()
if op == '-':
stack.append(temp2-temp1)
else:
stack.append(temp1+temp2)
#print stack[-1]
return stack[-1]

def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
if len(num) == 0:
return []

q = deque()
if int(num[0]) != 0:
q.append([1, [int(num[0])]]) # store the idx for next character and current operation stack
q.append([1, [int(num[0]), '*']])
q.append([1, [int(num[0]), '+']])
q.append([1, [int(num[0]), '-']])

ret = []

while len(q) != 0:
temp = q.popleft()
stack = temp[1]
if temp[0] == len(num):
val = self.evaluate(stack)
if val == target:
ans = ''.join( str(e) for e in stack )
ret.append(ans)
elif stack[-1] == '*' or stack[-1] == '+' or stack[-1] == '-':
if temp[0]+1 != len(num):
newStack = stack + [int(num[temp[0]]), '*']
q.append([temp[0]+1, newStack])
newStack = stack + [int(num[temp[0]]), '+']
q.append([temp[0]+1, newStack])
newStack = stack + [int(num[temp[0]]), '-']
q.append([temp[0]+1, newStack])
if int(num[temp[0]]) != 0:
newStack = stack + [int(num[temp[0]])]
q.append([temp[0]+1, newStack])
else:
# top of stack is a number
newNum = stack[-1]*10 + int(num[temp[0]])
stack.pop()
stack.append( newNum )

q.append([temp[0]+1, stack])
if temp[0]+1 != len(num):
newStack = stack + ['*']
q.append([temp[0]+1, newStack])
newStack = stack + ['+']
q.append([temp[0]+1, newStack])
newStack = stack + ['-']
q.append([temp[0]+1, newStack])

return ret
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.