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


	Compute multiplication, reading from left to right; Then,
	Compute addition, reading from left to right.


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


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


Return the sum of the points of the students.

&nbsp;
Example 1:

Input: s = "7+3*1*2", answers = [20,13,42]
Output: 7
Explanation: As illustrated above, the correct answer of the expression is 13, therefore one student is rewarded 5 points: [20,13,42]
A student might have applied the operators in this wrong order: ((7+3)*1)*2 = 20. Therefore one student is rewarded 2 points: [20,13,42]
The points for the students are: [2,5,0]. The sum of the points is 2+5+0=7.


Example 2:

Input: s = "3+5*2", answers = [13,0,10,13,13,16,16]
Output: 19
Explanation: The correct answer of the expression is 13, therefore three students are rewarded 5 points each: [13,0,10,13,13,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,16,16]
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.


Example 3:

Input: s = "6+0*1", answers = [12,9,6,4,8,6]
Output: 10
Explanation: 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.


&nbsp;
Constraints:


	3 &lt;= s.length &lt;= 31
	s represents a valid expression that contains only digits 0-9, '+', and '*' only.
	All the integer operands in the expression are in the inclusive range [0, 9].
	1 &lt;= The count of all operators ('+' and '*') in the math expression &lt;= 15
	Test data are generated such that the correct answer of the expression is in the range of [0, 1000].
	n == answers.length
	1 &lt;= n &lt;= 104
	0 &lt;= answers[i] &lt;= 1000


class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        
        @cache
        def fn(lo, hi): 
            """Return possible answers of s[lo:hi]."""
            if lo+1 == hi: return {int(s[lo])}
            ans = set()
            for mid in range(lo+1, hi, 2): 
                for x in fn(lo, mid): 
                    for y in fn(mid+1, hi): 
                        if s[mid] == "+" and x + y <= 1000: ans.add(x + y)
                        elif s[mid] == "*" and x * y <= 1000: ans.add(x * y)
            return ans 
                
        target = eval(s)
        cand = fn(0, len(s))
        ans = 0 
        for x in answers: 
            if x == target: ans += 5
            elif x in cand: ans += 2
        return ans 
class Solution {

    HashMap<String , HashSet<Integer>> cache ;

    public int scoreOfStudents(String s, int[] answers) {

        cache = new HashMap();
        HashSet<Integer> total_possible_ans = getPossibleAns(s);

        int correct_ans = getCorrectAns(s);

        int total_score = 0 ;
        for(int i=0 ; i<answers.length ; i++){
            if(answers[i] == correct_ans){
                total_score += 5 ;
            }else if(total_possible_ans.contains(answers[i])){
                total_score += 2 ;
            }
        }

        return total_score ;
    }

    public HashSet<Integer> getPossibleAns(String s){

        if(cache.containsKey(s)){
            return cache.get(s) ;
        }

        HashSet<Integer> possible_ans = new HashSet() ;

        for(int i = 0 ; i<s.length() ; i++){

            char cur = s.charAt(i) ;
            HashSet<Integer> left = new HashSet() ;
            HashSet<Integer> right = new HashSet() ;

            if(cur == '+' || cur == '*'){
                left = getPossibleAns(s.substring(0 , i));
                right = getPossibleAns(s.substring(i+1));
            }

            for(Integer l : left){
                for(Integer r : right){
                    if(cur == '+'){
                        if(l+r > 1000) continue ; // skiping for ans that are greater than 1000
                        possible_ans.add(l+r);
                    }else if(cur == '*'){
                        if(l*r > 1000) continue ; // skiping for ans that are greater than 1000
                        possible_ans.add(l*r);
                    }
                }
            }
        }

        if(possible_ans.isEmpty() && s.length() <= 1){
            possible_ans.add(Integer.parseInt(s));
        }

        cache.put(s , possible_ans);

        return possible_ans ;
    }

