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).The #224 Basic Calculator problem asks you to evaluate a mathematical expression represented as a string. The expression may contain integers, addition and subtraction operators, spaces, and nested parentheses. Since parentheses affect evaluation order, a stack-based approach or recursive evaluation works well.
A common strategy is to iterate through the string while maintaining a running result, the current sign, and the current number being built. When encountering an opening parenthesis (, push the current result and sign onto a stack and start evaluating the new sub-expression. When a closing parenthesis ) appears, compute the sub-expression result and combine it with the previous state stored on the stack.
This approach processes each character once, ensuring efficiency. By carefully managing intermediate results and signs, the algorithm correctly handles nested expressions. The overall complexity remains linear relative to the length of the input string.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based expression evaluation | O(n) | O(n) |
| Recursive parsing of parentheses | O(n) | O(n) |
Cracking FAANG
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int calculate(const char* s) {
5 int stack[300000]
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.
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.
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.
1public
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Basic Calculator and similar expression evaluation problems frequently appear in FAANG-style interviews. They test understanding of stacks, parsing, and careful handling of edge cases like spaces and nested parentheses.
The optimal approach uses a stack to evaluate expressions while scanning the string once. The stack stores previous results and signs when encountering parentheses, allowing nested expressions to be evaluated correctly. This leads to an O(n) time complexity solution.
A stack is the most effective data structure for this problem. It helps store intermediate results and signs when entering and exiting parentheses, making it easy to evaluate nested expressions in the correct order.
Parentheses change the order of evaluation in expressions. The algorithm must temporarily store the current computation state when entering parentheses and restore it after finishing the sub-expression, which is why stacks or recursion are commonly used.
This Java implementation exploits recursion depth diversity for expression segments inside parentheses, integrating resolved pieces of the expression hierarchically as evaluation resumes outside each finished sub-context.