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 <= 10⁵
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

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:

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.
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 ).
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.

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};
    }
}

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;
    }
};

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]

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
}

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];
}

3749 - Evaluate Valid Expressions

3749. Evaluate Valid Expressions 🔒

Description

Solutions

Solution 1: Recursion

All Problems

All Solutions

Welcome to Subscribe On Youtube

3749. Evaluate Valid Expressions 🔒

Description

Solutions

Solution 1: Recursion

All Problems

All Solutions