<p>You are given a string <code>s</code> that contains digits <code>0-9</code>, addition symbols <code>&#39;+&#39;</code>, and multiplication symbols <code>&#39;*&#39;</code> <strong>only</strong>, representing a <strong>valid</strong> math expression of <strong>single digit numbers</strong> (e.g., <code>3+5*2</code>). This expression was given to <code>n</code> elementary school students. The students were instructed to get the answer of the expression by following this <strong>order of operations</strong>:</p>

<ol>
	<li>Compute <strong>multiplication</strong>, reading from <strong>left to right</strong>; Then,</li>
	<li>Compute <strong>addition</strong>, reading from <strong>left to right</strong>.</li>
</ol>

<p>You are given an integer array <code>answers</code> of length <code>n</code>, which are the submitted answers of the students in no particular order. You are asked to grade the <code>answers</code>, by following these <strong>rules</strong>:</p>

<ul>
	<li>If an answer <strong>equals</strong> the correct answer of the expression, this student will be rewarded <code>5</code> points;</li>
	<li>Otherwise, if the answer <strong>could be interpreted</strong> as if the student applied the operators <strong>in the wrong order</strong> but had <strong>correct arithmetic</strong>, this student will be rewarded <code>2</code> points;</li>
	<li>Otherwise, this student will be rewarded <code>0</code> points.</li>
</ul>

