TypeScript: Check brackets with a generic stack

Write a generic stack class and use it to check whether brackets are balanced.

What to build

A program that checks lines of brackets.

Requirements

  • Write class Stack<T> with push(item: T): void, pop(): T | undefined and isEmpty(): boolean.
  • For each line, print balanced if every (, [ and { is closed by the matching bracket in the right order, and not balanced otherwise. Other characters are ignored.

Input

Line 1: n. Then n lines.

Output

n lines.

Constraints

1 ≤ n ≤ 50; each line has at most 200 characters.

Example

Input:

4
(a[b]{c})
([)]
((
f(x) + g[y]

Output:

balanced
not balanced
not balanced
balanced

Why it works

The stack holds the brackets still waiting to be closed, the most recent on top, which is exactly the one the next closing bracket must match; typing it Stack<string> keeps pop's result checked.

Examples

Example 1 · Input
4
(a[b]{c})
([)]
((
f(x) + g[y]
Expected output
balanced
not balanced
not balanced
balanced
Example 2 · Input
2
}{
no brackets
Expected output
not balanced
balanced

Hints

Hint 1

class Stack<T> with push, pop (returning T | undefined) and isEmpty.

Hint 2

Push opening brackets; for a closing one, pop and check that it matches.

Solution

Show one correct solution (try it yourself first)
const read = (): string => prompt() ?? "";

class Stack<T> {
  private items: T[] = [];
  push(item: T): void {
    this.items.push(item);
  }
  pop(): T | undefined {
    return this.items.pop();
  }
  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

const PAIRS: Record<string, string> = { ")": "(", "]": "[", "}": "{" };

function balanced(line: string): boolean {
  const open = new Stack<string>();
  for (const ch of line) {
    if (ch === "(" || ch === "[" || ch === "{") open.push(ch);
    else if (ch in PAIRS && open.pop() !== PAIRS[ch]) return false;
  }
  return open.isEmpty();
}

const n = Number(read());
for (let i = 0; i < n; i++) console.log(balanced(read()) ? "balanced" : "not balanced");

Lesson: Generic classes and typed collections →