Basic Calculator - Stack Parsing Walkthrough

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

You are given a string s representing a valid expression. The expression can include non-negative integers, plus and minus operators, nested parentheses, and spaces.

Evaluate and return the final integer result.

Examples

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 spaces
s represents a valid expression
No use of built-in eval in interviews

🎯 Real-World Analogy

Receipt Subtotals with Nested Discounts

Imagine you are calculating a long shopping receipt. You keep a running subtotal. When you hit parentheses, think of them as "temporary mini-receipts" that must be completed before returning to the main total.

To handle that, you save your current subtotal and sign on a stack, work inside the parentheses, then fold the inner result back into the previous subtotal.

This maps directly to stack parsing: save context at (, restore and combine at ).

💡 Key Insights

Only + and - are present, so precedence is managed by parentheses context.
Keep three running states: total, num, and sign.
At every operator, flush the previous number into total.
On (, push the current total and sign to stack; reset inner context.
On ), close inner expression, then merge it into outer context from stack.

💻 Solution Approaches

Approach 1: Use Built-In Evaluator (Not Interview Safe)

Time: O(N) | Space: O(N)

Some languages let you call eval. It works but is unsafe, not accepted in most interviews, and does not demonstrate parsing fundamentals.

Approach 2: Stack-Based Single Pass (Recommended)

Time: O(N) | Space: O(N)

Parse left to right once, using a stack to save context around parentheses.

Python Implementation

          def calculate(s: str) -> int:
    """
    Evaluate expression with +, -, parentheses, and spaces.

    Time: O(N)
    Space: O(N)
    """
    total = 0
    num = 0
    sign = 1
    stack = []

    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in "+-":
            total += sign * num
            num = 0
            sign = 1 if ch == "+" else -1
        elif ch == "(":
            stack.append(total)
            stack.append(sign)
            total = 0
            sign = 1
        elif ch == ")":
            total += sign * num
            num = 0
            prev_sign = stack.pop()
            prev_total = stack.pop()
            total = prev_total + prev_sign * total
        # ignore spaces

    return total + sign * num
        

JavaScript Implementation

          function calculate(s) {
  /**
   * Evaluate expression with +, -, parentheses, and spaces.
   *
   * Time: O(N)
   * Space: O(N)
   */
  let total = 0;
  let num = 0;
  let sign = 1;
  const stack = [];

  for (const ch of s) {
    if (ch >= "0" && ch <= "9") {
      num = num * 10 + Number(ch);
    } else if (ch === "+" || ch === "-") {
      total += sign * num;
      num = 0;
      sign = ch === "+" ? 1 : -1;
    } else if (ch === "(") {
      stack.push(total);
      stack.push(sign);
      total = 0;
      sign = 1;
    } else if (ch === ")") {
      total += sign * num;
      num = 0;
      const prevSign = stack.pop();
      const prevTotal = stack.pop();
      total = prevTotal + prevSign * total;
    }
    // ignore spaces
  }

  return total + sign * num;
}
        

🔍 Step-by-Step Walkthrough

Trace s = "1 + (2 - (3 + 4)) + 5":

Start: total=0, num=0, sign=+1, stack=[]

            Read 1 then +: total = 0 + 1*1 = 1

            sign becomes +1
          
            Read (: push current context [1, +1], reset total/sign

            stack = [1, +1], inner total = 0
          
            Read 2 then -: inner total = 2, sign = -1
          
            Read nested (: push [2, -1], reset inner total/sign
          
            Read 3 + 4 then ): nested total = 7

            pop [2, -1] ⇒ total = 2 + (-1 * 7) = -5
          
            Read ) for first group: pop [1, +1] ⇒ total = 1 + (+1 * -5) = -4
          
            Read +5 and finish: result = -4 + 5 = 1

⚡ Complexity Analysis

Time Complexity: O(N)

Each character is processed once. Every push has one matching pop.

Space Complexity: O(N)

In the worst case, deeply nested parentheses store O(N) context frames on stack.

🔧 Edge Cases

Expressions with leading/trailing spaces
Single number input: "42"
Nested negatives: "1-(2-(3-(4)))"
Large multi-digit numbers: "12345-(678+90)"
Parentheses at beginning: "(7)-(3)"

🧪 Test Cases

Python

          def test_calculate():
    assert calculate("1 + 1") == 2
    assert calculate(" 2-1 + 2 ") == 3
    assert calculate("(1+(4+5+2)-3)+(6+8)") == 23
    assert calculate("42") == 42
    assert calculate("1-(2-(3-(4)))") == -2
    assert calculate("12345-(678+90)") == 11577

    print("✅ all tests passed")
        

JavaScript

          function testCalculate() {
  console.assert(calculate("1 + 1") === 2, "test 1");
  console.assert(calculate(" 2-1 + 2 ") === 3, "test 2");
  console.assert(calculate("(1+(4+5+2)-3)+(6+8)") === 23, "test 3");
  console.assert(calculate("42") === 42, "test 4");
  console.assert(calculate("1-(2-(3-(4)))") === -2, "test 5");
  console.assert(calculate("12345-(678+90)") === 11577, "test 6");

  console.log("✅ all tests passed");
}
        

💼 Interview Tips

Explain why eval is rejected and parsing is expected.
Call out the exact state variables: total, num, sign, stack.
State stack contract clearly: push outer context at (, merge at ).
Show how you handle spaces and multi-digit numbers.
Mention extension path for * and / (would require precedence handling).

🎓 Key Takeaways

Parentheses create nested evaluation contexts; stack is the right abstraction.
Flush numbers on operators and parentheses boundaries to avoid stale state.
This pattern generalizes to expression parsing and compiler-style token evaluation.

← Back to All Algorithms