    public int getCorrectAns(String s) {

        Stack<Integer> stack = new Stack() ;

        for(int i = 0 ; i<s.length() ; i++){

            // push only integers into stack
            if(s.charAt(i) != '+' && s.charAt(i) != '*'){
                stack.push(Character.getNumericValue(s.charAt(i))) ;
            }

            // If operator is '*' , then take the last element from stack and multiply with next element
            // Also push into stack , and then increment i also , to avoid pushing the same next element into stack again
            if(s.charAt(i) == '*'){
                int cur = stack.pop();
                int next = Character.getNumericValue(s.charAt(i+1)) ;
                stack.push(cur * next);
                i++ ;
            }
        }

        // Now sum all the element in the stack to get result for '+' operator
        int total_sum = stack.pop() ;

        while(!stack.isEmpty()){
            total_sum += stack.pop() ;
        }

        return total_sum ;
    }

}
class Solution {
    int eval(int a, int b, char op) {
        if (op == '+') {
            return a + b;
        } else {
            return a * b;
        }
    }
    
    unordered_map<string_view, unordered_set<int>> mp;
    unordered_set<int> potential;
    
    unordered_set<int>& solve(string_view s) {
        if (auto it = mp.find(s); it != mp.end()) {
            return it->second;
        }
        
        bool res = true;
        int n = 0;
        unordered_set<int> ans;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (c >= '0' && c <= '9') {
                n = n * 10 + (c - '0');
            } else {
                n = 0;
                res = false;
                for (int l : solve(s.substr(0, i))) {
                    for (int r : solve(s.substr(i + 1))) {
                        int res2 = eval(l, r, c);
                        if (res2 <= 1000) {
                            ans.insert(res2);
                        }
                    }
                }
            }
        }
        if (res) {
            ans.insert(n);
        }
        return mp[s] = ans;
    }
    
public:
    int scoreOfStudents(string s, vector<int>& answers) {
        int ans = 0, correct = 0;
        stack<int> ns, op;
        unordered_map<char, int> prec{
            {'+', 1},
            {'*', 2},
            {'(', 0}
        };
        int n = 0;
        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (c >= '0' && c <= '9') {
                n = n * 10 + (c - '0');
            } else if (c == '(') {
                op.push(c);
            } else if (c == ')') {
                ns.push(n);
                while (op.top() != '(') {
                    int b = ns.top();
                    ns.pop();
                    int a = ns.top();
                    ns.pop();
                    ns.push(eval(a, b, op.top()));
                    op.pop();
                }
                op.pop();
                n = ns.top();
                ns.pop();
            } else {
                ns.push(n);
                n = 0;
                int p = prec[c];
                while (!op.empty() && prec[op.top()] >= p) {
                    int b = ns.top();
                    ns.pop();
                    int a = ns.top();
                    ns.pop();
                    ns.push(eval(a, b, op.top()));
                    op.pop();
                }
                op.push(c);
            }
        }
        ns.push(n);
        while (!op.empty()) {
            int b = ns.top();
            ns.pop();
            int a = ns.top();
            ns.pop();
            ns.push(eval(a, b, op.top()));
            op.pop();
        }
        correct = ns.top();
        
        string_view sv{s.data(), s.size()};
        solve(sv);
        for (int n2 : mp[sv]) {
            potential.insert(n2);
        }
        
        for (int n2 : answers) {
            if (n2 == correct) {
                ans += 5;
            } else if (potential.find(n2) != potential.end()) {
                ans += 2;
            }
        }
        return ans;
    }
};
var scoreOfStudents = function(s, answers) {
    let correct=s.split('+').reduce((a,c)=>a+c.split('*').reduce((b,d)=>b*d,1),0),
        n=s.length,dp=[...Array(n)].map(d=>[...Array(n)])
    let dfs=(i=0,j=n-1)=>{
        if(dp[i][j]!==undefined)
            return dp[i][j]
        if(i===j)
            return dp[i][j]=[Number(s[i])]
        let ans=new Set()
        for(let k=i+1;k<=j-1;k+=2)
            for(let a1 of dfs(i,k-1))
                for(let a2 of dfs(k+1,j))
                    if(s[k]==='*')
                        ans.add(Number(a1)*Number(a2))
                    else
                        ans.add(Number(a1)+Number(a2))
        return dp[i][j]=Array.from(ans).filter(d=>d<=1000)
    }
    dfs()
    dp[0][n-1]=new Set(dp[0][n-1])
    return answers.reduce( (a,c)=> a+ (c===correct?5:(dp[0][n-1].has(c)?2:0)) ,0)
};
The Score of Students Solving Math Expression