We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

The Score of Students Solving Math Expression

Difficulty: Hard

Problem Description

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+52). 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:

  1. Compute multiplication, reading from left to right; Then,
  2. 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 5 points;
  • 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 2 points;
  • Otherwise, this student will be rewarded 0 points.

Return the sum of the points of the students.

Key Insights

  • The problem requires evaluating a mathematical expression based on specific order of operations.
  • Two different evaluations need to be conducted: one following the correct order (multiplication before addition) and another assuming incorrect order (addition before multiplication).
  • The final score for each student depends on whether their answer matches the correct evaluation or the incorrect evaluation.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of the string representing the expression and m is the number of student answers. Space Complexity: O(1), as we are using a constant amount of space for variables regardless of input size.

Solution

To solve the problem, we can use the following approach:

  1. Parse the string expression to evaluate the correct answer by respecting the order of operations (multiplication first, then addition).
  2. Compute the incorrect answer by evaluating the expression as if addition is done first.
  3. Compare each student's answer to both the correct and incorrect answers, assigning points accordingly.
  4. Sum the points for all students and return the total.

The key data structures used are simple variables to store the results of the evaluations and a loop to iterate through the students' answers.

Code Solutions

def scoreOfStudents(s, answers):
    # Function to evaluate the expression considering multiplication first.
    def evaluate_correct(order):
        stack = []
        current_number = 0
        current_operation = '+'
        
        for char in order:
            if char.isdigit():
                current_number = int(char)
            if char in '+*':
                if current_operation == '*':
                    stack[-1] *= current_number
                else:
                    stack.append(current_number)
                current_number = 0
                current_operation = char
        
        if current_operation == '*':
            stack[-1] *= current_number
        else:
            stack.append(current_number)
        
        return sum(stack)
    
    # Evaluate the correct answer
    correct_answer = evaluate_correct(s)
    
    # Calculate incorrect answer by evaluating as if addition happens first
    def evaluate_incorrect(order):
        parts = order.split('+')
        total = 0
        for part in parts:
            product = 1
            for num in part.split('*'):
                product *= int(num)
            total += product
        return total
    
    incorrect_answer = evaluate_incorrect(s)
    
    # Calculate the total score based on student answers
    total_score = 0
    for answer in answers:
        if answer == correct_answer:
            total_score += 5
        elif answer == incorrect_answer:
            total_score += 2
        else:
            total_score += 0
    
    return total_score
← Back to All Questions