🥞 Stacks: Your Magical Plate Tower

The Story of the Pancake Stack

Imagine you’re at a breakfast buffet. The chef keeps adding fresh, hot pancakes to a pile. When you want one, you always take from the top — never from the middle or bottom!

This is exactly how a Stack works in programming. It’s a special container where:

• You add items on top (called push)
• You remove items from the top (called pop)
• You can only see the top item (called peek)

🎯 One Rule: Last In, First Out (LIFO) The last pancake added is the first one you eat!

Stack Fundamentals

What Makes a Stack Special?

Think of stacking your favorite books. You put one book on top of another. When you want a book, you take the one on top first.

// Creating a stack in JavaScript
const stack = [];

// Push: Add to top
stack.push("Book 1");
stack.push("Book 2");
stack.push("Book 3");
// Stack now: [Book1, Book2, Book3]
//                          ↑ top

// Pop: Remove from top
const topBook = stack.pop();
// topBook = "Book 3"
// Stack now: [Book1, Book2]

// Peek: Look at top (without removing)
const peekBook = stack[stack.length - 1];
// peekBook = "Book 2"

Key Operations

🔗 Balanced Parentheses

The Matching Game

Imagine you have a box of colored brackets: (), [], {}. Your job is to check if every opening bracket has its matching closing bracket — and in the right order!

Example:

• "([])" ✅ Valid — each opener finds its partner
• "([)]" ❌ Invalid — brackets crossed paths

How Stack Solves This

graph TD
    A["Read #40;"] --> B["Push #40; to stack"]
    B --> C["Read ["]
    C --> D["Push [ to stack"]
    D --> E["Read ]"]
    E --> F["Pop [ — Match!"]
    F --> G["Read #41;"]
    G --> H["Pop #40; — Match!"]
    H --> I["Stack empty = Valid!"]

The Code

