<p>You are given a <strong>0-indexed</strong> string <code>expression</code> of the form <code>&quot;&lt;num1&gt;+&lt;num2&gt;&quot;</code> where <code>&lt;num1&gt;</code> and <code>&lt;num2&gt;</code> represent positive integers.</p>

<p>Add a pair of parentheses to <code>expression</code> such that after the addition of parentheses, <code>expression</code> is a <strong>valid</strong> mathematical expression and evaluates to the <strong>smallest</strong> possible value. The left parenthesis <strong>must</strong> be added to the left of <code>&#39;+&#39;</code> and the right parenthesis <strong>must</strong> be added to the right of <code>&#39;+&#39;</code>.</p>

<p>Return <code>expression</code><em> after adding a pair of parentheses such that </em><code>expression</code><em> evaluates to the <strong>smallest</strong> possible value.</em> If there are multiple answers that yield the same result, return any of them.</p>

<p>The input has been generated such that the original value of <code>expression</code>, and the value of <code>expression</code> after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.</p>

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

<pre>
<strong>Input:</strong> expression = &quot;247+38&quot;
<strong>Output:</strong> &quot;2(47+38)&quot;
<strong>Explanation:</strong> The <code>expression</code> evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that &quot;2(4)7+38&quot; is invalid because the right parenthesis must be to the right of the <code>&#39;+&#39;</code>.
It can be shown that 170 is the smallest possible value.
</pre>

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

<pre>
<strong>Input:</strong> expression = &quot;12+34&quot;
<strong>Output:</strong> &quot;1(2+3)4&quot;
<strong>Explanation:</strong> The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.
</pre>

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

<pre>
<strong>Input:</strong> expression = &quot;999+999&quot;
<strong>Output:</strong> &quot;(999+999)&quot;
<strong>Explanation:</strong> The <code>expression</code> evaluates to 999 + 999 = 1998.
</pre>

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

<ul>
	<li><code>3 &lt;= expression.length &lt;= 10</code></li>
	<li><code>expression</code> consists of digits from <code>&#39;1&#39;</code> to <code>&#39;9&#39;</code> and <code>&#39;+&#39;</code>.</li>
	<li><code>expression</code> starts and ends with digits.</li>
	<li><code>expression</code> contains exactly one <code>&#39;+&#39;</code>.</li>
	<li>The original value of <code>expression</code>, and the value of <code>expression</code> after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.</li>
</ul>

