Challenge: Bracket Checker

Lab Java Beginner 10 points

Read a line that may contain (), [], {} and other characters. Print balanced if every bracket is closed by the right partner in the right order, otherwise not balanced. Ignore other characters.

Input

One line of text.

Output

balanced or not balanced.

Example

Input

if (a[i] > {b}) { x = (y + z); }

Output

balanced

Sample input available Sample output available

Editor

Java

Hints

Push opening brackets. For a closing bracket, pop and check it's the partner.

At the end the stack must be empty.

Solution explanation

O(n) with a stack. Compilers do exactly this to check your code's brackets.

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();
        ArrayDeque<Character> stack = new ArrayDeque<Character>();
        boolean ok = true;
        for (char c : s.toCharArray()) {
            if ("([{".indexOf(c) >= 0) {
                stack.push(c);
            } else if (")]}".indexOf(c) >= 0) {
                char want = "([{".charAt(")]}".indexOf(c));
                if (stack.isEmpty() || stack.pop() != want) {
                    ok = false;
                    break;
                }
            }
        }
        System.out.println(ok && stack.isEmpty() ? "balanced" : "not balanced");
    }
}

Output

Answer