Basic Calculator III
Basic Calculator III is a hard stack problem solved with the stack basics pattern.
The best approach, optimal (single pass with a shared index), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (recursion on substrings) up.
Problem
Implement a calculator that evaluates a string expression s and returns its integer value. The expression may contain non-negative integers, the operators +, -, *, /, opening and closing parentheses, and spaces.
* and / bind tighter than + and -, operators of the same precedence are applied from left to right, and parentheses override everything. Integer division truncates toward zero.
You may not use any built-in function that evaluates strings as expressions.
Examples
Example 1
- Input
s = "7 - 2 * (3 + 1)"- Output
-1- Why
- The parentheses give 4, then 2 * 4 = 8, and 7 - 8 = -1.
Example 2
- Input
s = "(9 + 5) / 4 * 3"- Output
9- Why
- 14 / 4 = 3 after truncation, and 3 * 3 = 9 (operators of equal precedence go left to right).
Example 3
- Input
s = "20/(2*(1+2)-10)"- Output
-5- Why
- The inner value is 6 - 10 = -4, and 20 / -4 = -5.
Constraints
1 <= s.length <= 10^4sconsists of digits,'+','-','*','/','(',')'and spacessis a valid expression; every number in it is a non-negative integer, and there is no unary minus- Every intermediate result fits in a signed 32-bit integer, and no division is by zero
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (recursion on substrings) | O(n · d) | O(n) |
| Optimal (single pass with a shared index) | O(n) | O(n) |
1Brute force (recursion on substrings)
O(n · d)Every opening parenthesis triggers a scan for its match, and a character inside d nested groups is scanned d times (O(n²) worst case).O(n)Stacks of terms and recursion frames together hold O(n) items.Evaluate a range s[lo..hi) with the Basic Calculator II stack. Whenever a ( appears, scan forward to find its matching ), evaluate the inside recursively and use the result as the current number. Finding each matching parenthesis rescans the group, so deeply nested input costs quadratic time.
- eval(lo, hi): stack = [], op = '+', num = 0.
- For each character: digits extend num; '(' → find its match j by counting depth, num = eval(i + 1, j), jump to j + 1; an operator → apply(op, num) to the stack, op = that operator, num = 0.
- apply: '+' pushes num, '-' pushes -num, '*' and '/' replace the top with top * num or top / num (truncated).
- At the end apply the last (op, num) and return the sum of the stack.
class Solution {
public int calculate(String s) {
return eval(s, 0, s.length());
}
private int eval(String s, int lo, int hi) {
Deque<Integer> stack = new ArrayDeque<>();
char op = '+';
int num = 0;
int i = lo;
while (i < hi) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
i++;
} else if (c == '(') {
int depth = 0, j = i;
while (true) {
if (s.charAt(j) == '(') depth++;
else if (s.charAt(j) == ')' && --depth == 0) break;
j++;
}
num = eval(s, i + 1, j);
i = j + 1;
} else if (c == ' ') {
i++;
} else {
apply(stack, op, num);
op = c;
num = 0;
i++;
}
}
apply(stack, op, num);
int sum = 0;
for (int v : stack) sum += v;
return sum;
}
private void apply(Deque<Integer> stack, char op, int num) {
if (op == '+') stack.push(num);
else if (op == '-') stack.push(-num);
else if (op == '*') stack.push(stack.pop() * num);
else stack.push(stack.pop() / num);
}
}class Solution:
def calculate(self, s: str) -> int:
def div(a: int, b: int) -> int:
q = abs(a) // abs(b)
return q if (a >= 0) == (b > 0) else -q
def apply(stack: List[int], op: str, num: int) -> None:
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
else:
stack.append(div(stack.pop(), num))
def evaluate(lo: int, hi: int) -> int:
stack = []
op, num, i = '+', 0, lo
while i < hi:
c = s[i]
if c.isdigit():
num = num * 10 + int(c)
i += 1
elif c == '(':
depth, j = 0, i
while True:
if s[j] == '(':
depth += 1
elif s[j] == ')':
depth -= 1
if depth == 0:
break
j += 1
num = evaluate(i + 1, j)
i = j + 1
elif c == ' ':
i += 1
else:
apply(stack, op, num)
op, num = c, 0
i += 1
apply(stack, op, num)
return sum(stack)
return evaluate(0, len(s))class Solution {
public:
int calculate(string s) {
return eval(s, 0, s.size());
}
private:
int eval(const string& s, int lo, int hi) {
vector<int> stack;
char op = '+';
int num = 0, i = lo;
while (i < hi) {
char c = s[i];
if (isdigit(c)) {
num = num * 10 + (c - '0');
i++;
} else if (c == '(') {
int depth = 0, j = i;
while (true) {
if (s[j] == '(') depth++;
else if (s[j] == ')' && --depth == 0) break;
j++;
}
num = eval(s, i + 1, j);
i = j + 1;
} else if (c == ' ') {
i++;
} else {
apply(stack, op, num);
op = c;
num = 0;
i++;
}
}
apply(stack, op, num);
int sum = 0;
for (int v : stack) sum += v;
return sum;
}
void apply(vector<int>& stack, char op, int num) {
if (op == '+') stack.push_back(num);
else if (op == '-') stack.push_back(-num);
else if (op == '*') stack.back() *= num;
else stack.back() /= num;
}
};function calculate(s) {
const apply = (stack, op, num) => {
if (op === '+') stack.push(num);
else if (op === '-') stack.push(-num);
else if (op === '*') stack.push(stack.pop() * num);
else stack.push(Math.trunc(stack.pop() / num));
};
const evaluate = (lo, hi) => {
const stack = [];
let op = '+', num = 0, i = lo;
while (i < hi) {
const c = s[i];
if (c >= '0' && c <= '9') {
num = num * 10 + (c.charCodeAt(0) - 48);
i++;
} else if (c === '(') {
let depth = 0, j = i;
while (true) {
if (s[j] === '(') depth++;
else if (s[j] === ')' && --depth === 0) break;
j++;
}
num = evaluate(i + 1, j);
i = j + 1;
} else if (c === ' ') {
i++;
} else {
apply(stack, op, num);
op = c;
num = 0;
i++;
}
}
apply(stack, op, num);
return stack.reduce((a, b) => a + b, 0);
};
return evaluate(0, s.length);
}2Optimal (single pass with a shared index)
O(n)The shared index moves forward on every step, so each character is processed once.O(n)The term stacks and the recursion depth (one frame per open parenthesis) are O(n) in total.Use the same term stack, but read the string with one index shared by all recursion levels. On ( the parser calls itself; the inner call consumes characters up to its matching ), returns the group's value, and the outer call continues right after it. No character is ever scanned twice.
- Keep a field i = 0 and call parse().
- parse(): stack = [], op = '+', num = 0. While i < n: skip spaces; digit → extend num; '(' → i++, num = parse(); ')' → i++ and stop; operator → apply(op, num), op = it, num = 0.
- After the loop apply(op, num) and return the sum of the stack.
class Solution {
private int i;
public int calculate(String s) {
i = 0;
return parse(s);
}
private int parse(String s) {
Deque<Integer> stack = new ArrayDeque<>();
char op = '+';
int num = 0;
while (i < s.length()) {
char c = s.charAt(i);
if (c == ' ') {
i++;
} else if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
i++;
} else if (c == '(') {
i++;
num = parse(s);
} else if (c == ')') {
i++;
break;
} else {
apply(stack, op, num);
op = c;
num = 0;
i++;
}
}
apply(stack, op, num);
int sum = 0;
for (int v : stack) sum += v;
return sum;
}
private void apply(Deque<Integer> stack, char op, int num) {
if (op == '+') stack.push(num);
else if (op == '-') stack.push(-num);
else if (op == '*') stack.push(stack.pop() * num);
else stack.push(stack.pop() / num);
}
}class Solution:
def calculate(self, s: str) -> int:
n = len(s)
i = 0
def div(a: int, b: int) -> int:
q = abs(a) // abs(b)
return q if (a >= 0) == (b > 0) else -q
def apply(stack: List[int], op: str, num: int) -> None:
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
else:
stack.append(div(stack.pop(), num))
def parse() -> int:
nonlocal i
stack = []
op, num = '+', 0
while i < n:
c = s[i]
if c == ' ':
i += 1
elif c.isdigit():
num = num * 10 + int(c)
i += 1
elif c == '(':
i += 1
num = parse()
elif c == ')':
i += 1
break
else:
apply(stack, op, num)
op, num = c, 0
i += 1
apply(stack, op, num)
return sum(stack)
return parse()class Solution {
public:
int calculate(string s) {
i = 0;
return parse(s);
}
private:
size_t i = 0;
int parse(const string& s) {
vector<int> stack;
char op = '+';
int num = 0;
while (i < s.size()) {
char c = s[i];
if (c == ' ') {
i++;
} else if (isdigit(c)) {
num = num * 10 + (c - '0');
i++;
} else if (c == '(') {
i++;
num = parse(s);
} else if (c == ')') {
i++;
break;
} else {
apply(stack, op, num);
op = c;
num = 0;
i++;
}
}
apply(stack, op, num);
int sum = 0;
for (int v : stack) sum += v;
return sum;
}
void apply(vector<int>& stack, char op, int num) {
if (op == '+') stack.push_back(num);
else if (op == '-') stack.push_back(-num);
else if (op == '*') stack.back() *= num;
else stack.back() /= num;
}
};function calculate(s) {
let i = 0;
const apply = (stack, op, num) => {
if (op === '+') stack.push(num);
else if (op === '-') stack.push(-num);
else if (op === '*') stack.push(stack.pop() * num);
else stack.push(Math.trunc(stack.pop() / num));
};
const parse = () => {
const stack = [];
let op = '+', num = 0;
while (i < s.length) {
const c = s[i];
if (c === ' ') {
i++;
} else if (c >= '0' && c <= '9') {
num = num * 10 + (c.charCodeAt(0) - 48);
i++;
} else if (c === '(') {
i++;
num = parse();
} else if (c === ')') {
i++;
break;
} else {
apply(stack, op, num);
op = c;
num = 0;
i++;
}
}
apply(stack, op, num);
return stack.reduce((a, b) => a + b, 0);
};
return parse();
}Edge cases to test
- A single number, possibly wrapped in several pairs of parentheses
- Division that truncates a negative result toward zero, like 7 / (0 - 2) = -3
- Deeply nested parentheses
- Spaces anywhere between tokens
- Multiplication and division chained left to right, like 8 / 3 * 3 = 6
Hints
Hint 1
Without parentheses this is Basic Calculator II: keep a stack of terms, push +x or -x, and combine * and / with the top of the stack immediately.
Hint 2
A parenthesised group is just a number whose value comes from evaluating the inside with the same routine.
Hint 3
Use a shared index and recursion: on '(' recurse, and return to the caller when you hit the matching ')'. Every character is then read exactly once.
FAQ
What is the best time complexity for Basic Calculator III?
Optimal (single pass with a shared index) runs in O(n) time and O(n) extra space. The shared index moves forward on every step, so each character is processed once.
Which pattern does Basic Calculator III use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Basic Calculator III?
Yes. Brute force (recursion on substrings) takes O(n · d) time and O(n) space. Evaluate a range s[lo..hi) with the Basic Calculator II stack.
Which edge cases should I test for Basic Calculator III?
A single number, possibly wrapped in several pairs of parentheses; Division that truncates a negative result toward zero, like 7 / (0 - 2) = -3; Deeply nested parentheses; Spaces anywhere between tokens; Multiplication and division chained left to right, like 8 / 3 3 = 6.