Java: Check brackets with a stack

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. Print balanced, or error at P where P is the 1-based position of the first closing bracket that does not match (or has nothing to match), or error at end when 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()));
    }
}

Lesson: Sets, queues and stacks →