Matching brackets is the classic job for a stack.
What to build
A program that checks brackets in each line and says where the first problem is.
Requirements
- For each line, consider only
()[]{}characters. Printbalanced, orerror at Pwhere P is the 1-based position of the first closing bracket that does not match (or has nothing to match), orerror at endwhen brackets are left open.
Input
Line 1: n. Then n lines.
Output
n lines.
Constraints
1 ≤ n ≤ 50; lines have at most 200 characters.
Example
Input:
4
a(b[c]d)e
([)]
((x)
)
Output:
balanced
error at 3
error at end
error at 1
Why it works
The stack holds the brackets still open, the most recent on top, which is exactly the one the next closing bracket must close.
Examples
Example 1 · Input
4 a(b[c]d)e ([)] ((x) )
Expected output
balanced error at 3 error at end error at 1
Example 2 · Input
2
no brackets
{[()()]}
Expected output
balanced balanced
Hints
Hint 1
Push opening brackets onto an ArrayDeque<Character>; for a closing one, the top must be its partner.
Hint 2
Report the 1-based position of the first problem.
Solution
Show one correct solution (try it yourself first)
import java.util.*;
public class Main {
static String check(String line) {
Deque<Character> open = new ArrayDeque<>();
for (int i = 0; i < line.length(); i++) {
char c = line.charAt(i);
if (c == '(' || c == '[' || c == '{') {
open.push(c);
} else if (c == ')' || c == ']' || c == '}') {
char want = c == ')' ? '(' : c == ']' ? '[' : '{';
if (open.isEmpty() || open.pop() != want) return "error at " + (i + 1);
}
}
return open.isEmpty() ? "balanced" : "error at end";
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = Integer.parseInt(in.nextLine().trim());
for (int i = 0; i < n; i++) System.out.println(check(in.nextLine()));
}
}