Skip to content

3749. Evaluate Valid Expressions πŸ”’

Description

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.

Solutions

Solution 1: Recursion

Thinking

The expression is a nested \(\mathrm{op}(a,b)\) whose shape is given by parentheses, so recursive descent fits. At the current index we either parse a literal, or read an operator, recurse on the two operands, and apply \(\mathrm{add}/\mathrm{sub}/\mathrm{mul}/\mathrm{div}\).

We define a recursive function \(\text{parse}(i)\) to parse the subexpression starting from index \(i\) and return the computed result along with the next unprocessed index position. The answer is \(\text{parse}(0)[0]\).

The implementation of the function \(\text{parse}(i)\) is as follows:

  1. If the current position \(i\) is a digit or a negative sign -, continue scanning forward until a non-digit character is encountered, parse an integer, and return that integer along with the next unprocessed index position.
  2. Otherwise, the current position \(i\) is the starting position of an operator op. We continue scanning forward until we encounter a left parenthesis (, parsing the operator string op. Then we skip the left parenthesis, recursively call \(\text{parse}\) to parse the first parameter \(a\), skip the comma, recursively call \(\text{parse}\) to parse the second parameter \(b\), and finally skip the right parenthesis ).
  3. Based on the operator op, calculate the result of \(a\) and \(b\), and return that result along with the next unprocessed index position.

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the expression string.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def evaluateExpression(self, expression: str) -> int:
        def parse(i: int) -> (int, int):
            if expression[i].isdigit() or expression[i] == "-":
                j = i
                if expression[j] == "-":
                    j += 1
                while j < len(expression) and expression[j].isdigit():
                    j += 1
                return int(expression[i:j]), j

            j = i
            while expression[j] != "(":
                j += 1
            op = expression[i:j]
            j += 1
            val1, j = parse(j)

            j += 1
            val2, j = parse(j)
            j += 1
            res = 0
            match op:
                case "add":
                    res = val1 + val2
                case "sub":
                    res = val1 - val2
                case "mul":
                    res = val1 * val2
                case "div":
                    res = val1 // val2
            return res, j

        return parse(0)[0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    private String expression;

    public long evaluateExpression(String expression) {
        this.expression = expression;
        return parse(0)[0];
    }

    private long[] parse(int i) {
        if (Character.isDigit(expression.charAt(i)) || expression.charAt(i) == '-') {
            int j = i;
            if (expression.charAt(j) == '-') {
                j++;
            }
            while (j < expression.length() && Character.isDigit(expression.charAt(j))) {
                j++;
            }
            long num = Long.parseLong(expression.substring(i, j));
            return new long[] {num, j};
        }

        int j = i;
        while (expression.charAt(j) != '(') {
            j++;
        }
        String op = expression.substring(i, j);
        j++;

        long[] result1 = parse(j);
        long val1 = result1[0];
        j = (int) result1[1];
        j++;

        long[] result2 = parse(j);
        long val2 = result2[0];
        j = (int) result2[1];
        j++;

        long res = 0;
        switch (op) {
        case "add":
            res = val1 + val2;
            break;
        case "sub":
            res = val1 - val2;
            break;
        case "mul":
            res = val1 * val2;
            break;
        case "div":
            res = val1 / val2;
            break;
        }

        return new long[] {res, j};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    long long evaluateExpression(string expression) {
        auto parse = [&](this auto&& parse, int i) -> pair<long long, int> {
            if (isdigit(expression[i]) || expression[i] == '-') {
                int j = i;
                if (expression[j] == '-') {
                    j++;
                }
                while (j < expression.size() && isdigit(expression[j])) {
                    j++;
                }
                long long num = stoll(expression.substr(i, j - i));
                return {num, j};
            }

            int j = i;
            while (expression[j] != '(') {
                j++;
            }
            string op = expression.substr(i, j - i);
            j++;

            auto [val1, next_j1] = parse(j);
            j = next_j1 + 1;

            auto [val2, next_j2] = parse(j);
            j = next_j2 + 1;

            long long res = 0;
            if (op == "add") {
                res = val1 + val2;
            } else if (op == "sub") {
                res = val1 - val2;
            } else if (op == "mul") {
                res = val1 * val2;
            } else if (op == "div") {
                res = val1 / val2;
            }

            return {res, j};
        };

        return parse(0).first;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func evaluateExpression(expression string) int64 {
    var parse func(int) (int64, int)
    parse = func(i int) (int64, int) {
        if expression[i] >= '0' && expression[i] <= '9' || expression[i] == '-' {
            j := i
            if expression[j] == '-' {
                j++
            }
            for j < len(expression) && expression[j] >= '0' && expression[j] <= '9' {
                j++
            }
            num, _ := strconv.ParseInt(expression[i:j], 10, 64)
            return num, j
        }

        j := i
        for expression[j] != '(' {
            j++
        }
        op := expression[i:j]
        j++

        val1, nextJ1 := parse(j)
        j = nextJ1 + 1

        val2, nextJ2 := parse(j)
        j = nextJ2 + 1

        var res int64
        switch op {
        case "add":
            res = val1 + val2
        case "sub":
            res = val1 - val2
        case "mul":
            res = val1 * val2
        case "div":
            res = val1 / val2
        }

        return res, j
    }

    result, _ := parse(0)
    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function evaluateExpression(expression: string): number {
    function parse(i: number): [number, number] {
        if (/\d/.test(expression[i]) || expression[i] === '-') {
            let j = i;
            if (expression[j] === '-') {
                j++;
            }
            while (j < expression.length && /\d/.test(expression[j])) {
                j++;
            }
            const num = +expression.slice(i, j);
            return [num, j];
        }

        let j = i;
        while (expression[j] !== '(') {
            j++;
        }
        const op = expression.slice(i, j);
        j++;

        const [val1, nextJ1] = parse(j);
        j = nextJ1 + 1;

        const [val2, nextJ2] = parse(j);
        j = nextJ2 + 1;

        let res: number;
        switch (op) {
            case 'add':
                res = val1 + val2;
                break;
            case 'sub':
                res = val1 - val2;
                break;
            case 'mul':
                res = val1 * val2;
                break;
            case 'div':
                res = Math.floor(val1 / val2);
                break;
            default:
                res = 0;
        }

        return [res, j];
    }

    return parse(0)[0];
}

Comments