Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = "1 + 1" Output: 2
Example 2:
Input: s = " 2-1 + 2 " Output: 3
Example 3:
Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23
Constraints:
1 <= s.length <= 3 * 105s consists of digits, '+', '-', '(', ')', and ' '.s represents a valid expression.'+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).Problem Overview: You are given a string representing a mathematical expression containing digits, +, -, parentheses, and spaces. The task is to evaluate the expression and return the final integer result. The tricky part is correctly handling nested parentheses and maintaining the correct sign for each number.
Approach 1: Iterative Parsing with Stack (O(n) time, O(n) space)
This approach scans the string from left to right while maintaining the current result, current number being built, and the active sign. When you encounter a digit, build the number by multiplying the previous value by 10 and adding the new digit. When encountering + or -, add the previous number multiplied by its sign to the running result.
Parentheses introduce a new evaluation context. Push the current result and sign onto a stack when you see (. Reset the result and sign to start evaluating the sub-expression. When ) appears, finalize the current sub-expression, then pop the sign and previous result from the stack and combine them. This stack effectively stores suspended calculations while nested expressions are evaluated. The algorithm processes each character once, giving O(n) time complexity and O(n) space due to the stack. This technique relies heavily on stack operations while parsing the string.
Approach 2: Recursive Expression Evaluation (O(n) time, O(n) space)
Recursive parsing treats each pair of parentheses as a subproblem. As you iterate through the characters, build numbers and apply signs exactly like the iterative method. When you encounter (, recursively evaluate the substring representing the inner expression. The recursive call returns the computed value and the index where the sub-expression ended.
Each recursion level handles its own partial result and sign state. When the recursion returns, the result is treated as a number in the outer expression. This mirrors how mathematical expressions are naturally evaluated: solve the innermost parentheses first and propagate results upward. The recursion stack replaces the explicit stack used in the iterative approach. Time complexity remains O(n) since each character is processed once, and space complexity is O(n) due to recursion depth for nested parentheses. This approach highlights the recursive structure of expression evaluation and fits well with problems involving recursion and expression trees.
Recommended for interviews: The iterative stack solution is usually what interviewers expect. It demonstrates strong control over parsing logic, sign handling, and stack-based state management. Explaining the recursive version shows deeper understanding of expression evaluation, but implementing the stack-based parser quickly and correctly tends to perform better in a timed interview.
This approach uses a stack to handle the parentheses. We iterate over the string, using a stack to track the signs. We also build numbers on-the-fly to consider multi-digit numbers. Each time we encounter a closing parenthesis, we compute the resolved values until we reach an opening parenthesis.
In this solution, we use a stack to store results and signs before entering a set of parentheses. As we iterate over the expression, we update the result according to the sign, and when we encounter a closing parenthesis, we pop from the stack and multiply with the sign to maintain order.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string, as we iterate over it once.
Space Complexity: O(n) for the stack used to store intermediate results.
In this approach, we define a recursive function that processes the expression by evaluating parts of the expression until the end of the string or a closing parenthesis is encountered. The recursion allows "diving into" parentheses with adjusted state that mirrors stack behavior.
This C solution employs a recursive strategy to compute bracketed sub-expressions by evaluating subsequent numbers and operators in a controlled, isolated scope. Each recursive call takes over when an open bracket is encountered, emulating stack behavior implicitly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of string as operations are done in a linear pass.
Space Complexity: O(n) due to recursive call stack overhead.
| Approach | Complexity |
|---|---|
| Iterative with Stack | Time Complexity: O(n), where n is the length of the string, as we iterate over it once. |
| Recursive | Time Complexity: O(n), where n is the length of string as operations are done in a linear pass. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Parsing with Stack | O(n) | O(n) | Best general solution for parsing expressions with nested parentheses and sign context |
| Recursive Expression Evaluation | O(n) | O(n) | Useful when modeling expressions as recursive subproblems or implementing recursive parsers |
BASIC CALCULATOR II | LEETCODE 227 | PYTHON SOLUTION • Cracking FAANG • 34,883 views views
Watch 9 more video solutions →Practice Basic Calculator with our built-in code editor and test cases.
Practice on FleetCode