2019-解出数学表达式的学生分数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个字符串 s ，它 只 包含数字 0-9 ，加法运算符 '+' 和乘法运算符 '*' ，这个字符串表示一个 合法
的只含有 个位数 数字 的数学表达式（比方说 3+5*2）。有 n 位小学生将计算这个数学表达式，并遵循如下 运算顺序
：

  1. 按照 从左到右 的顺序计算 乘法 ，然后
  2. 按照 从左到右 的顺序计算 加法 。

给你一个长度为 n 的整数数组 answers ，表示每位学生提交的答案。你的任务是给 answer 数组按照如下 规则 打分：

  • 如果一位学生的答案 等于 表达式的正确结果，这位学生将得到 5 分。
  • 否则，如果答案由 一处或多处错误的运算顺序 计算得到，那么这位学生能得到 2 分。
  • 否则，这位学生将得到 0 分。

请你返回所有学生的分数和。

示例 1：

**输入：** s = "7+3*1*2", answers = [20,13,42]
**输出：** 7
**解释：** 如上图所示，正确答案为 13 ，因此有一位学生得分为 5 分：[20, _ **13**_ ,42] 。
一位学生可能通过错误的运算顺序得到结果 20 ：7+3=10，10*1=10，10*2=20 。所以这位学生得分为 2 分：[ _ **20**_ ,13,42] 。
所有学生得分分别为：[2,5,0] 。所有得分之和为 2+5+0=7 。

示例 2：

**输入：** s = "3+5*2", answers = [13,0,10,13,13,16,16]
**输出：** 19
**解释：** 表达式的正确结果为 13 ，所以有 3 位学生得到 5 分：[ _ **13**_ ,0,10, _ **13**_ , _ **13**_ ,16,16] 。
学生可能通过错误的运算顺序得到结果 16 ：3+5=8，8*2=16 。所以两位学生得到 2 分：[13,0,10,13,13, _ **16**_ , _ **16**_ ] 。
所有学生得分分别为：[5,0,0,5,5,2,2] 。所有得分之和为 5+0+0+5+5+2+2=19 。

示例 3：

**输入：** s = "6+0*1", answers = [12,9,6,4,8,6]
**输出：** 10
**解释：** 表达式的正确结果为 6 。
如果一位学生通过错误的运算顺序计算该表达式，结果仍为 6 。
根据打分规则，运算顺序错误的学生也将得到 5 分（因为他们仍然得到了正确的结果），而不是 2 分。
所有学生得分分别为：[0,0,5,0,0,5] 。所有得分之和为 10 分。

提示：

  • 3 <= s.length <= 31
  • s 表示一个只包含 0-9 ，'+' 和 '*' 的合法表达式。
  • 表达式中所有整数运算数字都在闭区间 [0, 9] 以内。
  • 1 <= 数学表达式中所有运算符数目（'+' 和 '*'） <= 15
  • 测试数据保证正确表达式结果在范围 [0, 1000] 以内。
  • n == answers.length
  • 1 <= n <= 104
  • 0 <= answers[i] <= 1000

思路

这个题难点在于对运算顺序自由组合时，不知道怎么做组合。
其实可以简单的把一个表达式，拆分成
总表达式 = (左侧表达式) 运算符 (右侧表达式)
的形式，先计算左侧表达式所有可能结果，再计算右侧表达式所有可能结果，再两两组合得到总表达式的所有结果。

具体操作时，对于一个总表达式，枚举它内部所有的运算符位置，然后每次计算左和右。可以观察到，左和右表达式显然长度≤总表达式长度，不难想到应该用 dp 来解。

具体代码时，使用区间 dp 的方法，使用一个二维数组 dp[i][j] 表示字符串 s[i..j] 总共可以通过调换计算顺序，得到哪些计算结果。

