Stack Computation

🥞 Stack Computation: The Magical Pancake Machine

Imagine a pancake machine that can do math, decode secret messages, and even survive asteroid battles!

The Big Idea: What’s a Stack?

Think of a stack of pancakes on a plate.

• You can only add a new pancake on top
• You can only take a pancake from the top
• The last pancake you put on is the first one you take off

This is called LIFO = Last In, First Out

Stack<Integer> pancakes = new Stack<>();
pancakes.push(1);  // Add pancake
pancakes.pop();    // Remove top pancake
pancakes.peek();   // Look at top (don't remove)

1. 🏆 Min Stack: The Smartest Pancake Stack

The Story

Imagine you have a stack of numbered pancakes. Your friend keeps asking: “What’s the SMALLEST number in your stack right now?”

Without a special trick, you’d have to look through ALL pancakes every time. That’s slow! 😩

The Magic Trick

Keep TWO stacks!

• One stack holds your numbers (normal stack)
• One stack tracks the minimum at each level (min stack)

graph TD
    A["Push 5"] --> B["Stack: 5<br>Min: 5"]
    B --> C["Push 2"]
    C --> D["Stack: 5,2<br>Min: 5,2"]
    D --> E["Push 7"]
    E --> F["Stack: 5,2,7<br>Min: 5,2,2"]

Simple Example

The Code

class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    void push(int val) {
        stack.push(val);
        int min = minStack.isEmpty()
            ? val
            : Math.min(val, minStack.peek());
        minStack.push(min);
    }

    void pop() {
        stack.pop();
        minStack.pop();
    }

    int getMin() {
        return minStack.peek();
    }
}

Why it works: Every time you add a number, you also remember the smallest number up to that point. When you remove, both stacks shrink together!

2. ➕ Expression Parsing & Evaluation

The Story

Imagine you’re a calculator robot reading: 3 + 5 * 2

Do you do 3 + 5 = 8, then 8 * 2 = 16? NO!

Math rules say: multiply first! So it’s 5 * 2 = 10, then 3 + 10 = 13

How do you handle this? Use TWO stacks!

• One for numbers
• One for operators

The Rules

1. See a number? Push it to number stack
2. See an operator? Check if previous operator is “stronger”
3. If yes, calculate first, then push new operator
4. At the end, calculate everything left

graph TD
    A["Read: 3 + 5 * 2"] --> B["Push 3"]
    B --> C["Push +"]
    C --> D["Push 5"]
    D --> E["Push * #40;stronger than +#41;"]
    E --> F["Push 2"]
    F --> G["End: Calculate * first"]
    G --> H["5 * 2 = 10"]
    H --> I["3 + 10 = 13"]

Operator Strength (Precedence)

Simple Example: 2 + 3 * 4

3. 🧮 Basic Calculator

The Story

Now your calculator robot sees: (2 + 3) * 4

Those brackets change everything! Inside brackets comes first!

Think of brackets like a save point in a video game:

1. See ( → Save your current work
2. Calculate inside the brackets
3. See ) → Load your save, combine the results

How It Works

When you see (:

• Push current result to stack
• Push current sign to stack
• Start fresh!

When you see ):

• Pop the sign
• Pop the old result
• Combine: old_result + sign * current_result

Example: (1 + 2) * 3

graph TD
    A["Start: result=0, sign=+"] --> B["See #40; → Save 0 and +"]
    B --> C["Inside: 1 + 2 = 3"]
    C --> D["See #41; → Load: 0 + #40;+1#41;*3 = 3"]
    D --> E["See * and 3"]
    E --> F["Result = 9"]

The Code Pattern

int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    int result = 0, number = 0, sign = 1;

    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            number = number * 10 + (c - '0');
        } else if (c == '+') {
            result += sign * number;
            number = 0;
            sign = 1;
        } else if (c == '-') {
            result += sign * number;
            number = 0;
            sign = -1;
        } else if (c == '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } else if (c == ')') {
            result += sign * number;
            number = 0;
            result *= stack.pop(); // sign
            result += stack.pop(); // prev result
        }
    }
    return result + sign * number;
}

4. 🔐 Decode String

The Story

Your friend sends you a secret code: 3[ab]2[c]

This means: “ab ab ab c c” or “abababcc”

It’s like a copy machine:

• 3[ab] = copy “ab” three times
• 2[c] = copy “c” two times

The Tricky Part: Nested Codes!

What about 2[a3[b]]?

Read it like this:

1. First, decode inside: 3[b] = “bbb”
2. Now you have: 2[abbb]
3. Copy “abbb” twice = “abbbbbb”

How Stack Helps

When you see [:

• Save your current string
• Save the repeat number
• Start fresh!

When you see ]:

• Pop the number
• Pop the old string
• Combine: old_string + current_string × number

graph TD
    A["Read: 2[a3[b]]"] --> B["See 2[ → Save '' and 2"]
    B --> C["Build 'a'"]
    C --> D["See 3[ → Save 'a' and 3"]
    D --> E["Build 'b'"]
    E --> F["See ] → 'a' + 'b'×3 = 'abbb'"]
    F --> G["See ] → '' + 'abbb'×2"]
    G --> H["Result: 'abbbabbb'"]

Example: 3[a2[c]]

Result: “accaccacc”

5. 💥 Asteroid Collision

The Story

Asteroids are flying in space!

• Positive numbers (like 5) fly right →
• Negative numbers (like -3) fly left ←

When they crash:

• Bigger one survives
• Same size? Both explode!
• Same direction? They never meet!

The Rules

How to Solve

Use a stack! Each asteroid goes on the stack. But before adding a new one, check for collisions.

graph TD
    A["Asteroids: [5, 10, -5]"] --> B["Push 5 →"]
    B --> C["Push 10 →"]
    C --> D["See -5 ← #40;collision!#41;"]
    D --> E["10 vs -5: 10 wins"]
    E --> F["Result: [5, 10]"]

Example: [8, -8]

Result: [] (empty!)

Example: [5, 10, -5]

Result: [5, 10]

6. ✂️ Remove K Digits

The Story

You have a number like 1432219 and you want to remove 2 digits to make the smallest possible number.

Think of it like this: you’re building a number, and you want the smallest digits at the front.

The Magic Rule

If a digit is BIGGER than the next one, remove it!

Why? Because 14... is bigger than 12...

So in 1432219, we look:

• 1 < 4 ✓ (keep 1)
• 4 > 3 ❌ (remove 4!)
• 3 > 2 ❌ (remove 3!)
• Now we’ve removed 2 digits!

graph TD
    A["1432219, remove 2"] --> B["1 < 4, push 1"]
    B --> C["4 > 3, pop 4, push 3"]
    C --> D["3 > 2, pop 3, push 2"]
    D --> E["Used 2 removes!"]
    E --> F["Push remaining: 2, 1, 9"]
    F --> G["Result: 12219"]

Example: num = "1432219", k = 3

Result: "1219"

Edge Cases

• Result has leading zeros? Remove them!
• "10" with k=1 → Remove 1 → "0" (not “”)
• Removed everything? Return "0"

🎯 The Stack Superpower Summary

💡 Remember This!

Stack = Memory with UNDO

• Push = Remember something
• Pop = Go back / Undo
• Peek = Check what’s saved

Every problem here uses the stack to remember and go back when needed. That’s the superpower!

Now you’re ready to tackle any stack computation problem! Remember: when you need to track history or undo things, think STACK! 🥞