LeetCode Hard Problem ||

Although this problem is labeled as Hard, it is actually easier than it looks. A simple parser with tail-recursion. The only caveat is that I was doing a lot of string manipulation which led to too much memory being used. The solution was to avoid that by passing the indexes of the current processing string as parameters to the functions. That way there won't be any string manipulation, and the code works. Code is down below, cheers, ACC.

Evaluate Valid Expressions - LeetCode

You are given a string expression that represents a nested mathematical expression in a simplified form.

A valid expression is either an integer literal or follows the format op(a,b), where:

• op is one of "add", "sub", "mul", or "div".
• a and b are each valid expressions.

The operations are defined as follows:

• add(a,b) = a + b
• sub(a,b) = a - b
• mul(a,b) = a * b
• div(a,b) = a / b

Return an integer representing the result after fully evaluating the expression.

 

Example 1:

Input: expression = "add(2,3)"

Output: 5

Explanation:

The operation add(2,3) means 2 + 3 = 5.

Example 2:

Input: expression = "-42"

Output: -42

Explanation:

The expression is a single integer literal, so the result is -42.

Example 3:

Input: expression = "div(mul(4,sub(9,5)),add(1,1))"

Output: 8

Explanation:

• First, evaluate the inner expression: sub(9,5) = 9 - 5 = 4
• Next, multiply the results: mul(4,4) = 4 * 4 = 16
• Then, compute the addition on the right: add(1,1) = 1 + 1 = 2
• Finally, divide the two main results: div(16,2) = 16 / 2 = 8

Therefore, the entire expression evaluates to 8.

 

Constraints:

• 1 <= expression.length <= 105
• expression is valid and consists of digits, commas, parentheses, the minus sign '-', and the lowercase strings "add", "sub", "mul", "div".
• All intermediate results fit within the range of a long integer.
• All divisions result in integer values.

public long EvaluateExpression(string expression)
{
    return EvaluateExpression(expression, 0, expression.Length - 1);
}

public long EvaluateExpression(string expression,
                                int initIndex,
                                int endIndex)
{
    long val = 0;
    if (IsValidNumber(expression, initIndex, endIndex, out val)) return val;

    int indexDelimiter = FindExpressionDelimiterIndex(expression, initIndex + 4, endIndex - 1);
    switch (expression[initIndex])
    {
        case 'a':
            return EvaluateExpression(expression, initIndex + 4, indexDelimiter - 1) + EvaluateExpression(expression, indexDelimiter + 1, endIndex - 1);
        case 's':
            return EvaluateExpression(expression, initIndex + 4, indexDelimiter - 1) - EvaluateExpression(expression, indexDelimiter + 1, endIndex - 1);
        case 'm':
            return EvaluateExpression(expression, initIndex + 4, indexDelimiter - 1) * EvaluateExpression(expression, indexDelimiter + 1, endIndex - 1);
        case 'd':
            return EvaluateExpression(expression, initIndex + 4, indexDelimiter - 1) / EvaluateExpression(expression, indexDelimiter + 1, endIndex - 1);
    }

    return 0;
}

private bool IsValidNumber(string exp, 
                            int initIndex,
                            int endIndex,
                            out long val)
{
    val = 0;
    int signal = 1;

    for (int i = initIndex; i <= endIndex; i++)
    {
        if (i == initIndex && exp[i] == '-')
        {
            signal = -1;
        }
        else if (exp[i] >= '0' && exp[i] <= '9')
        {
            val = 10 * val + (int)(exp[i] - '0');
        }
        else return false;
    }

    val *= signal;
    return true;
}

private int FindExpressionDelimiterIndex(string expression, 
                                            int initIndex, 
                                            int endIndex)
{
    int countBrackets = 0;
    for (int i = initIndex; i <= endIndex; i++)
    {
        if (expression[i] == '(') countBrackets++;
        else if (expression[i] == ')') countBrackets--;

        if (expression[i] == ',' && countBrackets == 0) return i;
    }
    return -1;
}