The Score of Students Solving Math Expression solution and explanation
3 more videos on this problem
LeetCode 2019. The Score of Students Solving Math ExpressionHappy Coding · 18:09 · 1K views
【每日一题】LeetCode 2019. The Score of Students Solving Math Expression 10/1/2021Huifeng Guan · 20:25 · 665 views
2019. The Score of Students Solving Math Expression (Leetcode Hard)Programming Live with Larry · 45:53 · 381 views
LeetCode Hard 2019 The Score of Students Solving Math Expressionrobzingcod · 1:06:34 · 49 views
The problem
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:
- Compute multiplication, reading from left to right; Then,
- 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
5points; - 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
2points; - Otherwise, this student will be rewarded
0points.
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 <= 31srepresents a valid expression that contains only digits0-9,'+', and'*'only.- All the integer operands in the expression are in the inclusive range
[0, 9]. 1 <=The count of all operators ('+'and'*') in the math expression<= 15- Test data are generated such that the correct answer of the expression is in the range of
[0, 1000]. n == answers.length1 <= n <= 1040 <= answers[i] <= 1000
Approach overview
Problem 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 1: Evaluate with Left-to-Right Multiplication First
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.
def evaluate_expression(s: str) -> int:
result, multiply = 0, 1
num = 0
operator = '+'
for char in s:
if char.isdigit():
num = int(char)
if operator == '*':
multiply *= num
else:
result += multiply
multiply = num
if char in '+*':
operator = char
return result + multiply
s = '7+3*1*2'
answers = [20, 13, 42]
correct = evaluate_expression(s)
points = sum(5 if ans == correct else 0 for ans in answers)
print(f'Total Points: {points}')import java.util.*;
public class EvaluateExpression {
public static int evaluate(String s) {
int result = 0, multiply = 1, num = 0;
char op = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = c - '0';
if (op == '*') {
multiply *= num;
} else {
result += multiply;
multiply = num;
}
}
if (c == '+' || c == '*' || i == s.length() - 1) {
if (c == '+' || i == s.length() - 1) {
result += multiply;
multiply = 1;
}
op = c;
}
}
return result;
}
public static void main(String[] args) {
String s = "7+3*1*2";
int[] answers = {20, 13, 42};
int correct = evaluate(s);
int points = 0;
for (int ans : answers) {
if (ans == correct) points += 5;
}
System.out.println("Total Points: " + points);
}
}#include <iostream>
#include <string>
using namespace std;
int evaluate(string s) {
int n = s.length();
int result = 0, num = 0, multiply = 1;
char op = '+';
for (int i = 0; i < n; i++) {
if (isdigit(s[i])) {
num = s[i] - '0';
if (op == '*') {
multiply *= num;
} else {
result += multiply;
multiply = num;
}
}
if (s[i] == '+' || s[i] == '*' || i == n-1) {
if (s[i] == '+' || i == n-1) {
result += multiply;
multiply = 1;
}
op = s[i];
}
}
return result;
}
int main() {
string s = "7+3*1*2";
int answers[] = {20, 13, 42};
int correct = evaluate(s);
cout << "Correct Answer: " << correct << endl;
int points = 0;
for (int ans : answers) {
if (ans == correct) points += 5;
}
cout << "Total Points: " << points << endl;
}function evaluate(s) {
let result = 0, multiply = 1, num = 0, op = '+';
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (!isNaN(char)) {
num = parseInt(char);
if (op === '*') {
multiply *= num;
} else {
result += multiply;
multiply = num;
}
}
if (char === '+' || char === '*' || i === s.length - 1) {
if (char === '+' || i === s.length - 1) {
result += multiply;
multiply = 1;
}
op = char;
}
}
return result;
}
let s = "7+3*1*2";
let answers = [20, 13, 42];
let correct = evaluate(s);
let points = answers.reduce((total, ans) => total + (ans === correct ? 5 : 0), 0);
console.log(`Total Points: ${points}`);#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int evaluateExpression(const char* s) {
int i, num = 0, result = 0, multiply = 1;
char operator = '+', lastOperator = '+';
for (i = 0; s[i]; i++) {
char current = s[i];
if (current >= '0' && current <= '9') {
num = current - '0';
switch (lastOperator) {
case '*':
multiply *= num;
break;
case '+':
multiply = num;
break;
}
}
if (current == '+' || current == '*' || s[i + 1] == '\0') {
if (operator == '+') {
result += multiply;
}
operator = current;
lastOperator = current;
}
}
return result;
}
int main() {
char* s = "7+3*1*2";
int answers[] = {20, 13, 42};
int size = sizeof(answers) / sizeof(answers[0]);
int correct = evaluateExpression(s);
printf("Correct answer: %d\n", correct);
int points = 0;
for (int i = 0; i < size; i++) {
if (answers[i] == correct) {
points += 5;
}
}
printf("Total Points: %d\n", points);
return 0;
}using System;
class Program {
public static int Evaluate(string s) {
int result = 0, num = 0, multiply = 1;
char op = '+';
for (int i = 0; i < s.Length; i++) {
char c = s[i];
if (Char.IsDigit(c)) {
num = c - '0';
if (op == '*') multiply *= num;
else {
result += multiply;
multiply = num;
}
}
if (c == '+' || c == '*' || i == s.Length - 1) {
if (c == '+' || i == s.Length - 1) {
result += multiply;
multiply = 1;
}
op = c;
}
}
return result;
}
static void Main() {
string s = "7+3*1*2";
int[] answers = {20, 13, 42};
int correct = Evaluate(s);
int points = 0;
foreach (int answer in answers) {
if (answer == correct) points += 5;
}
Console.WriteLine("Total Points: " + points);
}
}A Python approach that respects the given order of operations evaluates the expression step by step. It first solves multiplication from left to right and then addition. This results in a function that can easily compute the correct answer.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since only a fixed number of variables are employed.
Approach 2: Evaluate with Brackets (Alternate Total Order)
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.
def evaluate_expression_alt(s: str) -> int:
result, num = 0, 0
operator = '+'
for char in s:
if char.isdigit():
num = int(char)
if operator == '+':
result += num
elif operator == '*':
result *= num
if char in '+*':
operator = char
return result
s = '7+3*1*2'
correct_alt = evaluate_expression_alt(s)
print(f'Alternate Correct: {correct_alt}')public class EvaluateExpressionAlt {
public static int evaluateAlt(String s) {
int result = 0, num = 0;
char op = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = c - '0';
if (op == '+') result += num;
else if (op == '*') result *= num;
}
if (c == '+' || c == '*') op = c;
}
return result;
}
public static void main(String[] args) {
String s = "7+3*1*2";
int correct = evaluateAlt(s);
System.out.println("Alternate Correct: " + correct);
}
}#include <iostream>
#include <string>
using namespace std;
int evaluateAlt(string s) {
int n = s.length(), result = 0, num = 0;
char op = '+';
for (int i = 0; i < n; i++) {
if (isdigit(s[i])) {
num = s[i] - '0';
if (op == '+') result += num;
else if (op == '*') result *= num;
}
if (s[i] == '+' || s[i] == '*') op = s[i];
}
return result;
}
int main() {
string s = "7+3*1*2";
int correct = evaluateAlt(s);
cout << "Alternate correct: " << correct << endl;
}function evaluateAlt(s) {
let result = 0, num = 0, op = '+';
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (!isNaN(char)) {
num = parseInt(char);
if (op === '+') result += num;
else if (op === '*') result *= num;
}
if (char === '+' || char === '*') op = char;
}
return result;
}
let s = "7+3*1*2";
let correctAlt = evaluateAlt(s);
console.log(`Alternate Correct: ${correctAlt}`);#include <stdio.h>
#include <string.h>
int evaluateAlt(const char* s) {
int i, num = 0, result = 0;
char operator = '+';
for (i = 0; s[i]; i++) {
char current = s[i];
if (current >= '0' && current <= '9') {
num = current - '0';
if (operator == '+') {
result += num;
} else if (operator == '*') {
result *= num;
}
}
if (current == '+' || current == '*') {
operator = current;
}
}
return result;
}
int main() {
char* s = "7+3*1*2";
int correct = evaluateAlt(s);
printf("Alternate correct: %d\n", correct);
return 0;
}using System;
class Program {
public static int EvaluateAlt(string s) {
int result = 0, num = 0;
char op = '+';
for (int i = 0; i < s.Length; i++) {
char c = s[i];
if (Char.IsDigit(c)) {
num = c - '0';
if (op == '+') result += num;
else if (op == '*') result *= num;
}
if (c == '+' || c == '*') op = c;
}
return result;
}
static void Main() {
string s = "7+3*1*2";
int correctAlt = EvaluateAlt(s);
Console.WriteLine("Alternate Correct: " + correctAlt);
}
}In Python, this implementation reads the expression and processes symbols strictly in order, allowing no element of priority between operators, thereby simulating potential student miscues.
Time Complexity: O(n), each character is visited once.
Space Complexity: O(1), limited storage required.
Approach 3: Dynamic Programming (Interval DP)
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$.
function scoreOfStudents(s: string, answers: number[]): number {
const n = s.length;
const cal = (s: string): number => {
let res = 0;
let pre = s.charCodeAt(0) - '0'.charCodeAt(0);
for (let i = 1; i < s.length; i += 2) {
const cur = s.charCodeAt(i + 1) - '0'.charCodeAt(0);
if (s[i] === '+') {
res += pre;
pre = cur;
} else {
pre *= cur;
}
}
res += pre;
return res;
};
const x = cal(s);
const m = (n + 1) >> 1;
const f: Set<number>[][] = Array(m)
.fill(0)
.map(() =>
Array(m)
.fill(0)
.map(() => new Set()),
);
for (let i = 0; i < m; ++i) {
f[i][i].add(s[i << 1].charCodeAt(0) - '0'.charCodeAt(0));
}
for (let i = m - 1; i >= 0; --i) {
for (let j = i; j < m; ++j) {
for (let k = i; k < j; ++k) {
for (const l of f[i][k]) {
for (const r of f[k + 1][j]) {
const op = s[(k << 1) + 1];
if (op === '+' && l + r <= 1000) {
f[i][j].add(l + r);
} else if (op === '*' && l * r <= 1000) {
f[i][j].add(l * r);
}
}
}
}
}
}
const cnt: number[] = Array(1001).fill(0);
for (const v of answers) {
++cnt[v];
}
let ans = cnt[x] * 5;
for (let i = 0; i <= 1000; ++i) {
if (i !== x && f[0][m - 1].has(i)) {
ans += cnt[i] << 1;
}
}
return ans;
}func scoreOfStudents(s string, answers []int) int {
n := len(s)
x := cal(s)
m := (n + 1) >> 1
f := make([][]map[int]bool, m)
for i := range f {
f[i] = make([]map[int]bool, m)
for j := range f[i] {
f[i][j] = make(map[int]bool)
}
f[i][i][int(s[i<<1]-'0')] = true
}
for i := m - 1; i >= 0; i-- {
for j := i; j < m; j++ {
for k := i; k < j; k++ {
for l := range f[i][k] {
for r := range f[k+1][j] {
op := s[k<<1|1]
if op == '+' && l+r <= 1000 {
f[i][j][l+r] = true
} else if op == '*' && l*r <= 1000 {
f[i][j][l*r] = true
}
}
}
}
}
}
cnt := [1001]int{}
for _, v := range answers {
cnt[v]++
}
ans := cnt[x] * 5
for k, v := range cnt {
if k != x && f[0][m-1][k] {
ans += v << 1
}
}
return ans
}
func cal(s string) int {
res, pre := 0, int(s[0]-'0')
for i := 1; i < len(s); i += 2 {
cur := int(s[i+1] - '0')
if s[i] == '+' {
res += pre
pre = cur
} else {
pre *= cur
}
}
res += pre
return res
}Complexity comparison
| Approach | Complexity |
|---|---|
| Evaluate with Left-to-Right Multiplication First | Time Complexity: O(n), where n is the length of the string. |
| Evaluate with Brackets (Alternate Total Order) | Time Complexity: O(n), each character is visited once. |
| Dynamic Programming (Interval DP) | – |
Complexity analysis
| 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 |
Frequently asked questions
Is The Score of Students Solving Math Expression easy or hard?
The problem is classified as Hard because it combines expression parsing with interval dynamic programming. Implementing the DP that enumerates all possible parenthesizations and managing result sets correctly requires careful reasoning.
The Score of Students Solving Math Expression Python/Java solution
Python and Java implementations usually compute the correct result with a stack, then use recursive memoization or bottom-up DP to generate all possible results for each substring. Each interval stores a set of possible values capped at 1000 to limit state growth.
How to solve The Score of Students Solving Math Expression in O(n)?
Only the correct expression evaluation can be done in O(n) time using a stack that applies multiplication immediately and sums additions later. However, scoring student answers requires enumerating all possible incorrect evaluation orders, which requires O(n^3) dynamic programming in the worst case.
What is the best approach for The Score of Students Solving Math Expression?
The best approach combines two steps: compute the correct result using a stack-based expression evaluation, then generate all possible incorrect results using interval dynamic programming. The DP enumerates every valid parenthesization of the expression. This solution runs in O(n^3) time and O(n^2) space.
Is The Score of Students Solving Math Expression asked at Google/Amazon/Meta?
Expression evaluation and interval dynamic programming problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of operator precedence, recursion with memoization, and parsing expressions.
What data structure is used in The Score of Students Solving Math Expression?
The solution typically uses a stack for evaluating the correct expression and a dynamic programming table or memoization map for storing results of expression intervals. Sets are also used to track all possible computed values for each subexpression.
What is the time complexity of The Score of Students Solving Math Expression?
Computing the correct expression value takes O(n) time using a stack. Generating all possible alternative evaluation results using interval dynamic programming takes O(n^3) time and O(n^2) space because every substring and operator split must be evaluated.