function isBalanced(str) {
  const stack = [];
  const pairs = {
    ')': '(',
    ']': '[',
    '}': '{'
  };

  for (const char of str) {
    if (char === '(' ||
        char === '[' ||
        char === '{') {
      stack.push(char);
    }
    else if (pairs[char]) {
      if (stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

// Examples
isBalanced("()[]{}");  // true
isBalanced("([])");    // true
isBalanced("([)]");    // false
isBalanced("((");      // false

Why It Works

• Opening bracket? Push it on the stack
• Closing bracket? Pop and check if it matches
• End of string? Stack should be empty

📁 Simplify Path

The GPS Navigator Problem

You’re giving directions in a file system. People write messy paths like:

• "/home//user/../documents/./photos"

You need to clean it up to:

• "/home/documents/photos"

The Rules

Stack to the Rescue!

graph TD
    A["Split path by /"] --> B["For each part"]
    B --> C{What is it?}
    C -->|Empty or .| D["Skip it"]
    C -->|..| E["Pop stack"]
    C -->|folder name| F["Push to stack"]
    D --> B
    E --> B
    F --> B
    B --> G["Join with /"]

The Code

function simplifyPath(path) {
  const stack = [];
  const parts = path.split('/');

  for (const part of parts) {
    if (part === '' || part === '.') {
      continue; // Skip empty and current
    }
    else if (part === '..') {
      stack.pop(); // Go back one level
    }
    else {
      stack.push(part); // Add folder
    }
  }

  return '/' + stack.join('/');
}

// Examples
simplifyPath("/home/");
// → "/home"

simplifyPath("/../");
// → "/"

simplifyPath("/home//foo/");
// → "/home/foo"

simplifyPath("/a/./b/../../c/");
// → "/c"

🏆 Longest Valid Parentheses

The Treasure Hunt

Given a string of only ( and ), find the longest stretch where all parentheses are perfectly balanced.

Example:

• "(()" → Answer: 2 (the () at the end)
• ")()())" → Answer: 4 (the ()() in middle)

The Stack Strategy

We use the stack to store positions (indices), not the characters themselves!

graph TD
    A["Start: Push -1 as base"] --> B["Read each character"]
    B --> C{Is it #40; ?}
    C -->|Yes| D["Push its index"]
    C -->|No| E["Pop stack"]
    E --> F{Stack empty?}
    F -->|Yes| G["Push current index"]
    F -->|No| H["Calculate length"]
    H --> I["Update max length"]
    D --> B
    G --> B
    I --> B

The Code

function longestValidParens(s) {
  const stack = [-1]; // Base index
  let maxLen = 0;

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i);
    } else {
      stack.pop();

      if (stack.length === 0) {
        stack.push(i); // New base
      } else {
        const len = i - stack[stack.length - 1];
        maxLen = Math.max(maxLen, len);
      }
    }
  }

  return maxLen;
}

// Examples
longestValidParens("(()");    // 2
longestValidParens(")()())"); // 4
longestValidParens("()(()");  // 2

Why Push -1?

The -1 acts as a “floor” so when we calculate length, we always have something to subtract from!

🧹 Remove Invalid Parentheses

The Cleanup Crew

Given a string with letters and parentheses, remove the minimum number of invalid parentheses to make it valid.

Example:

• "()())()" → ["()()()", "(())()"]
• "(a)())()" → ["(a)()()", "(a())()"]

The Two-Pass Approach

graph TD
    A["Pass 1: Left to Right"] --> B["Remove extra #41;"]
    B --> C["Pass 2: Right to Left"]
    C --> D["Remove extra #40;"]
    D --> E["Collect all valid results"]

The Code

function removeInvalidParens(s) {
  const results = new Set();

  function remove(str, start,
                  open, close, rev) {
    let count = 0;

    for (let i = start; i < str.length; i++) {
      if (str[i] === open) count++;
      if (str[i] === close) count--;

      if (count < 0) {
        // Remove one close bracket
        for (let j = 0; j <= i; j++) {
          if (str[j] === close) {
            // Skip duplicates
            if (j === 0 ||
                str[j-1] !== close) {
              const newStr =
                str.slice(0, j) +
                str.slice(j + 1);
              remove(newStr, i,
                     open, close, rev);
            }
          }
        }
        return;
      }
    }

    // Reverse and check other direction
    const reversed = str.split('')
                        .reverse()
                        .join('');
    if (rev) {
      results.add(reversed);
    } else {
      remove(reversed, 0, ')', '(', true);
    }
  }

  remove(s, 0, '(', ')', false);
  return [...results];
}

Key Insight

• First pass: Fix extra ) by going left-to-right
• Second pass: Fix extra ( by reversing and repeating!

➕ Minimum Add to Make Valid

The Missing Pieces

Count how many parentheses you need to add to make a string valid.

Example:

• "())" → Add 1 ( at start
• "(((" → Add 3 ) at end
• "()))((" → Add 4 total

The Simple Counter Method

graph TD
    A["Two counters: open, close"] --> B["Read each char"]
    B --> C{Is it #40; ?}
    C -->|Yes| D["open++"]
    C -->|No| E{open > 0?}
    E -->|Yes| F["open-- #40;matched!#41;"]
    E -->|No| G["close++ #40;unmatched#41;"]
    D --> B
    F --> B
    G --> B
    B --> H["Answer = open + close"]

The Code

function minAddToMakeValid(s) {
  let open = 0;   // Unmatched (
  let close = 0;  // Unmatched )

  for (const char of s) {
    if (char === '(') {
      open++;
    }
    else if (char === ')') {
      if (open > 0) {
        open--; // Found a match!
      } else {
        close++; // No ( to match
      }
    }
  }

  return open + close;
}

// Examples
minAddToMakeValid("())");    // 1
minAddToMakeValid("(((");    // 3
minAddToMakeValid("()");     // 0
minAddToMakeValid("()))(("); // 4

Why It Works

• open tracks unmatched (
• close tracks unmatched )
• The sum is what we need to add!

🎯 Quick Summary

🚀 You Did It!

You now understand how stacks power some of the most common string problems in programming. Remember:

🥞 Stack = Pancake Tower Last pancake in, first pancake out!

Every time you see parentheses, brackets, or “undo” functionality — think Stack!