<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]:
        if not num:
            return []

        index = 0
        ans = []
        path = []
        ops = {"+", "-", "*"}
        self.findAns(num, target, ops, index, path, ans)

        return ans

    
    def findAns(self, num, target, ops, index, path, ans):
        
        if index == len(num):
            # path.append(num[index])
            # print(path)
            res = self.calculate_Rev(path)
            # print(res)
            if res == target:
                ans.append( "".join(path) )
            # path.pop()
            return
        
        # path.append(num[index])
        # index += 1


        if num[index] == "0":
            curr = num[index]
            path.append(curr)
            if index == len(num)-1:
                self.findAns(num, target, ops, index+1, path, ans)
            else:
                for op in ops:
                    path.append(op)               
                    self.findAns(num, target, ops, index+1, path, ans)
                    path.pop()
            path.pop()
        else:
            for i in range(index, len(num)):
                curr = num[index : i+1]
                path.append(curr)
                if i == len(num)-1:
                    self.findAns(num, target, ops, i+1, path, ans)
                else:
                    for op in ops:
                        path.append(op)               
                        self.findAns(num, target, ops, i+1, path, ans)
                        path.pop()
                path.pop()

    def calculate_Rev(self, path):
        index = 0
        stack = []
        nums = []
        while index < len(path):
            if path[index] in "+-":
                stack.append(path[index])
            elif path[index] == "*":
                nxt_num = int(path[index+1])
                prenum = nums.pop()
                product = prenum * nxt_num
                nums.append(product)
                index += 1
            else:
                num = int(path[index])
                if stack and stack[-1]=="-":
                    stack.pop()
                    nums.append(-1*num)
                elif stack and stack[-1]=="+":
                    stack.pop()
                    nums.append(num)
                else:
                    nums.append(num)
            index += 1
        # print(nums)
        return sum(nums)

    
    def calculate(self, path):
        index = 0
        stack = []
        nums = []
        while index < len(path):
   
            if ord("0") <= ord(path[index]) <= ord("9"):
                num, index = self.getNum(path, index)
                if num == None:
                    return None
                if stack and stack[-1]=="-":
                    stack.pop()
                    nums.append(-1*num)
                elif stack and stack[-1]=="+":
                    stack.pop()
                    nums.append(num)
                else:
                    nums.append(num)

            elif path[index] in "-+":
                stack.append(path[index])

            elif path[index] == "*":
                index += 1
                num, index = self.getNum(path, index)
                if num == None:
                    return None
                prenum = nums.pop()
                product = prenum * num
                nums.append(product)
            
            index += 1
        
        # print(nums)
        # print(stack)
        return sum(nums)
    

    def getNum(self, path, index):
        if ord(path[index]) == ord("0"):
            if index < len(path)-1 and  ord("0") <= ord(path[index+1]) <= ord("9"):
                return None, None
            else:
                return 0, index

        num = 0
        while index < len(path) and ord("0") <= ord(path[index]) <= ord("9"):
            num = num *10 + ord(path[index]) - ord("0")
            index += 1
        
        index -= 1

        return num, index


        


        
17600