Basic Calculator
Basic Calculator is a hard stack problem solved with the stack basics pattern.
The best approach, optimal (stack of saved results and signs), runs in O(n) time and O(n) space.
Problem
Evaluate an expression string containing non-negative integers, +, -, brackets and spaces. A - can also be unary, as in -2 or -(1 + 2). Do not use a built-in eval.
Examples
Example 1
- Input
s = " 2 - (5 - 6) "- Output
3
Example 2
- Input
s = "-(3 + (4 + 5))"- Output
-12- Why
- A unary minus in front of a bracket flips everything inside.
Constraints
1 <= s.length <= 3 * 10^5- Digits, + - ( ) and spaces. No * or /.
- No library eval.
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 (2 examples, or your own). Submit also runs 13 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.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
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 |
|---|---|---|
| Optimal (stack of saved results and signs) | O(n) | O(n) |
1Optimal (stack of saved results and signs)
O(n)O(n)The stack grows with nesting depth.Scan left to right keeping result, the current number and the sign (+1 or -1) for the next number. On '(' push result and sign, then start fresh inside. On ')' finish the inner result, multiply by the saved sign and add the saved result.
- Digit: number = number * 10 + d.
- + or -: result += sign * number; number = 0; sign = ±1.
- (: push result, push sign; result = 0; sign = 1.
- ): result += sign * number; number = 0; result = result * pop() + pop().
- At the end return result + sign * number.
class Solution {
public int calculate(String s) {
Deque<Integer> st = new ArrayDeque<>();
int result = 0, number = 0, sign = 1;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '+' || c == '-') {
result += sign * number;
number = 0;
sign = c == '+' ? 1 : -1;
} else if (c == '(') {
st.push(result);
st.push(sign);
result = 0;
sign = 1;
} else if (c == ')') {
result += sign * number;
number = 0;
result = result * st.pop() + st.pop();
}
}
return result + sign * number;
}
}class Solution:
def calculate(self, s: str) -> int:
st = []
result, number, sign = 0, 0, 1
for c in s:
if c.isdigit():
number = number * 10 + (ord(c) - ord('0'))
elif c == '+' or c == '-':
result += sign * number
number = 0
sign = 1 if c == '+' else -1
elif c == '(':
st.append(result)
st.append(sign)
result = 0
sign = 1
elif c == ')':
result += sign * number
number = 0
result = result * st.pop() + st.pop()
return result + sign * numberclass Solution {
public:
int calculate(string s) {
vector<int> st;
int result = 0, number = 0, sign = 1;
for (char c : s) {
if (isdigit(c)) {
number = number * 10 + (c - '0');
} else if (c == '+' || c == '-') {
result += sign * number;
number = 0;
sign = c == '+' ? 1 : -1;
} else if (c == '(') {
st.push_back(result);
st.push_back(sign);
result = 0;
sign = 1;
} else if (c == ')') {
result += sign * number;
number = 0;
int savedSign = st.back(); st.pop_back();
int savedResult = st.back(); st.pop_back();
result = result * savedSign + savedResult;
}
}
return result + sign * number;
}
};function calculate(s) {
const st = [];
let result = 0, number = 0, sign = 1;
for (const c of s) {
if (c >= '0' && c <= '9') {
number = number * 10 + (c.charCodeAt(0) - 48);
} else if (c === '+' || c === '-') {
result += sign * number;
number = 0;
sign = c === '+' ? 1 : -1;
} else if (c === '(') {
st.push(result);
st.push(sign);
result = 0;
sign = 1;
} else if (c === ')') {
result += sign * number;
number = 0;
result = result * st.pop() + st.pop();
}
}
return result + sign * number;
}Edge cases to test
- Unary minus: -2 or -(...)
- Multi-digit numbers
- Nested brackets
Hints
Hint 1
With only + and -, each number is simply added with a sign. What decides that sign?
Hint 2
On '(' save the current result and sign; on ')' combine.
FAQ
What is the best time complexity for Basic Calculator?
Optimal (stack of saved results and signs) runs in O(n) time and O(n) extra space.
Which pattern does Basic Calculator use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Which edge cases should I test for Basic Calculator?
Unary minus: -2 or -(...); Multi-digit numbers; Nested brackets.