如此一来，假设我们知道了两个区间结果 dp[i][k] 和 dp[k][j]，那我们就可以通过
dp[i][j]={x ○ y | x \in dp[i][k] \ and \ y \in dp[k][j]
来一步步从小区间扩大到大区间。

Step 1：统计回答

思路

因为错误的计算结果可能有很多种，所以我们先对所有学生提交的结果做一个简单统计，后续就不需要每次都 O(N) 遍历了。

代码及注释

1
2
3
4
5
// 所有学生答案都在[0, 1000]，因此开一个差不多大小的空间即可
vector<int> count(1024); 
for(auto p : answer){
  count[p]++;
}

Step 2：计算正确结果

思路

使用加法入栈，乘法直接将栈顶元素做乘法的方法，计算正确结果。

解释

顺序遍历时

  • 对于 a + b ...，由于不知道 b 之后是否涉及到乘法运算，因此不可以直接将 a 与 b 相加，而是应该暂时把两个数都放在栈中；
  • 对于 a * b ...，乘法运算优先级最高，因此此处直接计算 a * b 的值，并更新栈顶的 a 的值为 a * b

代码及注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
stack<int> st;
st.push(s[0] - '0'); // 第一个元素入栈
for(int i = 1; i < s.length(); i += 2){
    if(s[i] == '+'){ // 加法运算，暂不做，存到栈顶
        st.push(s[i + 1] - '0');
    }
    else{ // 乘法运算，直接做
        st.top() *= (s[i + 1] - '0');
    }
}
// 弹栈，计算所有加法运算
int right = 0;
while(st.size() > 0){
    right += st.top();
    st.pop();
}
// 正确的得分 = 5 * 正确人数
int ans = 5 * count[right];

Step 3：枚举所有可能结果

思路

这一步中，使用区间 dp 的方法，使用一个二维数组 dp[i][j] 表示字符串 s[i..j] 总共可以通过调换计算顺序，得到哪些计算结果，dp[i][j] 是一个集合。

初始化

初始条件时，是 i=j，此时 dp[i][j] = {s[i] - ‘0’

递推关系

对于一个区间 dp[i][j]，我们有 dp[i][j] = {dp[i][k] ○ dp[k][j] \ 其中 i≤k≤j，符号 ○ 表示加号或乘号关系。

额外Tips

这里需要引入一个剪枝，否则会因为爆 int 而出错。就是如果中间的某个计算结果已经超过 1000 了，应该直接忽略。

这是因为无论是加法还是乘法，都是一个不减的操作，当计算结果已经超过 1000 时，无论如何组合，则最终表达式的值一定不在学生猜测范围 [0,1000] 内，因此可以忽略。

代码及注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 开空间，dp为n*n的数组，每一项为一个集合
int len = s.length();
vector<vector<unordered_set<int>>> dp(len + 2, vector<unordered_set<int>>(len + 2));
// 初始化，对于i=j情况，能组成的值为其本身
for(int j = 0; j < len; j += 2){
    dp[j][j].insert(s[j] - '0');
}
// 枚举步伐，不断增大，即 step = j-i
for(int step = 2; step < len; step += 2){
    // 枚举开始位置 i
    for(int i = 0; i + step < len; i += 2){
        // 枚举左半部分长度 t
        for(int t = 0; t < step; t += 2){
            // x是左半部分所有可能值
            // y是右半部分所有可能值
            for(auto x : dp[i][i + t]){
                for(auto y : dp[i + t + 2][i + step]){
                    // 根据中间连接符是+/*，来计算连接后的值
                    if(s[i + t + 1] == '+'){
                        // 因为学生猜测结果均在 [0,1000]，因此超限的值可以直接忽略。
                        if(x + y <= 1000)
                        dp[i][i + step].insert(x + y);
                    }
                    else{
                        if(x * y <= 1000)
                        dp[i][i + step].insert(x * y);
                    }
                }
            }
        }
    }
}

Step 4：统计所有错误结果

思路

上一步计算的 dp[0][len-1] 就是整个字符串，所有可能的计算结果。结合第一步统计的学生答案，做累加

代码及注释

1
2
3
4
5
for(auto p : dp[0][len - 1]){
    if(p != right){ // 只有错误答案需要统计，防止二次统计正确同学
        ans += 2 * count[p];
    }
}

Step 5：完整代码及注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
public:
    int scoreOfStudents(string s, vector<int>& answers) {
        // Step 1：统计所有学生答案
        // 所有学生答案都在[0, 1000]，因此开一个差不多大小的空间即可
        vector<int> count(1024);
        for(auto p : answers){
            count[p]++;
        }
        
        // Step 2：计算正确结果
                stack<int> st;
        st.push(s[0] - '0'); // 第一个元素入栈
        for(int i = 1; i < s.length(); i += 2){
            if(s[i] == '+'){ // 加法运算，暂不做，存到栈顶
                st.push(s[i + 1] - '0');
            }
            else{ // 乘法运算，直接做
                st.top() *= (s[i + 1] - '0');
            }
        }
        // 弹栈，计算所有加法运算
        int right = 0;
        while(st.size() > 0){
            right += st.top();
            st.pop();
        }
        // 正确的得分 = 5 * 正确人数
        int ans = 5 * count[right];
        
        // Step 3：枚举所有可能结果
        // 开空间，dp为n*n的数组，每一项为一个集合
        int len = s.length();
        vector<vector<unordered_set<int>>> dp(len + 2, vector<unordered_set<int>>(len + 2));
        // 初始化，对于i=j情况，能组成的值为其本身
        for(int j = 0; j < len; j += 2){
            dp[j][j].insert(s[j] - '0');
        }
        // 枚举步伐，不断增大，即 step = j-i
        for(int step = 2; step < len; step += 2){
            // 枚举开始位置 i
            for(int i = 0; i + step < len; i += 2){
                // 枚举左半部分长度 t
                for(int t = 0; t < step; t += 2){
                    // x是左半部分所有可能值
                    // y是右半部分所有可能值
                    for(auto x : dp[i][i + t]){
                        for(auto y : dp[i + t + 2][i + step]){
                            // 根据中间连接符是+/*，来计算连接后的值
                            if(s[i + t + 1] == '+'){
                                // 因为学生猜测结果均在 [0,1000]，因此超限的值可以直接忽略。
                                if(x + y <= 1000)
                                dp[i][i + step].insert(x + y);
                            }
                            else{
                                if(x * y <= 1000)
                                dp[i][i + step].insert(x * y);
                            }
                        }
                    }
                }
            }
        }
        // Step 4：统计顺序错误同学得分
        for(auto p : dp[0][len - 1]){
            if(p != right){ // 只有错误答案需要统计，防止二次统计正确同学
	            ans += 2 * count[p];
	        }
	    }
        return ans;
    }
};
 Comments
On this page
2019-解出数学表达式的学生分数
  1. 思路
  2. Step 1：统计回答
  3. Step 2：计算正确结果
  4. Step 3：枚举所有可能结果
  5. Step 4：统计所有错误结果
  6. Step 5：完整代码及注释