Skip to main content
Talentd

Evaluate Valid Expressions - Solution & Explanation

HardPremiumFree on FleetCodeHash TableMathStringDivide and Conquer11 min read
Practice this problem

Problem Statement

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.

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:

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack-Based Expression EvaluationO(n)O(n)General expression parsing with operator precedence
Recursive Divide and ConquerO(n)O(n)Expressions containing nested parentheses
Recursive Parsing with MemoizationO(n) averageO(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.

Ready to solve this problem?

Practice Evaluate Valid Expressions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Basic Calculator II