2019. The Score of Students Solving Math Expression

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+52). 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:

1. Compute multiplication, reading from left to right; Then,
2. 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.

class Solution {
    unordered_set<int> dp[32][32];
    unordered_set<int> dfs(string& s, int st, int ed) {
        if(dp[st][ed].size()) return dp[st][ed];

        if(ed - st == 1) dp[st][ed].insert(s[st] & 0b1111);

        for(int i = st + 1; i < ed; i += 2) {
            auto res1 = dfs(s,st,i);
            auto res2 = dfs(s,i+1,ed);
            for(auto& n : res1)
                for(auto& m : res2) {
                    int op = s[i] == '+' ? n + m : n * m;
                    if(op <= 1000) dp[st][ed].insert(op);
                }

        }
        return dp[st][ed];
    }
    int answer(string s) {
        vector<string> st;
        for(int i = 0; i < s.length(); i++) {

            if('0' <= s[i] and s[i] <= '9') {
                if(st.empty() || st.back() == "+") {
                    st.push_back(string(1,s[i]));
                } else {
                    st.pop_back();
                    int num1 = stoi(st.back());
                    int num2 = s[i] & 0b1111;
                    st.pop_back();
                    st.push_back(to_string(num1 * num2));
                }
            } else st.push_back(string(1,s[i]));
        }
        int res = 0;
        while(!st.empty()) {
            string back = st.back();
            st.pop_back();
            if(back == "+") continue;
            res += stoi(back);
        }
        return res;
    }
public:
    int scoreOfStudents(string s, vector<int>& answers) {
        int len = s.length();
        auto comb = dfs(s,0, len);
        int ans = answer(s);
        int res = 0;
        for(auto& a : answers) {
            if(a == ans) res += 5;
            else if(comb.count(a)) res += 2;
        }
        return res;
    }
};