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 + bsub(a,b) = a - bmul(a,b) = a * bdiv(a,b) = a / bReturn 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:
sub(9,5) = 9 - 5 = 4mul(4,4) = 4 * 4 = 16add(1,1) = 1 + 1 = 2div(16,2) = 16 / 2 = 8Therefore, the entire expression evaluates to 8.
Constraints:
1 <= expression.length <= 105expression is valid and consists of digits, commas, parentheses, the minus sign '-', and the lowercase strings "add", "sub", "mul", "div".We define a recursive function 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 parse(0)[0].
The implementation of the function parse(i) is as follows:
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.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 parse to parse the first parameter a, skip the comma, recursively call parse to parse the second parameter b, and finally skip the right parenthesis ).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.
Java
C++
Go
TypeScript
Practice Evaluate Valid Expressions with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor