Evaluate a Calculator Expression With Parentheses
Solve this Problems containing non-negative integers, +, -, and matched parentheses — no multiplication, division, or spaces — respecting the fact that a sign in front of a parenthesized group applies to the whole group, not just its first term.
Since there's no operator precedence to worry about here — only left-to-right evaluation and the way parentheses can flip a sign across an entire sub-expression — a single pass suffices, as long as entering and leaving a parenthesized group is handled correctly. Pushing the outer context (the result and sign pending before the group started) onto a stack the moment '(' is seen, and popping it back the moment ')' is seen, means never needing to know in advance where a group ends: the stack remembers exactly what to resume, exactly when it's needed.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s.length ≤ 20 - ◆
s contains non-negative integers (possibly multi-digit), the operators '+' and '-', and matched parentheses — no spaces, no '*' or '/' - ◆
A leading '-' before the whole expression or right after '(' is allowed (e.g. "-5+3") - ◆
The result always fits in a 32-bit signed integer
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursively Evaluate Inside Each Matched Pair
BruteScan left to right, accumulating digits into the current number and applying '+'/'-' against a running result as they're seen. Whenever '(' is reached, its matching ')' has to be located first — scan forward tracking bracket depth until it returns to zero — then recursively evaluate everything strictly between them as its own sub-expression, and fold that value into the running result with the sign that was pending. Locating the matching bracket costs O(distance to it), and that scan repeats at every level of nesting — O(n²) in the worst case, mirroring the same bracket-matching overhead seen in infix-to-postfix conversion.
O(n²)O(n)1class Solution {
2 public int calculate(String s) {
3 return calcHelper(s);
4 }
5
6 private int matchParen(String s, int openIdx) {
7 int depth = 0;
8 for (int i = openIdx; i < s.length(); i++) {
9 if (s.charAt(i) == '(') depth++;
10 else if (s.charAt(i) == ')') { depth--; if (depth == 0) return i; }
11 }
12 return -1;
13 }
14
15 private int calcHelper(String s) {
16 int result = 0, num = 0, sign = 1;
17 int i = 0;
18 while (i < s.length()) {
19 char c = s.charAt(i);
20 if (Character.isDigit(c)) {
21 num = num * 10 + (c - '0');
22 i++;
23 } else if (c == '+') {
24 result += sign * num; num = 0; sign = 1; i++;
25 } else if (c == '-') {
26 result += sign * num; num = 0; sign = -1; i++;
27 } else if (c == '(') {
28 int matchIdx = matchParen(s, i);
29 int innerVal = calcHelper(s.substring(i + 1, matchIdx));
30 result += sign * innerVal;
31 sign = 1;
32 i = matchIdx + 1;
33 }
34 }
35 result += sign * num;
36 return result;
37 }
38}Optimal — Single Pass With a Sign/Result Stack
OptimalWalk the string exactly once, never looking ahead. Digits build the current number; '+'/'-' fold it into the running result and set the pending sign. On '(', push the running result and the pending sign onto a stack, then reset both — a fresh sub-problem starts, with no need to know in advance where it ends. On ')', fold the current number in, then pop the sign and result that were saved before the '(' and combine them: multiply by the popped sign (undoing/applying it correctly) and add the popped result. The stack itself remembers exactly what to resume, eliminating the need to ever locate a matching bracket.
O(n)O(n)1class Solution {
2 public int calculate(String s) {
3 Deque<Integer> stack = new ArrayDeque<>();
4 int result = 0, num = 0, sign = 1;
5 for (int i = 0; i <= s.length(); i++) {
6 char c = i < s.length() ? s.charAt(i) : '\0';
7 if (Character.isDigit(c)) {
8 num = num * 10 + (c - '0');
9 } else if (c == '+') {
10 result += sign * num; num = 0; sign = 1;
11 } else if (c == '-') {
12 result += sign * num; num = 0; sign = -1;
13 } else if (c == '(') {
14 stack.push(result);
15 stack.push(sign);
16 result = 0;
17 sign = 1;
18 } else if (c == ')') {
19 result += sign * num;
20 num = 0;
21 result *= stack.pop();
22 result += stack.pop();
23 } else if (i == s.length()) {
24 result += sign * num;
25 }
26 }
27 return result;
28 }
29}