#224
Basic Calculator
Hard Stack for parentheses and signs
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Evaluate a string expression with integers, + and -, unary minus, parentheses and spaces. No eval allowed.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: evaluate + and - with brackets.
Why this works: keep a running result and a sign. On '(' save them on the stack and start fresh; on ')' combine with the saved values.
Example: "1 - (2 + 3)"
result 1, sign -'(' saves (1, -) → inner 5')' → 1 + (-1 × 5) = -4
✦Hints open one at a time
Without parentheses you only need a running result and the current sign.
On '(' push the result and sign so far, then start fresh inside.
On ')' finish the inner result, multiply by the saved sign and add the saved result.
↗Approach
Scan characters: build multi-digit numbers; on +/- add sign × number to result and set the new sign; on '(' push result and sign, reset; on ')' close the number, then result = savedResult + savedSign × result.
</>Solution (Java)
import java.util.*;
class Solution {
public int calculate(String s) {
Deque<Integer> st = new ArrayDeque<>();
int result = 0, sign = 1, num = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '+' || c == '-') {
result += sign * num;
num = 0;
sign = (c == '+') ? 1 : -1;
} else if (c == '(') {
st.push(result); // save the outer state
st.push(sign);
result = 0;
sign = 1;
} else if (c == ')') {
result += sign * num;
num = 0;
result = st.pop() * result + st.pop(); // saved sign, then saved result
}
}
return result + sign * num;
}
}!Common mistake
Forgetting to add the last number after the loop ends.
Complexity
- Time: O(n).
- Space: O(n) for nested parentheses.
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon