Stack Computation

🥞 Stack Computation: The Magic Pancake Counter

Ever wonder how calculators solve complex math? Or how computers decode secret messages? Let’s discover the magic of Stack Computation!

🎯 What You’ll Master

Imagine you have a stack of pancakes. You can only add or remove pancakes from the TOP. This simple rule makes stacks incredibly powerful for solving tricky problems!

graph TD
    A["🥞 Pancake Stack"] --> B["Add to TOP only"]
    A --> C["Remove from TOP only"]
    B --> D["Last In, First Out"]
    C --> D

1️⃣ Min Stack: The Smart Pancake Counter

🤔 The Problem

You’re stacking pancakes and your friend keeps asking: “What’s the smallest pancake in the stack RIGHT NOW?”

Checking every pancake each time would be slow! Can we answer instantly?

💡 The Trick: Two Stacks!

Keep a helper stack that always tracks the smallest value seen so far.

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];  // Helper!
  }

  push(val) {
    this.stack.push(val);
    // Track minimum at this point
    const currentMin =
      this.minStack.length === 0
        ? val
        : Math.min(val, this.minStack.at(-1));
    this.minStack.push(currentMin);
  }

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

  getMin() {
    return this.minStack.at(-1);  // Instant!
  }
}

🎮 Example Walkthrough

Magic: We always know the minimum without searching! 🎩

2️⃣ Expression Parsing: Reading Math Like a Story

🤔 The Challenge

How does a computer understand 3 + 4 * 2? It doesn’t just read left-to-right like us!

💡 The Secret: Operator Priority

Think of it like a VIP line:

• × and ÷ are VIPs (go first)
• + and − wait their turn

graph TD
    A["3 + 4 * 2"] --> B["See: 3"]
    B --> C["See: +"]
    C --> D["See: 4"]
    D --> E["See: *"]
    E --> F["* is VIP! Calculate 4*2 first"]
    F --> G["Result: 3 + 8 = 11"]

🎯 Two Stacks Save the Day

function evaluate(expression) {
  const nums = [];
  const ops = [];

  const priority = {'+':1, '-':1, '*':2, '/':2};

  function applyOp() {
    const b = nums.pop();
    const a = nums.pop();
    const op = ops.pop();
    if (op === '+') nums.push(a + b);
    if (op === '-') nums.push(a - b);
    if (op === '*') nums.push(a * b);
    if (op === '/') nums.push(Math.trunc(a / b));
  }

  // Parse character by character...
  // Push numbers to nums stack
  // Handle operators based on priority

  return nums[0];
}

Key Insight: Before adding a new operator, compute any waiting VIPs first!

3️⃣ Basic Calculator: The Bracket Master

🤔 The Puzzle

2 * (3 + 4) — How do we handle brackets?

💡 Brackets Are Like Pause Buttons!

When you see (:

1. Save your current work
2. Start fresh inside brackets

When you see ):

1. Finish bracket calculation
2. Resume saved work

function calculate(s) {
  const stack = [];
  let num = 0;
  let result = 0;
  let sign = 1;

  for (const char of s) {
    if (char >= '0' && char <= '9') {
      num = num * 10 + Number(char);
    } else if (char === '+') {
      result += sign * num;
      num = 0;
      sign = 1;
    } else if (char === '-') {
      result += sign * num;
      num = 0;
      sign = -1;
    } else if (char === '(') {
      // SAVE current state
      stack.push(result);
      stack.push(sign);
      result = 0;
      sign = 1;
    } else if (char === ')') {
      result += sign * num;
      num = 0;
      // RESTORE saved state
      result *= stack.pop();  // sign
      result += stack.pop();  // previous result
    }
  }

  return result + sign * num;
}

🎮 Example: 1 + (2 - 3)

4️⃣ Decode String: The Secret Message Unlocker

🤔 The Mystery

3[ab2[c]] means “repeat ab2[c] three times”… but what’s inside?

💡 Work from Inside Out!

