<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]:
        n = len(num)
        st = [None] * 100010
        m = {'-': 0, '+': 0, '*': 1}
        ans = []
        def dfs(k):
            nonlocal ans, st, n, m
            # st = ['*', None, None]
            if k == n - 1:
                nq, oq = deque(), deque()
                y = 0
                for i in range(n):
                    y*= 10
                    y+= ord(num[i]) - ord('0')

                    if st[i] is not None:
                        while oq and m[st[i]] <= m[oq[-1]]:
                            x = nq.pop()
                            op = oq.pop()
                            # print(x, op, y)
                            if op == '+':
                                y = x + y
                            elif op == '-':
                                y = x - y
                            elif op == '*':
                                y = x * y
                        oq.append(st[i])
                        nq.append(y)
                        y = 0
   
                while oq:
                    x = nq.pop()
                    op = oq.pop()
                    # print(x, op, y)

                    if op == '+':
                        y = x + y
                    elif op == '-':
                        y = x - y
                    elif op == '*':
                        y = x * y
                # `105` `1 * 0 None 5`
                if y == target:
                    p = [str(num[i]) + (str(st[i]) if st[i] is not None else '')  for i in range(n -1)]
                    p.append(str(num[n-1]))
                    ans.append(''.join(p))


                return
            # k < n - 1
            st[k] = '+'
            dfs(k+1)
            st[k] = '-'
            dfs(k+1)
            st[k] = '*'
            dfs(k+1)
            if not (num[k] == '0' and  (k == 0 or st[k - 1] is not None)):
                 st[k] = None
                 dfs(k+1)
            return
        dfs(0)
        return ans

                    


32200