<p>Return <em>the sum of the points of the students</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/17/student_solving_math.png" style="width: 678px; height: 109px;" />
<pre>
<strong>Input:</strong> s = &quot;7+3*1*2&quot;, answers = [20,13,42]
<strong>Output:</strong> 7
<strong>Explanation:</strong> As illustrated above, the correct answer of the expression is 13, therefore one student is rewarded 5 points: [20,<u><strong>13</strong></u>,42]
A student might have applied the operators in this wrong order: ((7+3)*1)*2 = 20. Therefore one student is rewarded 2 points: [<u><strong>20</strong></u>,13,42]
The points for the students are: [2,5,0]. The sum of the points is 2+5+0=7.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;3+5*2&quot;, answers = [13,0,10,13,13,16,16]
<strong>Output:</strong> 19
<strong>Explanation:</strong> The correct answer of the expression is 13, therefore three students are rewarded 5 points each: [<strong><u>13</u></strong>,0,10,<strong><u>13</u></strong>,<strong><u>13</u></strong>,16,16]
A student might have applied the operators in this wrong order: ((3+5)*2 = 16. Therefore two students are rewarded 2 points: [13,0,10,13,13,<strong><u>16</u></strong>,<strong><u>16</u></strong>]
The points for the students are: [5,0,0,5,5,2,2]. The sum of the points is 5+0+0+5+5+2+2=19.
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;6+0*1&quot;, answers = [12,9,6,4,8,6]
<strong>Output:</strong> 10
<strong>Explanation:</strong> The correct answer of the expression is 6.
If a student had incorrectly done (6+0)*1, the answer would also be 6.
By the rules of grading, the students will still be rewarded 5 points (as they got the correct answer), not 2 points.
The points for the students are: [0,0,5,0,0,5]. The sum of the points is 10.
</pre>

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

<ul>
	<li><code>3 &lt;= s.length &lt;= 31</code></li>
	<li><code>s</code> represents a valid expression that contains only digits <code>0-9</code>, <code>&#39;+&#39;</code>, and <code>&#39;*&#39;</code> only.</li>
	<li>All the integer operands in the expression are in the <strong>inclusive</strong> range <code>[0, 9]</code>.</li>
	<li><code>1 &lt;=</code> The count of all operators (<code>&#39;+&#39;</code> and <code>&#39;*&#39;</code>) in the math expression <code>&lt;= 15</code></li>
	<li>Test data are generated such that the correct answer of the expression is in the range of <code>[0, 1000]</code>.</li>
	<li><code>n == answers.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= answers[i] &lt;= 1000</code></li>
</ul>

class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        n = len(answers)
        
        correct_ans = self.eval_correct(s)
        s_list = self.make_s_list(s)
        dp = {}
        
        def eval_incorrect(s_list, left, right):
            if left == right:
                return [s_list[left]]
            if (left, right) in dp:
                return dp[(left, right)]

            all_answers = set()
            for i in range(left, right + 1):
                c = s_list[i]
                if c not in ['+', '*']:
                    continue
                left_answers = eval_incorrect(s_list, left, i - 1)
                right_answers = eval_incorrect(s_list, i + 1, right)
                
                if c == '+':
                    for x in left_answers:
                        for y in right_answers:
                            if x + y > 1000:
                                continue
                            all_answers.add(x + y)
                else:
                    for x in left_answers:
                        for y in right_answers:
                            if x * y > 1000:
                                continue
                            all_answers.add(x * y)

            dp[(left, right)] = all_answers
            return all_answers

        all_answers = eval_incorrect(s_list, 0, len(s_list) - 1)
        res = 0
        for ans in answers:
            if ans == correct_ans:
                res += 5
            elif ans in all_answers:
                res += 2
        return res

    def make_s_list(self, s):
        res = []
        curr_num = 0
        for c in s:
            if c not in ['+', '*']:
                curr_num = 10 * curr_num + int(c)
                continue
            res.append(curr_num)
            res.append(c)
            curr_num = 0
        res.append(curr_num)
        return res

    def eval_correct(self, s):
        stack = []
        curr_num = 0
        prev_op = '+'
        for c in s:
            if c not in ['+', '*']:
                curr_num = 10 * curr_num + int(c)
                continue

            if prev_op == '+':
                stack.append(curr_num)
            else:
                stack.append(stack.pop() * curr_num)
            prev_op = c
            curr_num = 0
        if prev_op == '+':
            stack.append(curr_num)
        else:
            stack.append(stack.pop() * curr_num)
        return sum(stack)


































        # """
        # Solution 1:
        # """
        # stack = [0]
        # n = len(s)
        # op = "+"
        # for i in range(n):
        #     c = s[i]
        #     if c.isdigit():
        #         num = int(c)
        #         if op == "+":
        #             stack.append(num)
        #         elif op == "*":
        #             prev_num = stack.pop()
        #             stack.append(prev_num * num)
        #             op = "+"
        #     else:
        #         if c == "+":
        #             op = "+"
        #         else:
        #             op = "*"
        # correct = sum(stack)

        # seen = {}
        # def f(i, j):
        #     if i == j:
        #         return set([int(s[i])])
        #     if (i, j) in seen:
        #         return seen[(i, j)]
        #     res = set()
        #     for op_idx in range(i + 1, j):
        #         if s[op_idx] not in ["+", "*"]:
        #             continue
        #         op = s[op_idx]
        #         left_list = f(i, op_idx - 1)
        #         right_list = f(op_idx + 1, j)
        #         for x in left_list:
        #             for y in right_list:
        #                 if op == "+":
        #                     if x + y <= 1000:
        #                         res.add(x + y)
        #                 else:
        #                     if x * y <= 1000:
        #                         res.add(x * y)
        #     seen[(i, j)] = res
        #     return res
        
        # possible = f(0, n-1)
        # res = 0
        # for answer in answers:
        #     if answer == correct:
        #         res += 5
        #     elif answer in possible:
        #         res += 2
        # return res

        # """
        # Solution 2:
        # Correct but TLE
        # The complexity is essentially the same as Solution 1, but we don't prune.
        # """
        # # stack = [0]
        # # n = len(s)
        # # op = "+"
        # # for i in range(n):
        # #     c = s[i]
        # #     if c.isdigit():
        # #         num = int(c)
        # #         if op == "+":
        # #             stack.append(num)
        # #         elif op == "*":
        # #             prev_num = stack.pop()
        # #             stack.append(prev_num * num)
        # #             op = "+"
        # #     else:
        # #         if c == "+":
        # #             op = "+"
        # #         else:
        # #             op = "*"
        # # correct = sum(stack)

        # # possible = set()
        # # # these are ordered according to appearance in s
        # # digits = [int(c) for c in s if c.isdigit()]
        # # ops = [c for c in s if not c.isdigit()]

        # # # group adjacent digits and recurse
        # # # need to group each pair of adjacent digits to try all possibilities
        # # seen = set()
        # # def f(digits, ops):
        # #     if len(digits) == 1:
        # #         possible.add(digits[0])
        # #         return
        # #     if (tuple(digits), tuple(ops)) in seen:
        # #         return
            
        # #     for i in range(len(digits) - 1):
        # #         remaining_digits = []
        # #         remaining_ops = []
                
        # #         for j in range(i):
        # #             remaining_digits.append(digits[j])
        # #         x, y = digits[i], digits[i+1]
                
        # #         op_idx = i
        # #         op = ops[op_idx]
        # #         for j in range(len(ops)):
        # #             if j != i:
        # #                 remaining_ops.append(ops[j])
                
        # #         if op == "+":
        # #             if x + y <= 1000:
        # #                 remaining_digits.append(x + y)
        # #             else:
        # #                 continue
        # #         else:
        # #             if x * y <= 1000:
        # #                 remaining_digits.append(x * y)
        # #             else:
        # #                 continue
                
        # #         for j in range(i + 2, len(digits)):
        # #             remaining_digits.append(digits[j])
        # #         f(remaining_digits, remaining_ops)
        # #         seen.add((tuple(remaining_digits), tuple(remaining_ops)))
        
        # # f(digits, ops)
        # # res = 0
        # # for answer in answers:
        # #     if answer == correct:
        # #         res += 5
        # #     elif answer in possible:
        # #         res += 2
        # # return res
26300