Balanced Brackets

Lab Java Intermediate 20 points

Read a line and print balanced or unbalanced for ()[]{}, using an ArrayDeque<Character> as a stack.

Input

One line.

Output

One word.

Example

Input

{[()()]}

Output

balanced

Sample input available Sample output available

Editor

Java

Hints

push opening brackets; a closing one must match pop().

Solution explanation

ArrayDeque is the recommended stack in modern Java (the old Stack class is synchronised and slower).

Show solution

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

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

Output

Answer