Watch 4 video solutions for The Score of Students Solving Math Expression, a hard level problem involving Array, Math, String. This walkthrough by Happy Coding has 1,586 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |