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

import re
class Solution:
    def genExpression(self, digits, left, right):
        if right - left == 1:
            return [digits[left:right]]
        suffixes = self.genExpression(digits, left + 1, right)
        d = digits[left]
        ans = []
        for op in ['+', '-', '*']:
            for s in suffixes:
                ans.append(d + op + s)
        for s in suffixes:
            ans.append(d + s)
        return ans
    
    def tokenize(self, expr):
        return re.split(r'([\+\-\*])', expr)
    
    def isValid(self, tokens):
        for t in tokens:
            if len(t) > 1 and t[0] == '0':
                return False
        return True
    
    def eval(self, tokens):
        ops = ['*', '-', '+']
        tokens = [int(t) if t not in ops else t for t in tokens]
        buff = []
        for op in ops:
            n = len(tokens)
            buff = []
            i = 0
            while i < n:
                t = tokens[i]
                if t == op:
                    l = buff.pop()
                    r = tokens[i + 1]
                    buff.append(self.apply(t, l, r))
                    i += 2
                else:
                    buff.append(t)
                    i += 1
            tokens = buff
        return buff[0]
    
    def apply(self, op, l, r):
        if op == '+':
            return l + r
        elif op == '-':
            return l - r
        else:
            return l * r
        
    def addOperators(self, num: str, target: int) -> List[str]:
        allExpressions = self.genExpression(num, 0, len(num))
        ans = []
        for expr in allExpressions:
            tokens = self.tokenize(expr)
            if self.isValid(tokens):
                res = self.eval(tokens)
                if res == target:
                    ans.append(expr)
        return ans

43800