THINK FIRST·CODE LATER

← All labs

Balanced brackets with a stack

Problem

Check whether the brackets (), [] and {} in each line of text are balanced. All other characters are ignored.

Input. An integer n, then n lines of text (a line may be empty).

Output. For each line, print its number (starting at 1), a colon and a space, then either Balanced or Unbalanced at index i, where i (0-based) is:

  • the index of the first closing bracket that has no matching opener (the stack is empty, or its top is a different kind of bracket); or
  • if the line ends with brackets still open, the index of the most recently opened bracket that was never closed.

Use a Deque<Integer> as a stack of the indices of open brackets (push, pop, peek).

Input:
4
([]{})
(]
a[i] = (b + c) * {d};
((

Output:
1: Balanced
2: Unbalanced at index 1
3: Balanced
4: Unbalanced at index 1

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d4-1-data-1.txt

4
([]{})
(]
a[i] = (b + c) * {d};
((
What your program must print for d4-1-data-1.txt
1: Balanced
2: Unbalanced at index 1
3: Balanced
4: Unbalanced at index 1

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d4-1-data-1.txt

Windows PowerShell does not understand <:

Get-Content d4-1-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.