Scanner sc = new Scanner(System.in);

    while (sc.hasNext()) {
        String input=sc.next();
        Stack<Character> s = new Stack<>();
        for(int i=0; i<input.length(); i++){                
            char c = input.charAt(i);
            if(c=='('||c=='['||c=='{'){
                s.push(c);  
            }else if(!s.isEmpty()&&((c==')'&&s.peek()=='(')
            ||(c==']'&&s.peek()=='[')
            ||(c=='}'&&s.peek()=='{'))){
                s.pop();
            }else {
                s.push(c);
            }
        }

        System.out.println(s.isEmpty()? "true": "false");

    }
    sc.close();

import java.util.*; class Solution{

public static void main(String []argh)
{
    Scanner sc = new Scanner(System.in);

    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put('}', '{');
    map.put(']', '[');


    while (sc.hasNext()) {
        boolean bo = true;
        Stack<Character> stack = new Stack<>();
        String input=sc.next();
        for(int i=0;i<input.length();i++) {
            Character c = input.charAt(i);
            if(map.containsValue(c)) {
                stack.add(c);
            }else if(map.containsKey(c)) {
                if(!stack.isEmpty()) {
                    Character p = stack.pop();
                    if(map.get(c) != p) {
                        bo = false;
                        break;
                    }
                }else {
                    bo = false;
                }
            }
        }

        if(stack.isEmpty() && bo) {
            System.out.println("true");
        }else {
            System.out.println("false");
        }

    }

}

}

public static void main(String []argh) { Scanner sc = new Scanner(System.in); Stack stack= new Stack<>(); boolean check= true;

    while (sc.hasNext()) {
        String input=sc.next();
        stack.clear();
        //Complete the code

        for(char c:input.toCharArray()){
            if(c=='('||c=='{'||c=='['){
                stack.push(c);
            }else if(c==')'||c=='}'||c==']'){

                if(stack.isEmpty()){
                    check=false;
                    break;
                }else{

                    char top=stack.pop();

                    if( !((top=='(' && c==')')||(top=='[' && c==']')||(top=='{' && c=='}'))){
                        check=false;
                        break;
                    }else{
                        check=true;
                    }

                }
            }
        }

        if (!check){
            System.out.println(check);
        }else {
            if (stack.isEmpty()){
                System.out.println(check);
            }else {
                System.out.println(!check);
            }
        }

    }

}

import java.util.*; class Solution{ public static void main(String[]args){ Scanner obj = new Scanner(System.in); int tc= obj.nextInt(); while(tc-- >0){

        String s= obj.next();
        Stack<Character> stack = new Stack<>();
        int n = s.length();
        for(int i=0; i<n;i++){
            char ch = s.charAt(i);
            if(!stack.isEmpty()&&
            ((stack.peek()=='{'&& ch=='}') ||
            (stack.peek()=='(' && ch== ')') ||
             (stack.peek()=='[' && ch== ']')
            )){
                stack.pop();
            }
            else{
                stack.push(ch);
            }
        }
        if(stack.isEmpty()){
            System.out.println("balanced");
        }
        else{
            System.out.println("not balanced");
        }
    }
}

}