Stacks and Queues

Balanced Parentheses

Scan a string of brackets left to right; push each opener and pop on each matching closer. The string is balanced when the scan ends with an empty stack and no mismatch ever fired.

Algorithm

Canonical input ({[]}) walks six characters and finishes with an empty stack; the printed result is True.

push on open Each of `(`, `[`, `{` is pushed onto the stack as the scan visits it.
pop on match Each closer must match the stack's top opener. A mismatch (or an empty stack on a closer) flips the balanced flag to false; trailing openers left on the stack at end of input do the same.

Basic Implementation

basic.sql
Replay: real traced execution (multi-file project)
.mode list
.headers off
CREATE TABLE chars(pos INTEGER PRIMARY KEY, ch TEXT);
INSERT INTO chars(pos, ch) VALUES
  (0, '('), (1, '{'), (2, '['), (3, ']'), (4, '}'), (5, ')');

WITH RECURSIVE scan(pos, stack, ok) AS (
  SELECT 0, '', 1
  UNION ALL
  SELECT scan.pos + 1,
    CASE
      WHEN c.ch IN ('(', '[', '{') THEN scan.stack || c.ch
      WHEN c.ch = ')' AND substr(scan.stack, length(scan.stack), 1) = '('
        THEN substr(scan.stack, 1, length(scan.stack) - 1)
      WHEN c.ch = ']' AND substr(scan.stack, length(scan.stack), 1) = '['
        THEN substr(scan.stack, 1, length(scan.stack) - 1)
      WHEN c.ch = '}' AND substr(scan.stack, length(scan.stack), 1) = '{'
        THEN substr(scan.stack, 1, length(scan.stack) - 1)
      ELSE scan.stack
    END,
    CASE
      WHEN c.ch IN ('(', '[', '{') THEN scan.ok
      WHEN c.ch = ')' AND substr(scan.stack, length(scan.stack), 1) = '(' THEN scan.ok
      WHEN c.ch = ']' AND substr(scan.stack, length(scan.stack), 1) = '[' THEN scan.ok
      WHEN c.ch = '}' AND substr(scan.stack, length(scan.stack), 1) = '{' THEN scan.ok
      ELSE 0
    END
  FROM scan JOIN chars c ON c.pos = scan.pos
  WHERE scan.ok = 1
)
SELECT CASE WHEN ok = 1 AND stack = '' THEN 'True' ELSE 'False' END
FROM scan ORDER BY pos DESC LIMIT 1;

  1. chars ← (empty)

    1.mode list2.headers off
    values this step(empty)chars

  2. chars ← ({[]})

    1.mode list2.headers off
    values this step(empty) → ({[]})chars

  3. pos ← 1, stack ← (

    1.mode list2.headers off
    values this step0 → 1pos(empty) → (stack(ch1ok

  4. pos ← 2, stack ← ({

    1.mode list2.headers off
    values this step1 → 2pos( → ({stack{ch1ok

  5. pos ← 3, stack ← ({[

    1.mode list2.headers off
    values this step2 → 3pos({ → ({[stack[ch1ok

  6. pos ← 4, stack ← ({

    1.mode list2.headers off
    values this step3 → 4pos({[ → ({stack]ch1ok

  7. pos ← 5, stack ← (

    1.mode list2.headers off
    values this step4 → 5pos({ → (stack}ch1ok

  8. pos ← 6, stack ← (empty)

    1.mode list2.headers off
    values this step5 → 6pos( → (empty)stack)ch1ok

  9. stdout ← True

    1.mode list2.headers off
    values this stepTruestdout1ok(empty)stack

Complexity

  • Time: O(n)
  • Space: O(n) worst case for the stack string

Implementation notes

  • SQL: characters are staged in chars(pos, ch), indexed by their position. A WITH RECURSIVE scan(pos, stack, ok) CTE carries the current stack as a plain text string; substr(stack, length(stack), 1) reads the top, and substr(stack, 1, length(stack) - 1) is the pop. Concatenation stack || c.ch is the push.
  • The triple CASE expressions inside the recursive arm enumerate the three matching pairs explicitly so each closer's required opener is visible in the source. An ok = 0 flag is sticky once set; the WHERE scan.ok = 1 guard ends the recursion early.
  • The final projection reports 'True' only when the stack ends empty and no mismatch fired. The canonical lesson input prints True because each closer is preceded by its expected opener and the final pop leaves the stack empty.