Like Russian nesting dolls 🪆 — open the innermost first!

graph TD
    A["3[ab2[c]]"] --> B["Find innermost: 2[c]"]
    B --> C["Decode: cc"]
    C --> D["Now have: 3[abcc]"]
    D --> E["Decode: abccabccabcc"]

🎯 The Stack Solution

function decodeString(s) {
  const countStack = [];
  const stringStack = [];
  let currentStr = '';
  let k = 0;

  for (const char of s) {
    if (char >= '0' && char <= '9') {
      k = k * 10 + Number(char);
    } else if (char === '[') {
      // SAVE current progress
      countStack.push(k);
      stringStack.push(currentStr);
      currentStr = '';
      k = 0;
    } else if (char === ']') {
      // DECODE and combine
      const count = countStack.pop();
      const prevStr = stringStack.pop();
      currentStr = prevStr +
        currentStr.repeat(count);
    } else {
      currentStr += char;
    }
  }

  return currentStr;
}

🎮 Walkthrough: 2[a3[b]]

5️⃣ Asteroid Collision: The Space Battle

🤔 The Scenario

Asteroids fly in a line. Positive = right →, Negative = left ←

When they collide:

• Bigger one survives
• Same size? Both explode! 💥

💡 Think Like a Space Traffic Controller

Process asteroids left to right. Use a stack to track survivors!

function asteroidCollision(asteroids) {
  const stack = [];

  for (const ast of asteroids) {
    let destroyed = false;

    // Collision: top going right, current going left
    while (
      stack.length > 0 &&
      stack.at(-1) > 0 &&
      ast < 0
    ) {
      const top = stack.at(-1);

      if (top < Math.abs(ast)) {
        stack.pop();  // Top destroyed
      } else if (top === Math.abs(ast)) {
        stack.pop();  // Both destroyed
        destroyed = true;
        break;
      } else {
        destroyed = true;  // Current destroyed
        break;
      }
    }

    if (!destroyed) {
      stack.push(ast);
    }
  }

  return stack;
}

🎮 Battle Simulation: [5, 10, -5]

Result: [5, 10] — The small asteroid was destroyed!

6️⃣ Remove K Digits: Make the Smallest Number

🤔 The Challenge

Given "1432219" and k=3, remove 3 digits to make the smallest number.

💡 The Greedy Stack Strategy

Scan left to right. If a digit is bigger than the next one, it’s a good candidate to remove!

graph TD
    A["1432219, remove 3"] --> B["1 < 4: keep 1"]
    B --> C["4 > 3: remove 4"]
    C --> D["3 > 2: remove 3"]
    D --> E["2 > 1: remove 2"]
    E --> F["Result: 1219"]

🎯 The Stack Solution

function removeKdigits(num, k) {
  const stack = [];

  for (const digit of num) {
    // Remove larger digits from stack
    while (
      k > 0 &&
      stack.length > 0 &&
      stack.at(-1) > digit
    ) {
      stack.pop();
      k--;
    }
    stack.push(digit);
  }

  // Remove remaining from end
  while (k > 0) {
    stack.pop();
    k--;
  }

  // Remove leading zeros
  const result = stack.join('')
    .replace(/^0+/, '');

  return result || '0';
}

🎮 Example: "1432219", k=3

Result: "1219" ✨

🎊 You Did It!

You’ve mastered the six superpowers of Stack Computation:

graph LR
    A["🥞 Stack"] --> B["Min Stack"]
    A --> C["Calculators"]
    A --> D["String Decoding"]
    A --> E["Simulations"]
    A --> F["Optimization"]

    B --> G["✨ O#40;1#41; minimum"]
    C --> H["✨ Handle any expression"]
    D --> I["✨ Nested patterns"]
    E --> J["✨ Collision detection"]
    F --> K["✨ Greedy removal"]

Remember: Stacks are simple (Last In, First Out), but combined with clever thinking, they solve incredibly complex problems!

🚀 Now go stack up your skills!