Basic Calculator - Solution & Explanation
Problem Statement
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 * 105sconsists of digits,'+','-','(',')', and' '.srepresents 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).- There will be no two consecutive operators in the input.
- Every number and running calculation will fit in a signed 32-bit integer.
Approach Overview
Problem Overview: Evaluate a string expression containing integers, +, -, parentheses, and spaces. You must correctly handle nested parentheses and operator precedence while scanning the string.
Approach 1: Iterative Stack Evaluation (O(n) time, O(n) space)
This approach scans the expression from left to right while maintaining the current number, current sign, and a running result. When encountering digits, you build the number. When encountering + or -, you finalize the previous number by applying the stored sign. Parentheses introduce a new evaluation scope, so you push the current result and sign onto a stack. When a closing parenthesis appears, compute the inner expression and combine it with the previous state popped from the stack. Each character is processed once, giving O(n) time complexity and O(n) auxiliary space for nested parentheses.
Approach 2: Recursive Expression Parsing (O(n) time, O(n) space)
The recursive method treats each parenthesized expression as a subproblem. While iterating through the string, digits build numbers and signs update the running result. When an opening parenthesis appears, recursively evaluate the substring until the matching closing parenthesis. The returned value becomes the current number in the outer expression. This mirrors how compilers parse arithmetic expressions and is a natural fit for problems involving nested structures in a string. The recursion stack may grow up to the depth of parentheses, so space complexity is O(n) in the worst case.
Recommended for interviews: The iterative stack solution is usually expected because it demonstrates strong control over expression parsing and stack-based state management. Interviewers often look for the insight that each parenthesis creates a new evaluation frame that can be saved and restored with a stack. The recursive approach is equally valid and sometimes easier to reason about, especially if you already think of the expression as nested subproblems. Both rely on concepts from math, stack, and recursion, and both achieve optimal O(n) time complexity since every character in the expression is processed exactly once.
Approach 1: Iterative with Stack
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.
Complexity
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.
Approach 2: Recursive
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.
Complexity
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 3: Stack
We use a stack stk to save the current calculation result and operator, a variable sign to save the current sign, and a variable ans to save the final calculation result.
Next, we traverse each character of the string s:
- If the current character is a number, we use a loop to read the following consecutive numbers, and then add or subtract it to
ansaccording to the current sign. - If the current character is
'+', we change the variablesignto positive. - If the current character is
'-', we change the variablesignto negative. - If the current character is
'(', we push the currentansandsigninto the stack, and reset them to empty and 1, and start to calculate the newansandsign. - If the current character is
')', we pop the top two elements of the stack, one is the operator, and the other is the number calculated before the bracket. We multiply the current number by the operator, and add the previous number to get the newans.
After traversing the string s, we return ans.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.
Complexity Comparison
| 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. |
| Stack | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Stack Evaluation | O(n) | O(n) | General case with nested parentheses. Preferred interview solution. |
| Recursive Expression Parsing | O(n) | O(n) | When recursive parsing feels more natural for nested expressions. |
Video Solution
BASIC CALCULATOR | LEETCODE # 224 | PYTHON SOLUTION • Cracking FAANG • 46,921 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Basic Calculator easy or hard?
Basic Calculator Python/Java solution
How to solve Basic Calculator in O(n)?
What is the best approach for Basic Calculator?
Is Basic Calculator asked at Google/Amazon/Meta?
What data structure is used in Basic Calculator?
What is the time complexity of Basic Calculator?
Ready to solve this problem?
Practice Basic Calculator with our built-in code editor and test cases.
Practice on FleetCode