Skip to content

113. Basic Calculator

🔗 LeetCode Problem: 224. Basic Calculator
📊 Difficulty: Hard
🏷️ Topics: Stack, String, Math

Problem Statement

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 * 10^5 - s consists of digits, '+', '-', '(', ')', and ' '. - s represents a valid expression.

🌟 Understanding the Problem First

Let's start with what we're trying to do.

The Simple Case - No Parentheses

"1 + 2 - 3"

Reading left to right:
  Start with 0
  See 1 → add it → 0 + 1 = 1
  See + → ok, continue
  See 2 → add it → 1 + 2 = 3
  See - → ok, continue
  See 3 → subtract it → 3 - 3 = 0

Result: 0

This is just addition and subtraction!

The Hard Case - With Parentheses

"5 - (3 + 2)"

What does this mean?
  First: Calculate what's inside ()
  (3 + 2) = 5

  Then: Use that result
  5 - 5 = 0

The parentheses create a "mini calculation" that we do first.

💡 The Core Challenge

How do we handle parentheses?

"5 - (3 + 2)"
 ↑   └─────┘
 │     │
outer  inner

Problem:
  When we see '(', we need to:
  1. PAUSE the outer calculation "5 -"
  2. START a new inner calculation "3 + 2"
  3. When we see ')', RESUME outer and use inner result

How to PAUSE and RESUME? 🤔

🎯 Building the Intuition

Insight 1: We Only Add and Subtract

Even subtraction can be thought of as adding a negative number!

"5 - 3" is the same as "5 + (-3)"

So our calculation is really just:
  result = result + number1
  result = result + number2
  result = result + number3
  ...

Where numbers can be positive or negative!

Insight 2: Track "What to Do Next"

When we see an operator, we need to remember it for the NEXT number.

"5 - 3"

See '5': We have the number 5
See '-': Remember "the next number should be SUBTRACTED"
See '3': Apply what we remembered: 5 - 3 = 2

We need a variable to "remember" the operation!

Insight 3: Parentheses Create Nested Calculations

Think of parentheses like a Russian doll:

Outer calculation: 5 - ???
  ↓
  Inner calculation: 3 + 2 = 5
  ↓
Back to outer: 5 - 5 = 0

We need to:
  - Save the outer state before entering inner
  - Calculate inner completely
  - Come back and finish outer

This is EXACTLY what a stack does!

🎨 The Three Variables We Need

Let me explain each variable and WHY we need it.

Variable 1: result

int result = 0;

This tracks our RUNNING SUM.

Example: "1 + 2 - 3"

After '1': result = 1
After '2': result = 3
After '3': result = 0

Simple! This is just our running total.

Variable 2: number

int number = 0;

This builds multi-digit numbers.

Why needed?
  "12 + 3"

  Can't process '1' immediately (it's part of 12!)
  '1': number = 1
  '2': number = 12  (1 × 10 + 2)
  '+': NOW use 12

We accumulate digits until we hit an operator.

Variable 3: sign

This is the CONFUSING one. Let me explain clearly.

int sign = 1;

This is NOT the sign of the result!
This tells us: "How should I use the next number?"

sign = 1  means: ADD the next number
sign = -1 means: SUBTRACT the next number

Example: "5 - 3"

See '5': number = 5
See '-': 
  First, use current number: result = 0 + 1×5 = 5
  Then, remember for next: sign = -1
See '3': number = 3
End:
  Use current number with remembered operation:
  result = 5 + (-1)×3 = 5 - 3 = 2 ✓

Why use sign × number?

Instead of writing:
  if (lastOperator == '+')
    result = result + number;
  else if (lastOperator == '-')
    result = result - number;

We write ONE line:
  result = result + sign × number;

When sign = 1:  result + 1×number = result + number ✓
When sign = -1: result + (-1)×number = result - number ✓

🎯 Handling Parentheses - The Key Insight

What Happens at '('?

"5 - (3 + 2)"
     ↑
   Here!

Before '(':
  result = 5
  sign = -1  (because we just saw '-')

What these mean:
  result = 5       → "We have calculated 5 so far"
  sign = -1        → "We're going to SUBTRACT what's in ()"

When we see '(':
  We need to SAVE these two values!
  Why? Because we'll need them when we see ')'!

What Do We Save on the Stack?