PRIORITY : Dict[str, int] = {
    '+': 0,
    '-': 0,
    '*': 1,
    '/': 1,
}
class Solution:
    # def minimizeResult(self, expression: str) -> str:
    #     min_val = float('inf')
    #     left_num, right_num = expression.split('+')
    #     left_idx, right_idx = None, None 
    #     for i in range(len(left_num)):
    #         for j in range(len(right_num)):
    #             new_val = int(left_num[:i] or 1) * \
    #                      (int(left_num[i:]) + int(right_num[:j+1])) * \
    #                       int(right_num[j+1:] or 1)
    #             if new_val < min_val:
    #                 min_val, left_idx, right_idx = new_val, i, j+1
    #     left_num = left_num[:left_idx] + '(' + left_num[left_idx:]
    #     right_num = right_num[:right_idx] + ')' + right_num[right_idx:]
    #     return left_num + '+' + right_num

    # def minimizeResult(self, s: str) -> str:
    #     left_num, right_num = s.split('+')
    #     strs = []
    #     for i in range(len(left_num)):
    #             if i == 0:
    #                 strs.append(left_num[:i]+'('+left_num[i:])
    #             else:
    #                 strs.append(left_num[:i]+'*('+left_num[i:])
    #     strs2 = []
    #     for j in range(len(right_num)):
    #         if j == len(right_num)-1:
    #             strs2.append(right_num[:j+1]+')'+right_num[j+1:])
    #         else:
    #             strs2.append(right_num[:j+1]+')*'+right_num[j+1:])
    #     expressions = []
    #     for left in strs:
    #         for right in strs2:
    #             expressions.append(left+'+'+right)

    #     min_val = float('inf')
    #     min_s = None
    #     for expression in expressions:
    #         cur_val = self.calculate(expression)
    #         if cur_val < min_val:
    #             min_val = cur_val
    #             min_s = expression
    #     return min_s.replace('*', '')
    
    # def calculate(self, s: str) -> int:
    #     # 此題為有加減乘除且有左右括號故不可以簡化
    #     stack: List[int | str] = []
    #     num = 0
    #     for char in s:
    #         if char.isdigit():
    #             num = num * 10 + ord(char) - ord('0')
    #         if char in '+-*/':
    #             # 判斷優先級
    #             while stack and stack[-1] != '(' \
    #                 and PRIORITY[stack[-1]] >= PRIORITY[char]:
    #                 operator = stack.pop()
    #                 prev_num = stack.pop()
    #                 num = self.calc(prev_num, num, operator)
    #             stack.append(num)
    #             stack.append(char)
    #             num = 0 # reset num to be zero after each iteration
    #         if char == '(':
    #             stack.append(char)
    #         if char == ')':
    #             while stack and stack[-1] != '(':
    #                 operator = stack.pop()
    #                 prev_num = stack.pop()
    #                 num = self.calc(prev_num, num, operator)
    #             stack.pop()
    #         else:
    #             continue 
    #     # when executing the LAST operation, like [10, '+'] left in the stack
    #     while stack:
    #         operator = stack.pop()
    #         prev_num = stack.pop()
    #         num = self.calc(prev_num, num, operator)
    #     return num 

    # def calc(self, prev, cur, op):
    #     if op == '+': return prev + cur 
    #     if op == '-': return prev - cur 
    #     if op == '*': return prev * cur 
    #     if op == '/': return int(prev / cur)


    def minimizeResult(self, s: str) -> str:
        #247+38
        left_num, right_num = s.split('+')
        # 247 and 38
        left_strs = []
        # 2*(47, (247, 24*(7
        for i in range(len(left_num)):
            if i == 0:
                left_strs.append(left_num[:i]+'('+left_num[i:])
            else:
                left_strs.append(left_num[:i]+'*('+left_num[i:])
        right_strs = []
        # 3)*8, 38)
        for i in range(len(right_num)):
            if i == len(right_num)-1:
                right_strs.append(right_num[:i+1]+')'+right_num[i+1:])
            else:
                right_strs.append(right_num[:i+1]+')*'+right_num[i+1:])
        print(left_strs, right_strs)
        expressions = []
        for left in left_strs:
            for right in right_strs:
                expressions.append(left + '+' + right)
        print('expressions')
        min_val = float('inf')
        min_s = None 
        for expression in expressions:
            cur_val = self.calculate(expression)
            if cur_val < min_val:
                min_val = cur_val
                min_s = expression
        return min_s.replace('*', '')
    
    def calculate(self, s: str) -> int:
        stack: List[str|int] = []
        res = 0
        for char in s:
            if char.isdigit():
                res = res * 10 + ord(char) - ord('0')
            if char in '+*':
                while stack and stack[-1] != '(' and \
                    PRIORITY[stack[-1]] >= PRIORITY[char]:
                    op = stack.pop()
                    prev = stack.pop()
                    res = self.compute(prev, res, op)
                stack.append(res)
                stack.append(char)
                res = 0
            if char == '(':
                stack.append(char)
            if char == ')':
                while stack and stack[-1] != '(':
                    op = stack.pop()
                    prev = stack.pop()
                    res = self.compute(prev, res, op)
                stack.pop()
            else:
                continue 
        while stack:
            op = stack.pop()
            prev = stack.pop()
            res = self.compute(prev, res, op)        
        return res
    
    def compute(self, prev, cur, op):
        if op == '+':
            return prev + cur 
        if op == '*':
            return prev * cur

33