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".Problem Overview: You receive a string representing mathematical expressions and must evaluate them while respecting operator precedence, parentheses, and validity rules. The goal is to correctly parse the string and compute the final value without relying on built‑in evaluators.
Approach 1: Stack-Based Expression Evaluation (O(n) time, O(n) space)
A direct strategy scans the string from left to right while maintaining a stack of intermediate values. Numbers are parsed digit by digit, and operators determine how the previous value interacts with the current number. Multiplication and division are applied immediately to maintain precedence, while addition and subtraction push signed values onto the stack. Parentheses can trigger recursive or nested stack evaluation. This approach works well for expression parsing because stack operations naturally mirror the order of operations.
Approach 2: Recursive Divide and Conquer (O(n) time, O(n) space)
A more structured solution treats each parenthesized segment as a subproblem. You recursively evaluate the substring inside parentheses, then integrate the result into the surrounding expression. The recursion maintains the current operator and partial result while scanning characters. Each time you encounter a closing parenthesis, the recursive call returns the computed value. The key insight is that expressions form a hierarchical structure, which fits naturally with divide and conquer recursion.
During traversal, maintain the current number and last operator. When you hit an operator or the end of the string, apply the previous operator to the current number and update a stack or running total. This combines recursion with classic parsing logic and guarantees each character is processed once.
Approach 3: Recursive Parsing with Hash Memoization (O(n) time average, O(n) space)
If expressions contain repeated substrings or nested structures evaluated multiple times, memoization can cache results of previously solved segments. A hash table maps substring ranges to computed values. When recursion revisits the same segment, the cached value is returned instantly. This avoids repeated work in complex nested expressions and keeps evaluation close to linear time.
Recommended for interviews: The recursive parsing approach is typically expected. It shows that you understand expression trees, operator precedence, and recursive evaluation. Starting with a simple stack-based parser demonstrates fundamentals, while the recursive divide-and-conquer solution highlights stronger algorithmic thinking and cleaner handling of nested parentheses.
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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Expression Evaluation | O(n) | O(n) | General expression parsing with operator precedence |
| Recursive Divide and Conquer | O(n) | O(n) | Expressions containing nested parentheses |
| Recursive Parsing with Memoization | O(n) average | O(n) | When repeated subexpressions appear in large inputs |
Practice Evaluate Valid Expressions with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor