Stacks and Queues

Balanced Parentheses

Walk a string of bracket characters. Push every opening bracket. On a closing bracket, pop and verify it matches; mismatch or empty-stack pop means unbalanced. At end of string, stack must be empty.

Algorithm

Canonical input "({[]})" (balanced) finishes with the stack empty and the result true.

stack push/pop Use a plain `string[]` array (`push` / `pop`) as the stack.
matching map A small `Record<string, string>` mapping each closing bracket to its expected opener keeps the lesson compact.

Basic Implementation

basic.ts
Replay: real traced execution (multi-file project)
const text: string = "({[]})";
const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
const stack: string[] = [];
let balanced: boolean = true;
for (let i: number = 0; i < text.length; i++) {
    const ch: string = text[i];
    if (ch === "(" || ch === "[" || ch === "{") {
        stack.push(ch);
    } else {
        if (stack.length === 0 || stack[stack.length - 1] !== pairs[ch]) {
            balanced = false;
            break;
        }
        stack.pop();
    }
}
if (stack.length !== 0) {
    balanced = false;
}
console.log(balanced);

  1. text ← ({[]})

    1const text: string = "({[]})";2const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
    values this step({[]})text

  2. stack ← []

    2const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };3const stack: string[] = [];4let balanced: boolean = true;
    values this step[]stack

  3. balanced ← true

    3const stack: string[] = [];4let balanced: boolean = true;5for (let i: number = 0; i < text.length; i++) {
    values this steptruebalanced

  4. stack ← [(]

    5for (let i: number = 0; i < text.length; i++) {6    const ch: string = text[i];7    if (ch === "(" || ch === "[" || ch === "{") {
    values this step[(]stack(ch

  5. stack ← [(, {]

    5for (let i: number = 0; i < text.length; i++) {6    const ch: string = text[i];7    if (ch === "(" || ch === "[" || ch === "{") {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    5for (let i: number = 0; i < text.length; i++) {6    const ch: string = text[i];7    if (ch === "(" || ch === "[" || ch === "{") {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    5for (let i: number = 0; i < text.length; i++) {6    const ch: string = text[i];7    if (ch === "(" || ch === "[" || ch === "{") {
    values this step[(, {]stack]ch

  8. stack ← [(]

    5for (let i: number = 0; i < text.length; i++) {6    const ch: string = text[i];7    if (ch === "(" || ch === "[" || ch === "{") {
    values this step[(]stack}ch

  9. stack ← []

    5for (let i: number = 0; i < text.length; i++) {6    const ch: string = text[i];7    if (ch === "(" || ch === "[" || ch === "{") {
    values this step[]stack)ch

  10. balanced ← true, stdout ← true

    16}17if (stack.length !== 0) {18    balanced = false;
    values this steptruebalancedtruestdout[]stack

Complexity

  • Time: O(n)
  • Space: O(n) worst case

Implementation notes

  • TypeScript: a plain string[] array doubles as a stack via push and pop; avoid any external stack library.
  • The Record<string, string> annotation on pairs documents the closing -> opening map without leaking object identity.
  • The replay highlights the current character, shows the stack updating each frame, and surfaces the final balanced/unbalanced verdict.