Basic Calculator solution and explanation
Google
9 more videos on this problem
BASIC CALCULATOR | LEETCODE # 224 | PYTHON SOLUTIONCracking FAANG · 21:06 · 46K views
Basic Calculator (Google, Meta, Airbnb) : Explanation ➕ Live Coding 🧑🏻💻👩🏻💻codestorywithMIK · 34:20 · 32K views
Leetcode - Basic Calculator (Python)Timothy H Chang · 7:29 · 17K views
Basic Calculator | Leetcode 224 | Live coding session 🔥🔥🔥Coding Decoded · 17:01 · 15K views
[Java] Leetcode 224. Basic Calculator [Stack & Queue #7]Eric Programming · 12:30 · 10K views
Leetcode 224 - Basic Calculator (JAVA Solution Explained!)LC Bear · 24:51 · 2K views
224. Basic Calculator (Leetcode Hard)Programming Live with Larry · 29:20 · 1K views
Daily Leetcode #964: Nov 20, 2022 - 224. Basic CalculatorProgramming Live with Larry · 12:44 · 1K views
Daily Leetcode #529: Sep 11, 2021 - 224. Basic CalculatorProgramming Live with Larry · 28:00 · 651 views
Leetcode 224 - Basic Calculator - JavaCoding Interview Preparation · 17:41 · 456 views
The problem
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.
def calculate(s: str) -> int:
stack = []
result = 0
sign = 1
i = 0
while i < len(s):
if s[i] == ' ':
i += 1
continue
if s[i] == '+':
sign = 1
elif s[i] == '-':
sign = -1
elif s[i] == '(':
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif s[i] == ')':
result = result * stack.pop() + stack.pop()
else:
num = 0
while i < len(s) and s[i].isdigit():
num = num * 10 + int(s[i])
i += 1
i -= 1
result += sign * num
i += 1
return result
print(calculate("(1+(4+5+2)-3)+(6+8)")) # Output: 23import java.util.Stack;
public class BasicCalculator {
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int result = 0, sign = 1, n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int num = 0;
while (i < n && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
i--;
result += sign * num;
} else if (c == '+') {
sign = 1;
} else if (c == '-') {
sign = -1;
} else if (c == '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (c == ')') {
result = result * stack.pop() + stack.pop();
}
}
return result;
}
public static void main(String[] args) {
BasicCalculator calculator = new BasicCalculator();
System.out.println(calculator.calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23
}
}#include <iostream>
#include <stack>
int calculate(const std::string &s) {
std::stack<int> stack;
int result = 0, sign = 1, n = s.size(), i = 0;
while (i < n) {
if (s[i] == ' ') {
i++;
continue;
}
if (s[i] == '+') {
sign = 1;
} else if (s[i] == '-') {
sign = -1;
} else if (s[i] == '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (s[i] == ')') {
result *= stack.top(); stack.pop();
result += stack.top(); stack.pop();
} else if (isdigit(s[i])) {
long num = 0;
while (i < n && isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
i++;
}
i--;
result += sign * num;
}
i++;
}
return result;
}
int main() {
std::cout << calculate("(1+(4+5+2)-3)+(6+8)") << std::endl; // Output: 23
return 0;
}function calculate(s) {
let stack = [];
let result = 0, sign = 1, len = s.length;
for (let i = 0; i < len; i++) {
if (s[i] === ' ') continue;
if (s[i] === '+') {
sign = 1;
} else if (s[i] === '-') {
sign = -1;
} else if (s[i] === '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (s[i] === ')') {
result = result * stack.pop() + stack.pop();
} else {
let num = 0;
while (i < len && !isNaN(parseInt(s[i]))) {
num = num * 10 + parseInt(s[i]);
i++;
}
result += sign * num;
i--;
}
}
return result;
}
console.log(calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23#include <stdio.h>
#include <stdlib.h>
int calculate(const char* s) {
int stack[300000], top = -1, n = strlen(s);
int sign = 1, result = 0, i = 0;
while (i < n) {
if (s[i] == ' ') {
i++;
continue;
}
if (s[i] == '-') {
sign = -1;
} else if (s[i] == '+') {
sign = 1;
} else if (s[i] == '(') {
stack[++top] = result;
stack[++top] = sign;
result = 0;
sign = 1;
} else if (s[i] == ')') {
result *= stack[top--];
result += stack[top--];
} else if (isdigit(s[i])) {
long num = 0;
while (i < n && isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
i++;
}
i--;
result += num * sign;
}
i++;
}
return result;
}
int main() {
printf("%d\n", calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23
return 0;
}using System;
using System.Collections.Generic;
class BasicCalculator {
public static int Calculate(string s) {
var stack = new Stack<int>();
int result = 0, sign = 1, n = s.Length;
for (int i = 0; i < n; i++) {
if (s[i] == ' ') {
continue;
}
if (s[i] == '+') {
sign = 1;
} else if (s[i] == '-') {
sign = -1;
} else if (s[i] == '(') {
stack.Push(result);
stack.Push(sign);
result = 0;
sign = 1;
} else if (s[i] == ')') {
result = result * stack.Pop() + stack.Pop();
} else if (Char.IsDigit(s[i])) {
int num = 0;
while (i < n && Char.IsDigit(s[i])) {
num = num * 10 + (s[i] - '0');
i++;
}
i--;
result += sign * num;
}
}
return result;
}
public static void Main() {
Console.WriteLine(Calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23
}
}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.
Time Complexity: O(n)
Space Complexity: O(n) from stack usage.
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.
def calculate(s: str) -> int:
def helper(index: int) -> (int, int):
result = 0
sign = 1
while index < len(s):
char = s[index]
if char == ' ':
index += 1
continue
elif char.isdigit():
num = 0
while index < len(s) and s[index].isdigit():
num = num * 10 + int(s[index])
index += 1
result += sign * num
continue
elif char == '+':
sign = 1
elif char == '-':
sign = -1
elif char == '(':
index, num = helper(index + 1)
result += sign * num
continue
elif char == ')':
return index + 1, result
index += 1
return index, result
return helper(0)[1]
print(calculate("(1+(4+5+2)-3)+(6+8)")) # Output: 23public class BasicCalculator {
private int calculateInner(char[] s, int[] idx) {
int result = 0, sign = 1;
while (idx[0] < s.length) {
if (s[idx[0]] == ' ') {
idx[0]++;
} else if (s[idx[0]] == '+') {
sign = 1;
idx[0]++;
} else if (s[idx[0]] == '-') {
sign = -1;
idx[0]++;
} else if (s[idx[0]] == '(') {
idx[0]++;
result += sign * calculateInner(s, idx);
} else if (s[idx[0]] == ')') {
idx[0]++;
break;
} else {
int num = 0;
while (idx[0] < s.length && Character.isDigit(s[idx[0]])) {
num = num * 10 + s[idx[0]++] - '0';
}
result += sign * num;
}
}
return result;
}
public int calculate(String s) {
return calculateInner(s.toCharArray(), new int[]{0});
}
public static void main(String[] args) {
BasicCalculator calculator = new BasicCalculator();
System.out.println(calculator.calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23
}
}#include <iostream>
#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;
}function calculate(s) {
function helper(index) {
let result = 0, sign = 1;
while (index < s.length) {
const c = s[index];
if (c === ' ') {
index++;
continue;
}
if (c === '+') {
sign = 1;
} else if (c === '-') {
sign = -1;
} else if (c === '(') {
const res = helper(index + 1);
index = res[0];
result += sign * res[1];
continue;
} else if (c === ')') {
index++;
break;
} else {
let num = 0;
while (index < s.length && !isNaN(parseInt(s[index]))) {
num = num * 10 + parseInt(s[index]);
index++;
}
result += sign * num;
continue;
}
index++;
}
return [index, result];
}
return helper(0)[1];
}
console.log(calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23#include <stdio.h>
#include <ctype.h>
int next_int(const char* s, int* index) {
int val = 0;
while (isdigit(s[*index])) {
val = val * 10 + (s[*index] - '0');
(*index)++;
}
return val;
}
int calculate_inner(const char* s, int* index) {
int val = 0, sign = 1;
while (s[*index] != '\0') {
if (s[*index] == ' ') {
(*index)++;
continue;
}
if (isdigit(s[*index])) {
val += sign * next_int(s, index);
(*index)--;
} else if (s[*index] == '+') {
sign = 1;
} else if (s[*index] == '-') {
sign = -1;
} else if (s[*index] == '(') {
(*index)++;
val += sign * calculate_inner(s, index);
} else if (s[*index] == ')') {
break;
}
(*index)++;
}
return val;
}
int calculate(const char* s) {
int index = 0;
return calculate_inner(s, &index);
}
int main() {
printf("%d\n", calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23
return 0;
}using System;
class BasicCalculator {
private static int CalculateInner(char[] s, ref int index) {
int result = 0, sign = 1;
while (index < s.Length) {
if (s[index] == ' ') index++;
else if (s[index] == '+') {
sign = 1;
index++;
} else if (s[index] == '-') {
sign = -1;
index++;
} else if (s[index] == '(') {
index++;
result += sign * CalculateInner(s, ref index);
} else if (s[index] == ')') {
index++;
break;
} else {
int num = 0;
while (index < s.Length && char.IsDigit(s[index])) {
num = num * 10 + s[index++] - '0';
}
result += sign * num;
}
}
return result;
}
public static int Calculate(string s) {
int index = 0;
return CalculateInner(s.ToCharArray(), ref index);
}
public static void Main() {
Console.WriteLine(Calculate("(1+(4+5+2)-3)+(6+8)")); // Output: 23
}
}The Python recursion uses a nested helper function, self-contained to evaluate sub-expression operands iteratively. Each recursion call accounts for proceeding beyond a parenthesis to assimilate aggregate results with prior computed outcomes.
Time Complexity: O(n)
Space Complexity: O(n) for maintaining recursion state data implicitly.
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.
function calculate(s: string): number {
const stk: number[] = [];
let sign = 1;
let ans = 0;
const n = s.length;
for (let i = 0; i < n; ++i) {
if (s[i] === ' ') {
continue;
}
if (s[i] === '+') {
sign = 1;
} else if (s[i] === '-') {
sign = -1;
} else if (s[i] === '(') {
stk.push(ans);
stk.push(sign);
ans = 0;
sign = 1;
} else if (s[i] === ')') {
ans *= stk.pop() as number;
ans += stk.pop() as number;
} else {
let x = 0;
let j = i;
for (; j < n && !isNaN(Number(s[j])) && s[j] !== ' '; ++j) {
x = x * 10 + (s[j].charCodeAt(0) - '0'.charCodeAt(0));
}
ans += sign * x;
i = j - 1;
}
}
return ans;
}func calculate(s string) (ans int) {
stk := []int{}
sign := 1
n := len(s)
for i := 0; i < n; i++ {
switch s[i] {
case ' ':
case '+':
sign = 1
case '-':
sign = -1
case '(':
stk = append(stk, ans)
stk = append(stk, sign)
ans, sign = 0, 1
case ')':
ans *= stk[len(stk)-1]
stk = stk[:len(stk)-1]
ans += stk[len(stk)-1]
stk = stk[:len(stk)-1]
default:
x := 0
j := i
for ; j < n && '0' <= s[j] && s[j] <= '9'; j++ {
x = x*10 + int(s[j]-'0')
}
ans += sign * x
i = j - 1
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative with Stack | Time Complexity: O(n) |
| Recursive | Time Complexity: O(n) |
| Stack | – |
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. |
Frequently asked questions
Is Basic Calculator easy or hard?
Basic Calculator is classified as a hard problem because it combines string parsing, stack management, and nested expression evaluation. Many candidates initially struggle with correctly handling parentheses and sign propagation across scopes.
Basic Calculator Python/Java solution
Python and Java solutions typically implement the stack-based scan of the expression. Both languages iterate through the characters, build numbers from digits, push state when '(' appears, and resolve sub-expressions when ')'. The logic remains O(n) time with O(n) stack space.
How to solve Basic Calculator in O(n)?
Iterate through the string while maintaining a running result, current number, and sign. When encountering '(', push the current state onto a stack and start evaluating a new sub-expression. When ')' appears, combine the computed value with the previous state. Each character is processed once, producing O(n) time complexity.
What is the best approach for Basic Calculator?
The most common solution uses a stack to evaluate the expression while scanning the string once. Each time a parenthesis is encountered, the current result and sign are pushed onto the stack and restored later. This approach runs in O(n) time and O(n) space and is widely expected in technical interviews.
Is Basic Calculator asked at Google/Amazon/Meta?
Basic Calculator is a common string parsing and stack problem that appears in interviews at large tech companies including Google, Amazon, and Meta. Variants such as Basic Calculator II and III are also frequently used to test parsing and stack fundamentals.
What data structure is used in Basic Calculator?
A stack is the primary data structure used to manage nested parentheses and restore previous evaluation states. The algorithm also uses simple variables to track the current number, running result, and sign while scanning the string.
What is the time complexity of Basic Calculator?
The optimal algorithms run in O(n) time because each character in the expression is processed exactly once. Both the stack-based and recursive approaches achieve this complexity. Space complexity is O(n) due to the stack or recursion depth for nested parentheses.