Basic Calculator III solution and explanation
Google
9 more videos on this problem
LeetCode 224,227,772 Basic Calculator 1,2,3 Explanation and Solutionhappygirlzt · 19:25 · 13K views
BASIC CALCULATOR III | LEETCODE # 772 | PYTHON SOLUTIONCracking FAANG · 13:05 · 11K views
Basic Calculator III | Leetcode 772Pepcoding · 28:43 · 6K views
[Java] Leetcode 772. Basic Calculator III [Stack & Queue #9]Eric Programming · 7:14 · 3K views
【每日一题】772. Basic Calculator III, 5/27/2020Huifeng Guan · 23:11 · 2K views
772. Basic Calculator III , Top Interview DSA Questions, Java Solution with time complexityShrayansh Jain · 15:49 · 2K views
Baozi Training Leetcode 772 solution: Basic Calculator IIIBaozi Training · 12:55 · 1K views
leetcode log(小雨）772. Basic Calculator IIILing Chen · 25:02 · 459 views
Universal Solution for Basic Calculator I, II, and IIINeedCode⚡ · 13:48 · 383 views
Leetcode 772 Basic Calculator III带老婆转码 · 13:58 · 253 views
The problem
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
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 = "6-4/2" Output: 4
Example 3:
Input: s = "2*(5+5*2)/3+(6/2+8)" Output: 21
Constraints:
1 <= s <= 104sconsists of digits,'+','-','*','/','(', and')'.sis a valid expression.
Approach overview
Problem Overview: You need to evaluate a string arithmetic expression containing integers, operators +, -, *, /, and nested parentheses. The expression may include spaces, and operator precedence must be respected while correctly handling parentheses.
Approach 1: Recursive Expression Evaluation (O(n) time, O(n) space)
This approach processes the string using recursion to evaluate sub-expressions inside parentheses. Iterate through the characters, build numbers digit by digit, and apply operators when encountered. When you see (, recursively evaluate until the matching ). A stack tracks intermediate values so multiplication and division can be applied immediately while addition and subtraction defer until summation. Each character is processed once, giving O(n) time and recursion/stack usage of O(n) space.
Approach 2: Two-Stack Expression Parsing (O(n) time, O(n) space)
This classic expression evaluator uses one stack for numbers and another for operators. Iterate through the string, push numbers to the value stack, and push operators while respecting precedence rules. Before pushing a new operator, resolve any operators with higher or equal precedence already on the stack. Parentheses trigger evaluation until the matching opening bracket. This mirrors the Shunting Yard technique and handles precedence cleanly using explicit operator comparisons.
Approach 3: Single Stack with Precedence Handling (O(n) time, O(n) space)
The optimized solution scans the string once and uses a single stack to manage numbers. Track the previous operator and apply logic when a new operator or closing parenthesis appears. Push numbers for + and -, but immediately compute * or / with the stack top. When encountering (, recursively evaluate the inner expression and treat the returned value as the current number. This approach combines operator precedence and parenthesis handling efficiently while keeping the code concise.
These solutions rely heavily on concepts from stack-based parsing and recursive expression evaluation from recursion. Since the problem operates on characters and tokens inside an expression string, familiarity with string traversal is essential.
Recommended for interviews: The single-stack recursive evaluation is what interviewers typically expect. It shows you understand operator precedence, expression parsing, and stack-based evaluation in linear time. Mentioning the two-stack parsing method first demonstrates foundational understanding, but implementing the optimized single-pass approach proves stronger problem-solving ability.
Solution
class Solution:
def calculate(self, s: str) -> int:
def dfs(q):
num, sign, stk = 0, "+", []
while q:
c = q.popleft()
if c.isdigit():
num = num * 10 + int(c)
if c == "(":
num = dfs(q)
if c in "+-*/)" or not q:
match sign:
case "+":
stk.append(num)
case "-":
stk.append(-num)
case "*":
stk.append(stk.pop() * num)
case "/":
stk.append(int(stk.pop() / num))
num, sign = 0, c
if c == ")":
break
return sum(stk)
return dfs(deque(s))class Solution {
public:
// Define an operation function that performs mathematical operations based on the operator
int operate(int b, char ch, int a) {
// Note the order of ab
switch (ch) {
case '+':
return a + b; // Addition
case '-':
return a - b; // Subtraction
case '*':
return a * b; // Multiplication
case '/':
return a / b; // Division
default:
break;
}
return 0; // Default return 0, handle invalid operators
}
// Calculate the value of the string expression
int calculate(string s) {
int preority[250]; // Operator precedence array
preority['+'] = 1;
preority['-'] = 1;
preority['*'] = 2;
preority['/'] = 2;
preority['('] = 0;
preority[')'] = 0;
stack<char> op; // Operator stack
stack<int> num; // Operand stack
int stringsize = s.size(); // Length of the string
int i = 0;
char ch;
// Traverse the string
for (; i < stringsize; i++) {
ch = s[i];
if (ch == ' ') {
continue; // Skip spaces
}
if (ch >= '0' && ch <= '9') {
int realnum = ch - '0'; // Convert character to number
// Handle multi-digit numbers
while (s[i + 1] >= '0' && s[i + 1] <= '9') {
i++;
realnum *= 10;
realnum += s[i] - '0';
}
num.push(realnum); // Push the number onto the stack
} else {
// Handle operators
if (op.empty() || ch == '(' || preority[ch] > preority[op.top()]) {
// Special case, handle the first character being '-' or '+'
if (num.empty() && (ch == '-' || ch == '+')) {
num.push(0);
}
op.push(ch); // Push the operator onto the stack
// Handle expressions inside parentheses
if (ch == '(') {
int j = i;
while (j + 1 < stringsize) {
// Preprocess the first operator inside the parentheses
if (s[j + 1] == '-' || s[j + 1] == '+') {
num.push(0);
}
if (s[j + 1] != ' ') {
break;
}
j++;
}
}
} else if (ch == ')') {
// Handle right parentheses
char ch2 = ')';
ch2 = op.top();
op.pop();
while (ch2 != '(') {
int a = num.top();
num.pop();
int b = num.top();
num.pop();
num.push(operate(a, ch2, b)); // Calculate and push the result
ch2 = op.top();
op.pop();
}
} else if (preority[ch] <= preority[op.top()]) {
// Handle cases where the precedence is less than or equal to the top of the stack
char ch2;
ch2 = op.top();
while (!op.empty() && preority[ch] <= preority[op.top()] && ch2 != '(') {
op.pop();
int a = num.top();
num.pop();
int b = num.top();
num.pop();
num.push(operate(a, ch2, b)); // Calculate and push the result
if (!op.empty()) {
ch2 = op.top();
} else {
break;
}
}
op.push(ch); // Push the current operator onto the stack
}
}
}
// Handle the remaining expressions in the stack
while (!op.empty()) {
ch = op.top();
op.pop();
int a = num.top();
num.pop();
int b = num.top();
num.pop();
num.push(operate(a, ch, b)); // Calculate and push the result
}
return num.top(); // Return the final result
}
};Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Expression Evaluation | O(n) | O(n) | Clean handling of nested parentheses using recursion |
| Two-Stack Expression Parsing | O(n) | O(n) | When implementing classic infix expression evaluation with precedence rules |
| Single Stack with Precedence Handling | O(n) | O(n) | Best interview solution; single pass with immediate handling of * and / |
Frequently asked questions
Is Basic Calculator III easy or hard?
Basic Calculator III is rated Hard because it combines multiple concepts: string parsing, operator precedence, stack-based evaluation, and nested parentheses. While each idea is manageable individually, implementing them together correctly requires careful control flow and edge case handling.
Basic Calculator III Python/Java solution
In Python or Java, the common solution iterates through the string, builds numbers, and uses a stack to apply operators based on precedence. When encountering parentheses, a recursive helper evaluates the sub-expression and returns its result. The algorithm remains O(n) time and O(n) space across languages.
How to solve Basic Calculator III in O(n)?
Scan the expression from left to right while building numbers and tracking the previous operator. Use a stack to store intermediate values: push numbers for + and -, and immediately compute multiplication or division with the stack top. When encountering parentheses, recursively evaluate the inner expression and treat the result as a number. Every character is processed once, giving O(n) time.
What is the best approach for Basic Calculator III?
The best approach uses a stack combined with recursion to evaluate expressions while scanning the string once. Numbers are pushed to a stack and multiplication or division is computed immediately, while addition and subtraction are accumulated later. Parentheses trigger recursive evaluation of sub-expressions. This solution runs in O(n) time with O(n) space.
Is Basic Calculator III asked at Google/Amazon/Meta?
Expression evaluation and calculator-style parsing problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants such as Basic Calculator I, II, and III test understanding of stacks, recursion, and operator precedence handling.
What data structure is used in Basic Calculator III?
The primary data structure is a stack. It stores intermediate numbers while operators determine how values are combined. Recursion is often used alongside the stack to evaluate expressions inside parentheses.
What is the time complexity of Basic Calculator III?
The optimal solution runs in O(n) time where n is the length of the expression string. Each character is processed once while building numbers or applying operators. Stack operations are constant time, so the overall complexity remains linear with O(n) auxiliary space.