Challenge: Balanced Brackets

Lab Java Intermediate 20 points

Read a line made of the brackets ( ) [ ] { }. Print balanced if every bracket is closed by the right kind in the right order, otherwise not balanced. Use a stack.

Input

One line of brackets (no spaces).

Output

balanced or not balanced.

Example

Input

([]{})

Output

balanced

Sample input available Sample output available

Editor

Java

Hints

Push every opening bracket.

For a closing bracket, pop and check it matches.

At the end the stack must be empty.

Solution explanation

The most recent unclosed bracket is always on top of the stack, so it must match the next closing one.

Show solution

import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine().trim();
        ArrayDeque<Character> stack = new ArrayDeque<>();
        boolean ok = true;
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) { ok = false; break; }
                char open = stack.pop();
                if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) {
                    ok = false;
                    break;
                }
            }
        }
        if (!stack.isEmpty()) ok = false;
        System.out.println(ok ? "balanced" : "not balanced");
    }
}

Output

Answer