<p>Given a string <code>num</code> that contains only digits and an integer <code>target</code>, return <em><strong>all possibilities</strong> to insert the binary operators </em><code>&#39;+&#39;</code><em>, </em><code>&#39;-&#39;</code><em>, and/or </em><code>&#39;*&#39;</code><em> between the digits of </em><code>num</code><em> so that the resultant expression evaluates to the </em><code>target</code><em> value</em>.</p>

<p>Note that operands in the returned expressions <strong>should not</strong> contain leading zeros.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;123&quot;, target = 6
<strong>Output:</strong> [&quot;1*2*3&quot;,&quot;1+2+3&quot;]
<strong>Explanation:</strong> Both &quot;1*2*3&quot; and &quot;1+2+3&quot; evaluate to 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;232&quot;, target = 8
<strong>Output:</strong> [&quot;2*3+2&quot;,&quot;2+3*2&quot;]
<strong>Explanation:</strong> Both &quot;2*3+2&quot; and &quot;2+3*2&quot; evaluate to 8.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;3456237490&quot;, target = 9191
<strong>Output:</strong> []
<strong>Explanation:</strong> There are no expressions that can be created from &quot;3456237490&quot; to evaluate to 9191.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 10</code></li>
	<li><code>num</code> consists of only digits.</li>
	<li><code>-2<sup>31</sup> &lt;= target &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        que = collections.deque()
        que.append(("", 0))
        answer = []

        while(len(que) > 0):
            pp, depth = que.popleft()

            if depth == 0:
                que.append((num[depth], depth+1))
                continue

            if depth >= len(num):
                result = self.evaluate(pp, target)
                if result != "":
                    answer.append(result)
                continue
            
            que.append((pp + ",*," + num[depth], depth+1))
            que.append((pp + ",-," + num[depth], depth+1))
            que.append((pp + ",+," + num[depth], depth+1))
            que.append((pp + num[depth], depth+1))
        
        return answer

    def evaluate(self, evalstring: str, target: int) -> List[str]:
        ar = evalstring.split(",")

        for item in ar:
            if len(item) > 1 and item[0] == "0":
                return ""

        sumlist = []
        counter = 0
        while(counter < len(ar)):
            if ar[counter].isdigit():
                sumlist.append(int(ar[counter]))
            elif ar[counter] == "*":
                l = sumlist.pop()
                sumlist.append(l * int(ar[counter+1]))
                counter += 1
            elif ar[counter] == "-":
                sumlist.append(-int(ar[counter+1]))
                counter += 1
            counter += 1
        
        if sum(sumlist) == target:
            return "".join(ar)
        else:
            return ""


"""

1

1,*,2
1,+,2
1,-,2 
12 

1,*,2,*,3
1,*,2,+,3
1*2-3
1*23

1+2*3
1+2+3
1+2-3
1+23

[1, *, 2, *, 3]
[1, *, 2, -, 3]

"""
57000