Evaluate Valid Expressions solution and explanation
The problem
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:
opis one of"add","sub","mul", or"div".aandbare 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 / 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 <= 105expressionis 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.
Approach overview
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.
Solution
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:
- If the current position
iis 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
iis the starting position of an operatorop. We continue scanning forward until we encounter a left parenthesis(, parsing the operator stringop. Then we skip the left parenthesis, recursively callparseto parse the first parametera, skip the comma, recursively callparseto parse the second parameterb, and finally skip the right parenthesis). - Based on the operator
op, calculate the result ofaandb, 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:
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]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;
}
};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];
}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
}Complexity analysis
| 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 |
Frequently asked questions
Is Evaluate Valid Expressions easy or hard?
Evaluate Valid Expressions is considered a hard problem because it combines string parsing, operator precedence handling, recursion, and stack-based evaluation. Correctly managing nested parentheses and intermediate calculations requires careful implementation and edge-case handling.
Evaluate Valid Expressions Python/Java solution
Python, Java, C++, Go, and TypeScript implementations typically use recursion combined with stack-based operator handling. The algorithm parses digits to build numbers, tracks the previous operator, and evaluates parentheses using recursive calls. Each implementation maintains O(n) time complexity.
How to solve Evaluate Valid Expressions in O(n)?
Scan the string once while maintaining the current number, operator, and a stack of partial results. When encountering parentheses, recursively evaluate the substring inside them. Apply multiplication and division immediately while pushing addition and subtraction values to the stack. This ensures each character is processed once, achieving O(n) time.
What is the best approach for Evaluate Valid Expressions?
The recursive divide-and-conquer approach is usually the best solution. It evaluates nested expressions by recursively processing parentheses while maintaining operator precedence with a stack or running accumulator. Each character is processed once, giving O(n) time complexity and O(n) space due to recursion and intermediate storage.
Is Evaluate Valid Expressions asked at Google/Amazon/Meta?
Expression parsing problems frequently appear in interviews at large tech companies including Google, Amazon, and Meta. Variations such as Basic Calculator, Evaluate Reverse Polish Notation, and expression tree evaluation test similar skills involving stacks, recursion, and string parsing.
What data structure is used in Evaluate Valid Expressions?
The most common data structure is a stack, which stores intermediate values while processing operators and maintaining precedence. Recursive solutions also use the call stack to evaluate nested parentheses. Some implementations use hash tables for memoization when caching repeated subexpressions.
What is the time complexity of Evaluate Valid Expressions?
The optimal solution runs in O(n) time where n is the length of the expression string. Each character is parsed once while numbers and operators are processed using constant-time stack or recursion operations. Space complexity is O(n) because of recursion depth and temporary storage for intermediate values.