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:
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:
5 points;2 points;0 points.Return the sum of the points of the students.
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.
Constraints:
3 <= s.length <= 31s represents a valid expression that contains only digits 0-9, '+', and '*' only.[0, 9].1 <= The count of all operators ('+' and '*') in the math expression <= 15[0, 1000].n == answers.length1 <= n <= 1040 <= answers[i] <= 1000Problem Overview: You are given a math expression containing digits, +, and *. Students submit answers after evaluating the expression, sometimes applying incorrect operator precedence. You must award 5 points for the correct answer and 2 points for answers that could appear from a valid but incorrectly parenthesized evaluation.
Approach 1: Evaluate with Left-to-Right Multiplication First (Stack Evaluation) (O(n) time, O(n) space)
First compute the correct value of the expression using normal arithmetic precedence where multiplication happens before addition. Scan the string and use a stack to handle multiplication immediately while deferring addition. When a digit is read, multiply with the top of the stack if the previous operator is *; otherwise push it. The final result is the sum of stack values. This step gives the true answer used to award 5 points and serves as the baseline for scoring.
Approach 2: Evaluate with Brackets (Alternate Total Order) using Dynamic Programming (O(n^3) time, O(n^2) space)
Students who ignore operator precedence effectively evaluate the expression using arbitrary parenthesization. Model this with interval dynamic programming. Let dp[i][j] store all possible values produced from the substring between numbers i and j. For every operator position k, combine results from dp[i][k] and dp[k+1][j] using the operator. Use memoization to avoid recomputing intervals and keep only results ≤1000 as required by the problem constraints. This generates the complete set of answers a student could produce when evaluating the expression incorrectly.
After computing both values, iterate through the students' answers array. If an answer equals the correct evaluation, add 5. If it exists in the DP-generated set of possible incorrect results, add 2. Otherwise add 0. The DP essentially enumerates every possible evaluation tree of the expression using techniques common in stack and expression parsing problems.
Recommended for interviews: Interviewers expect the dynamic programming interval solution combined with correct expression evaluation. The stack-based evaluation shows you understand operator precedence, while the DP demonstrates deeper algorithmic reasoning about expression trees and subproblem reuse.
This approach involves evaluating the expression by computing multiplication first, strictly from left to right, followed by addition. This simulates the way the students are supposed to solve it according to the problem statement.
First, parse the expression and perform multiplication operations in sequence. Next, sum up the resulting values for the final evaluation.
This C function parses the string character by character, performing multiplications when encountering the '*' symbol and additions when encountering the '+' symbol. The multiplications are evaluated immediately, and the current running total is only updated with additions. This function returns the final evaluated value according to the left-to-right rule.
Time Complexity: O(n), where n is the length of the string as each character is processed once.
Space Complexity: O(1), as only a fixed amount of additional memory is used.
This approach evaluates the expression assuming operators don’t follow precedence rules, using only left-to-right order. This simulates potential misinterpretations by students while respecting arithmetic correctness.
C code showcases handling of operations strictly as they appear, without considering multiplication precedence, thereby evaluating left-to-right only.
Time Complexity: O(n), iterating over each character once.
Space Complexity: O(1), Constant space complexity due to primitive variables.
First, we design a function cal(s) to calculate the result of a valid mathematical expression that only contains single-digit numbers. The correct answer is x = cal(s).
Let the length of the string s be n, then the number of digits in s is m = \frac{n+1}{2}.
We define f[i][j] as the possible values of the result calculated by selecting the digits from the i-th to the j-th in s (index starts from 0). Initially, f[i][i] represents the selection of the i-th digit, and the result can only be this digit itself, i.e., f[i][i] = {s[i times 2]} (the i-th digit maps to the character at index i times 2 in the string s).
Next, we enumerate i from large to small, and then enumerate j from small to large. We need to find out the possible values of the results of the operation of all digits in the interval [i, j]. We enumerate the boundary point k in the interval [i, j], then f[i][j] can be obtained from f[i][k] and f[k+1][j] through the operator s[k times 2 + 1]. Therefore, we can get the following state transition equation:
$
f[i][j] = \begin{cases}
{s[i times 2]}, & i = j \
\bigcup\limits_{k=i}^{j-1} {f[i][k] \otimes f[k+1][j]}, & i < j
\end{cases}
Where \otimes represents the operator, i.e., s[k times 2 + 1].
The possible values of the results of all digit operations in the string s are f[0][m-1].
Finally, we count the answer. We use an array cnt to count the number of times each answer appears in the answer array answers. If the answer is equal to x, then this student gets 5 points, otherwise if the answer is in f[0][m-1], then this student gets 2 points. Traverse cnt to count the answer.
The time complexity is O(n^3 times M^2), and the space complexity is O(n^2 times M^2). Here, M is the maximum possible value of the answer, and n is the number of digits in the length of the string s$.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Evaluate with Left-to-Right Multiplication First | Time Complexity: O(n), where n is the length of the string as each character is processed once. |
| Evaluate with Brackets (Alternate Total Order) | Time Complexity: O(n), iterating over each character once. |
| Dynamic Programming (Interval DP) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack Evaluation for Correct Result | O(n) | O(n) | Compute the true expression value with standard precedence |
| Interval Dynamic Programming (All Parenthesizations) | O(n^3) | O(n^2) | Generate all valid results from incorrect evaluation orders |
| Memoized Recursive Expression Evaluation | O(n^3) | O(n^2) | Cleaner implementation of the same interval DP idea |
LeetCode 2019. The Score of Students Solving Math Expression • Happy Coding • 1,586 views views
Watch 3 more video solutions →Practice The Score of Students Solving Math Expression with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor