Stack Parsing

How to think about it

A stack holds open work: unmatched brackets, partial numbers, path segments, or live asteroids. Closing tokens reduce the top until the structure is consistent. The final stack (or empty) is the answer.

Template shapes

Shape	Core move	Notes
Matching	Push open; pop on close	Empty ⇒ valid
Nested decode	Push count and string	Expand on ‘]’
Collisions	Pop while top loses	Push survivor

Complexity baseline

Usually O(n) time and space in the depth or output size.

From template to problem

1. Define what a stack frame stores (char, number, string builder, direction).
2. Scan left to right; on each token either push or reduce.
3. Handle edge cases (empty, single token, leading signs).
4. Serialize the remaining stack into the result.

/** Stack parsing template: valid parentheses. */
export function isValid(s: string): boolean {
  const st: string[] = [];
  const pair: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") st.push(ch);
    else if (!st.length || st.pop() !== pair[ch]) return false;
  }
  return st.length === 0;
}

/** Stack parsing template: valid parentheses. */
export function isValid(s: string): boolean {
  const st: string[] = [];
  const pair: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") st.push(ch);
    else if (!st.length || st.pop() !== pair[ch]) return false;
  }
  return st.length === 0;
}