Two numbers:

1. result (what we calculated so far)
2. sign (what we'll do with the inner result)

Example: "5 - (3 + 2)"

At '(':
  stack.push(5)    // Save result
  stack.push(-1)   // Save sign

Why save BOTH?
  result tells us: "We had 5"
  sign tells us: "We'll SUBTRACT the inner result"

Then we reset:
  result = 0
  sign = 1

And start calculating inside () from scratch!

What Happens at ')'?

We've been calculating inside ().
Now we're done and need to go back to outer calculation.

Example: "5 - (3 + 2)"
            └─────┘
After calculating inside: result = 5 (from 3+2)

At ')':
  1. Get back saved values:
     savedSign = stack.pop() = -1
     savedResult = stack.pop() = 5

  2. Combine inner result with outer:
     result = savedResult + savedSign × result
     result = 5 + (-1) × 5
     result = 5 - 5 = 0 ✓

The formula applies the inner result to the outer calculation!

🔍 Complete Example Walkthrough

Let me trace "5 - (3 + 2)" in detail, focusing on intuition.

═══════════════════════════════════════════════════════════════
Initial State
═══════════════════════════════════════════════════════════════

stack = []
result = 0       // Running sum
number = 0       // Current number being built
sign = 1         // How to use next number (start with +)

═══════════════════════════════════════════════════════════════
Character: '5'
═══════════════════════════════════════════════════════════════

It's a digit!
Build the number: number = 5

State:
  result = 0
  number = 5
  sign = 1

Meaning: "We're building the number 5"

═══════════════════════════════════════════════════════════════
Character: ' ' (space)
═══════════════════════════════════════════════════════════════

Skip it.

═══════════════════════════════════════════════════════════════
Character: '-'
═══════════════════════════════════════════════════════════════

It's an operator!

Step 1: Process the number we built (5)
  result = result + sign × number
  result = 0 + 1 × 5 = 5

  Now result = 5 ✓

Step 2: Reset number for next one
  number = 0

Step 3: Remember operation for NEXT number
  sign = -1  (next number will be subtracted)

State:
  result = 5       // We have 5
  number = 0
  sign = -1        // Next number will be subtracted
  stack = []

Meaning:
  "We have 5 so far"
  "The next number we see should be SUBTRACTED"

Think of it as: "5 - ???" (waiting for next number)

═══════════════════════════════════════════════════════════════
Character: ' ' (space)
═══════════════════════════════════════════════════════════════

Skip it.

═══════════════════════════════════════════════════════════════
Character: '('
═══════════════════════════════════════════════════════════════

Opening parenthesis!

This is KEY! We're entering a nested calculation.

Current state before '(':
  result = 5       // What we calculated
  sign = -1        // What we'll do with inner result

Step 1: SAVE these to stack
  stack.push(result)  → push 5
  stack.push(sign)    → push -1

  stack = [5, -1]

Why save both?
  - We'll need result (5) to continue outer calculation
  - We'll need sign (-1) to know we're SUBTRACTING inner result

Step 2: RESET for inner calculation
  result = 0
  sign = 1

State:
  stack = [5, -1]  // Saved outer state
  result = 0       // Fresh start inside ()
  number = 0
  sign = 1         // Default to addition

Meaning:
  "Paused outer: We had 5, we'll subtract what's inside"
  "Starting inner: Clean slate, calculating from 0"

Visual:
  Outer: 5 - ???  (PAUSED, saved on stack)
  Inner: 0        (STARTING NOW)

═══════════════════════════════════════════════════════════════
Character: '3'
═══════════════════════════════════════════════════════════════

It's a digit!
Build the number: number = 3

State:
  stack = [5, -1]
  result = 0
  number = 3
  sign = 1

Meaning: "Inside (), building number 3"

═══════════════════════════════════════════════════════════════
Character: ' ' (space)
═══════════════════════════════════════════════════════════════

Skip it.

═══════════════════════════════════════════════════════════════
Character: '+'
═══════════════════════════════════════════════════════════════

It's an operator!

Step 1: Process number (3)
  result = result + sign × number
  result = 0 + 1 × 3 = 3

Step 2: Reset number
  number = 0

Step 3: Remember operation for next
  sign = 1  (next will be added)

State:
  stack = [5, -1]
  result = 3       // Inside (), we have 3
  number = 0
  sign = 1         // Next will be added

Meaning: "Inside (), we have 3 so far, will add next number"

═══════════════════════════════════════════════════════════════
Character: ' ' (space)
═══════════════════════════════════════════════════════════════

Skip it.

═══════════════════════════════════════════════════════════════
Character: '2'
═══════════════════════════════════════════════════════════════

It's a digit!
Build the number: number = 2

State:
  stack = [5, -1]
  result = 3
  number = 2
  sign = 1

Meaning: "Inside (), building number 2"

═══════════════════════════════════════════════════════════════
Character: ')'
═══════════════════════════════════════════════════════════════

Closing parenthesis! This is THE KEY MOMENT!

Step 1: Finish the inner calculation
  result = result + sign × number
  result = 3 + 1 × 2 = 5

  Inner calculation complete: (3 + 2) = 5 ✓

Step 2: Reset number
  number = 0

Step 3: Get back saved values from stack
  savedSign = stack.pop() = -1
  savedResult = stack.pop() = 5

  stack = []

What we got back:
  savedResult = 5    // This was our outer result
  savedSign = -1     // This says SUBTRACT inner from outer

Step 4: Apply inner result to outer
  result = savedResult + savedSign × result
  result = 5 + (-1) × 5
  result = 5 - 5
  result = 0 ✓

Let me break down this formula:
  savedResult = 5         // What we had before (
  savedSign = -1          // Operation to apply (subtract)
  result = 5              // Inner calculation result

  Formula combines them:
    5 + (-1) × 5
  = 5 - 5
  = 0

In plain English:
  "We HAD 5 in outer calculation"
  "We SUBTRACT the inner result (which is 5)"
  "5 - 5 = 0"

State:
  stack = []       // Back to outer level
  result = 0       // Final answer!
  number = 0
  sign = -1        // (leftover, not used)

Meaning:
  "Finished inner: (3 + 2) = 5"
  "Applied to outer: 5 - 5 = 0"
  "We're done!"

═══════════════════════════════════════════════════════════════
End of String
═══════════════════════════════════════════════════════════════

Check if any number left:
  result = result + sign × number
  result = 0 + (-1) × 0 = 0

(No remaining number)

═══════════════════════════════════════════════════════════════
FINAL ANSWER: 0 ✓
═══════════════════════════════════════════════════════════════

Verification: 5 - (3 + 2) = 5 - 5 = 0 ✓

🎯 Understanding the Key Formula

At ')': result = savedResult + savedSign × result

This is the MOST IMPORTANT line. Let me explain it clearly.

What each piece means:

savedResult:  What we had BEFORE entering (
savedSign:    How to apply inner result (+1 or -1)
result:       What we calculated INSIDE ()

The formula: savedResult + savedSign × result

Example 1: "5 - (3 + 2)"

Before '(':  savedResult=5, savedSign=-1
Inside '()': result = 5 (from 3+2)

Apply:
  5 + (-1) × 5
= 5 - 5
= 0 ✓

Translation: "We had 5, subtract inner result 5, get 0"

Example 2: "5 + (3 + 2)"

Before '(':  savedResult=5, savedSign=+1
Inside '()': result = 5 (from 3+2)

Apply:
  5 + (+1) × 5
= 5 + 5
= 10 ✓

Translation: "We had 5, add inner result 5, get 10"

Example 3: "-(3 + 2)"

Before '(':  savedResult=0, savedSign=-1
Inside '()': result = 5 (from 3+2)

Apply:
  0 + (-1) × 5
= 0 - 5
= -5 ✓

Translation: "We had 0, subtract inner result 5, get -5"

The formula does exactly what you'd do manually!

💻 The Complete Algorithm

Now that we understand the intuition, here's the code:

import java.util.Stack;

class Solution {
  public int calculate(String s) {
    // This is similar to decode string problem.
    Stack<int[]> stack = new Stack<>();
    int res = 0; // overall result
    // Purpose is to decide what to do next number with earlier number.
    int sign = 1; // by default. Or it can be -1. 
    int k = 0; // to handle double digit numbers
    for(char ch : s.toCharArray()) {
      if(Character.isDigit(ch)) {
        k = (k * 10) + (ch - '0');
      } else if (ch == '+') {
        res = res + (sign * k); // accumulate whatever is there before moving to next number
        sign = 1;        
        k = 0;
      } else if (ch == '-') {
        res = res + (sign * k); // accumulate whatever is there before moving to next number
        sign = -1;
        k = 0;
      } else if (ch == '(') {
        // push the existing state before entering the new context.
        stack.push(new int[] {res, sign});
        // once saved the existing context, reset the values to build for the next context.
        sign = 1;
        res = 0;
      } else if (ch == ')') {
        res = res + (sign * k); // finish whatever we have till now
        k = 0;
        // in case of 5 - (3 + 2), 
        // popped: [5, -1]
        int[] popped = stack.pop();
        int savedResult = popped[0];
        int savedSign = popped[1];
        res = savedResult + (savedSign * res);         
      } else if (ch == ' ') {
        continue;
      }
    }

    res = res + (sign * k); // if the input string does not end with ). For example, 1 + 2

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.calculate("1 + 1") == 2);
    System.out.println(s.calculate("2-1 + 2") == 3);
    System.out.println(s.calculate("(1+(4+5+2)-3)+(6+8)") == 23);
  }
}

Time: O(n) - Single pass
Space: O(d) where d = max nesting depth

🎯 Why This Works - Summary

The Three Variables:

  1. result = Running sum (what we've calculated)
  2. number = Current number being built (for multi-digit)
  3. sign = How to use next number (+1 for add, -1 for subtract)

The Stack Role:

  • Saves outer state when entering '('
  • Stack stores TWO values: [result, sign]
  • When we see ')', we restore and combine

The Key Operation:

result += sign × number

This ONE line handles both addition and subtraction!

The Key Formula at ')':

result = savedResult + savedSign × result

Combines outer and inner calculations!

⚠️ Common Mistakes

Mistake 1: Not processing number before operator

// ❌ WRONG
if (ch == '+') {
    sign = 1;  // Forgot to add number first!
}

// ✓ CORRECT
if (ch == '+') {
    result += sign * number;  // Process number first
    number = 0;
    sign = 1;
}

Mistake 2: Forgetting final number

// ❌ WRONG
return result;  // Last number not added!

// ✓ CORRECT
result += sign * number;  // Add last number
return result;

Mistake 3: Wrong pop order

// ❌ WRONG (reversed!)
int savedResult = stack.pop();
int savedSign = stack.pop();

// ✓ CORRECT (reverse of push order)
int savedSign = stack.pop();    // Last in
int savedResult = stack.pop();  // First in

Mistake 4: Not resetting after '('

// ❌ WRONG
stack.push(result);
stack.push(sign);
// Forgot to reset!

// ✓ CORRECT
stack.push(result);
stack.push(sign);
result = 0;  // Reset
sign = 1;    // Reset

🎯 The Core Intuition - Final Check

Ask yourself these questions:

  1. What does result track? → Running sum of our calculation

  2. What does number do? → Builds multi-digit numbers (12 = 1×10 + 2)

  3. What does sign mean? → How to use the NEXT number (+1 add, -1 subtract)

  4. Why save to stack at '('? → To remember outer state while calculating inner

  5. What does the formula at ')' do? → Combines outer result with inner result

  6. Why result + sign × number? → One formula for both addition and subtraction

If you can answer these, you understand it! 🎉

📝 Quick Revision

Variables: - result: running sum - number: current number (multi-digit) - sign: +1 or -1 (add or subtract next)

At operator (+/-): - Process: result += sign × number - Reset: number = 0 - Update: sign = new operation

At '(': - Save: [result, sign] to stack - Reset: result=0, sign=1

At ')': - Finish: result += sign × number - Restore: pop sign, pop result - Combine: result = savedResult + savedSign × result

End: - Add: result += sign × number

🎉 You've Got It!

The key insights:

  1. Everything is addition (subtraction = add negative)
  2. sign remembers operation for next number
  3. Stack saves state at '(' for later
  4. Formula combines inner with outer at ')'

This is genuinely a hard problem, but once you understand: - Why we use sign × number - What we save on stack - How the formula works

It becomes clear! 🎯

Happy practicing! 💪✨

Note: Don't memorize the code - understand WHY each part exists. The intuition is: pause outer calculation, do inner calculation, then combine them. The stack makes this possible!