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.
1def calculate(s: str) -> int:
2 stack = []
3 result = 0
4 sign = 1
5 i =
This Python solution interprets the expression using a stack to manage parentheses. Numbers are built by processing each digit and results are accumulated using a sign, augmented by data from the stack when closing parentheses are encountered.
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.
1#include <string>
int calculate_inner(const std::string &s, int &index) {
int result = 0, sign = 1;
while (index < s.size()) {
if (s[index] == ' ') {
index++;
} else if (isdigit(s[index])) {
int num = 0;
while (index < s.size() && isdigit(s[index])) {
num = num * 10 + (s[index] - '0');
index++;
}
result += sign * num;
continue;
} else if (s[index] == '+') {
sign = 1;
} else if (s[index] == '-') {
sign = -1;
} else if (s[index] == '(') {
index++;
result += sign * calculate_inner(s, index);
continue;
} else if (s[index] == ')') {
index++;
break;
}
index++;
}
return result;
}
int calculate(const std::string &s) {
int index = 0;
return calculate_inner(s, index);
}
int main() {
std::cout << calculate("(1+(4+5+2)-3)+(6+8)") << std::endl; // Output: 23
return 0;
}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.
The C++ approach uses a recursive function for sub-expression evaluation by managing current index and executing sub-operations inside parentheses directly, propagating results back to outer layers appropriately.