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>withpush(item: T): void,pop(): T | undefinedandisEmpty(): boolean. - For each line, print
balancedif every(,[and{is closed by the matching bracket in the right order, andnot balancedotherwise. 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");