LeetCode 3749 - Evaluate Valid Expressions

Difficulty: 🔴 Hard
Topics: Hash Table, Math, String, Divide and Conquer, Stack

Solution

Problem Understanding

The problem presents a simplified version of evaluating nested mathematical expressions in string format. The input expression is either a single integer literal, which may be negative, or a nested operation of the form op(a,b) where op is one of the four basic arithmetic operations: add, sub, mul, or div. The operands a and b themselves can be either integers or further nested operations.

The task is to compute and return the integer result of this expression. Importantly, all divisions are guaranteed to produce integer results, and the expressions are always valid according to the problem constraints. This removes the need to handle errors like division by zero or malformed expressions.

Key considerations include handling deeply nested expressions, parsing integers and operators correctly, and maintaining the correct evaluation order without using eval for security and performance reasons. Edge cases include single negative numbers, expressions with maximum nesting depth, and expressions that produce negative results.

Approaches

A brute-force approach would involve scanning the string recursively or iteratively and splitting it at each comma after identifying the operation. While this works conceptually, naive string splitting and parsing of nested expressions can lead to significant overhead, especially for very deep expressions, making it inefficient for the maximum input size of 10^5.

The optimal approach leverages recursion or a stack to evaluate expressions using a divide-and-conquer strategy. By identifying the operator and correctly parsing the two operands, we can recursively evaluate each sub-expression. This avoids unnecessary string splitting and handles arbitrary nesting efficiently. Essentially, the recursion naturally mirrors the structure of the expression tree defined by the input string.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated string slicing and scanning for commas can be quadratic in the worst case
Optimal (Recursive/Divide-and-Conquer)	O(n)	O(n)	Parse once, recursively evaluate sub-expressions, linear scan of string

Algorithm Walkthrough

Check if the expression is a literal: If the first character is - or a digit, the expression is a literal integer. Convert it directly to an integer and return. This handles base cases like "-42".
Parse the operator: Scan from the beginning of the string until you reach '('. The substring before '(' is the operator (add, sub, mul, div).
Extract the operands: The operands are contained within the parentheses. Because operands may be nested expressions themselves, simply splitting by , is insufficient. Use a counter to track parentheses depth. Start from the character after '(', increment the counter for each '(' and decrement for each ')'. The comma that occurs when the counter is 0 separates the two top-level operands.
Recursively evaluate operands: Once the operands a and b are identified as substrings, recursively call the evaluation function on each.
Compute the result: Apply the operator to the results of the two recursive evaluations and return the result.

Why it works: This algorithm mimics the natural evaluation of an expression tree. Each recursive call evaluates a sub-tree of the expression. The invariant is that at any call, the expression substring corresponds to a valid expression; evaluating it recursively ensures correctness.

Python Solution

class Solution:
    def evaluateExpression(self, expression: str) -> int:
        if expression[0] == '-' or expression[0].isdigit():
            return int(expression)
        
        # Find operator
        op_end = expression.index('(')
        operator = expression[:op_end]
        inner = expression[op_end + 1:-1]  # remove outer parentheses
        
        # Split operands considering nested expressions
        count = 0
        for i, char in enumerate(inner):
            if char == '(':
                count += 1
            elif char == ')':
                count -= 1
            elif char == ',' and count == 0:
                left = inner[:i]
                right = inner[i + 1:]
                break
        
        left_val = self.evaluateExpression(left)
        right_val = self.evaluateExpression(right)
        
        if operator == 'add':
            return left_val + right_val
        elif operator == 'sub':
            return left_val - right_val
        elif operator == 'mul':
            return left_val * right_val
        elif operator == 'div':
            return left_val // right_val
        else:
            raise ValueError(f"Unknown operator: {operator}")

Explanation: The code first checks for integer literals. If not, it identifies the operator and recursively evaluates the two operands. The parentheses counter ensures that nested expressions are not incorrectly split at internal commas. Finally, it applies the operator to the evaluated results.

Go Solution

import (
    "strconv"
    "strings"
)

func evaluateExpression(expression string) int64 {
    if expression[0] == '-' || (expression[0] >= '0' && expression[0] <= '9') {
        val, _ := strconv.ParseInt(expression, 10, 64)
        return val
    }
    
    opEnd := strings.Index(expression, "(")
    operator := expression[:opEnd]
    inner := expression[opEnd+1 : len(expression)-1]
    
    count := 0
    split := 0
    for i, c := range inner {
        if c == '(' {
            count++
        } else if c == ')' {
            count--
        } else if c == ',' && count == 0 {
            split = i
            break
        }
    }
    
    left := inner[:split]
    right := inner[split+1:]
    
    leftVal := evaluateExpression(left)
    rightVal := evaluateExpression(right)
    
    switch operator {
    case "add":
        return leftVal + rightVal
    case "sub":
        return leftVal - rightVal
    case "mul":
        return leftVal * rightVal
    case "div":
        return leftVal / rightVal
    default:
        panic("Unknown operator: " + operator)
    }
}

Explanation: The Go version mirrors Python, with type conversions for int64. The parentheses counter and split logic ensure proper parsing of nested expressions. Error handling uses panic for unknown operators.

Worked Examples

Example 1: "add(2,3)"

Expression is not a literal.
Operator is "add".
Inner expression "2,3", split at comma → left: "2", right: "3".
Recursively evaluate "2" → 2, "3" → 3.
Apply add → 2 + 3 = 5.

Example 2: "-42"

Expression starts with '-' → literal.
Convert to int → -42.

Example 3: "div(mul(4,sub(9,5)),add(1,1))"

Operator: "div".
Inner expression "mul(4,sub(9,5)),add(1,1)".
Split at comma outside parentheses → "mul(4,sub(9,5))" and "add(1,1)".
Recursively evaluate left:

Operator "mul", operands "4" and "sub(9,5)".
"4" → 4
"sub(9,5)" → 9 - 5 = 4
Multiply: 4 * 4 = 16

Recursively evaluate right:

"add(1,1)" → 1 + 1 = 2

Apply div: 16 / 2 = 8

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character in the expression is scanned once for parsing and splitting, recursion evaluates sub-expressions linearly.
Space	O(n)	Recursion stack can be as deep as the nesting level; in the worst case, nesting is O(n).

The linear time complexity is justified because each character contributes to one recursive call at most. Space complexity is proportional to recursion depth.

Test Cases

# Provided examples
assert Solution().evaluateExpression("add(2,3)") == 5  # simple addition
assert Solution().evaluateExpression("-42") == -42    # single negative literal
assert Solution().evaluateExpression("div(mul(4,sub(9,5)),add(1,1))") == 8  # nested expressions

# Edge cases
assert Solution().evaluateExpression("add(-1,-2)") == -3  # negative operands
assert Solution().evaluateExpression("mul(0,add(5,5))") == 0  # multiplication by zero
assert Solution().evaluateExpression("div(10,2)") == 5  # simple division
assert Solution().evaluateExpression("sub(0,sub(0,5))") == 5  # nested negative result

# Large numbers
assert Solution().evaluateExpression("mul(100000,100000)") == 10000000000

Test	Why
`"add(2,3)"`	Simple operation validation
`"-42"`	Single integer literal handling
`"div(mul(4,sub(9,5)),add(1,1))"`	Nested expression evaluation
`"add(-1,-2)"`	Negative numbers