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

标签: 栈 记忆化搜索 数组 数学 字符串 动态规划

难度: Hard

给你一个字符串 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

Submission

运行时间: 700 ms

内存: 26.0 MB

class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        n = len(s)
        stk = list()
        stk = list()
        # ans = 0
        for i in range(n):
            if "0" <= s[i] <= "9":
                if stk and stk[-1] == "*":
                    stk.pop()
                    num = stk.pop()
                    tmp = int(num) * int(s[i])
                    stk.append(str(tmp))
                    # print(i, stk)
                    continue
            stk.append(s[i])
            # print(i, stk)
        while len(stk) > 1:
            num1 = stk.pop()
            stk.pop()
            num2 = stk.pop()
            stk.append(str(int(num1) + int(num2)))
        right_ans = int(stk[-1])
        # print(right_ans)
        # res = set()
        @cache
        def dfs(s):
            sn = len(s)
            if sn == 1:
                return set([int(s)])
            res = set()
            for op in range(1, sn, 2):
                tmp1 = dfs(s[:op])
                tmp2 = dfs(s[op + 1:])
                # print(op)
                if s[op] == "*":
                    for t1 in tmp1:
                        for t2 in tmp2:
                            if t1 * t2 <= 1000:
                                res.add(t1 * t2)
                else:
                    for t1 in tmp1:
                        for t2 in tmp2:
                            if t1 + t2 <= 1000:
                                res.add(t1 + t2)
            # print(s, res)
            return res
        
        res = dfs(s)
        # print(res)
        
        f = 0
        for a in answers:
            if a == right_ans:
                f += 5
            elif a in res:
                f += 2
        return f

Explain

题解首先通过使用栈来计算表达式的正确结果，遵循给定的运算顺序：先从左到右完成所有的乘法，然后再完成所有的加法。接着，使用深度优先搜索（DFS）和记忆化技术，计算可能通过错误的运算顺序得到的所有结果，并将这些结果存储在集合中。最后，根据答案数组和这两个结果来为学生打分。

时间复杂度: O(3^15 + m)

空间复杂度: O(1001)

class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        n = len(s)
        stk = []
        # 遍历字符串，使用栈计算表达式正确结果
        for i in range(n):
            if '0' <= s[i] <= '9':
                if stk and stk[-1] == '*':
                    stk.pop()
                    num = stk.pop()
                    tmp = int(num) * int(s[i])
                    stk.append(str(tmp))
                    continue
            stk.append(s[i])
        # 计算加法
        while len(stk) > 1:
            num1 = stk.pop()
            stk.pop()
            num2 = stk.pop()
            stk.append(str(int(num1) + int(num2)))
        right_ans = int(stk[-1])
        # 缓存DFS结果，避免重复计算
        @cache
        def dfs(s):
            sn = len(s)
            if sn == 1:
                return set([int(s)])
            res = set()
            for op in range(1, sn, 2):
                tmp1 = dfs(s[:op])
                tmp2 = dfs(s[op + 1:])
                if s[op] == '*':
                    for t1 in tmp1:
                        for t2 in tmp2:
                            if t1 * t2 <= 1000:
                                res.add(t1 * t2)
                else:
                    for t1 in tmp1:
                        for t2 in tmp2:
                            if t1 + t2 <= 1000:
                                res.add(t1 + t2)
            return res
        res = dfs(s)
        # 根据正确答案和可能的错误运算结果给学生打分
        f = 0
        for a in answers:
            if a == right_ans:
                f += 5
            elif a in res:
                f += 2
        return f

Explore

在DFS函数中，递归分割的位置是基于表达式中的运算符位置确定的。函数遍历表达式字符串，每当遇到一个运算符（加号或乘号），它就将运算符两侧的字符串作为新的子表达式进行递归调用。这种分割确保了所有可能的运算顺序都被考虑，从而生成所有可能的结果。

将乘法运算的结果限制在1000以内主要是为了防止结果过大，这样可以减小计算复杂度和内存消耗。在实际情况中，特别是在教育或测试环境中，通常假设学生不会计算超过某个范围的数值。此外，限制结果也可以避免在递归过程中产生大量无效或不切实际的结果，从而提高算法的效率和执行速度。虽然理论上表达式的结果可能超过1000，但在这个应用场景中，设置这样的限制是合理的。

在计算过程中，题解通过遍历整个字符串来处理数字和运算符。对于每个字符，算法首先检查它是否是数字（通过比较字符是否在'0'到'9'之间）。如果是数字并且栈顶元素是乘号，则从栈中弹出乘号和之前的数字，执行乘法运算，并将结果推回栈中。如果不是乘号或栈为空，则直接将数字或运算符推入栈。在处理完所有字符后，再次遍历栈以执行加法运算，直到栈中只剩下一个元素，即为正确的表达式结果。

记忆化技术在题解中通过Python的`@cache`装饰器实现。这个装饰器应用于`dfs`函数，它自动存储每个不同输入字符串对应的计算结果，以避免重复计算相同的子表达式。在本题中，这种技术显著提高了效率，因为递归过程中存在许多重复的子问题。通过存储这些子问题的结果，算法可以直接使用已计算的值而不需要再次执行计算密集的递归，从而减少总的计算时间和提升性能。