<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]:

        def find_total(expr):
            stack = deque()
            ops_stack = deque()
            ops = ['+', '-', '*']
            cur_int = ''
            for c in expr:
                if c == ' ': continue
                if c in ops:
                    i = int(cur_int)
                    cur_int = ''
                    if not stack:
                        stack.append(i)
                    else:
                        if ops_stack[-1] == '*':
                            top = stack.pop()
                            op = ops_stack.pop()
                            if op == '*':
                                stack.append(i * top)
                            else:
                                stack.append(top // i)
                        else:
                            stack.append(i)
                    ops_stack.append(c)
                else:
                    cur_int += c
            
            if len(cur_int) > 0:
                i = int(cur_int)
                if ops_stack and ops_stack[-1] in ('*', '/'):
                    top = stack.pop()
                    op = ops_stack.pop()
                    if op == '*':
                        stack.append(i * top)
                    else:
                        stack.append(top // i)
                else:
                    stack.append(i)

            output = 0

            while ops_stack:
                value1 = stack.popleft()
                op = ops_stack.popleft()
                if op == '+':
                    stack[0] = value1 + stack[0]
                else:
                    stack[0] = value1 - stack[0]
            
            return stack[0]

        def find_expressions(expr: str,  nums: str):

            if len(nums) == 0:
                e = expr[1:]
                if e not in dp:
                    t = find_total(e)
                    if t == target:
                        expressions.add(e)
                    dp[e] = t
                return

            for i in range(len(nums)):
                curr_chars = nums[:i+1]
                if len(curr_chars) > 1 and curr_chars[0] == '0':
                    continue
                find_expressions(expr + '+' + nums[:i+1], nums[i+1:])
                find_expressions(expr + '-' + nums[:i+1], nums[i+1:])
                find_expressions(expr + '*' + nums[:i+1], nums[i+1:])


        num_stack, ops_stack = list(), list()
        expressions = set()
        dp = dict()
        find_expressions('', num)
        return list(expressions)

155100