1.

package problemSetVolumes.volume006;
import java.util.Scanner;
/**
   * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10 
   * Problem: 673 - Parentheses Balance
   * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=614
   * 
   * @author Siegfried Ippisch
   * @version 1.0
   * 
   * Method : -
   * Status : Accepted
   * Runtime: 1.204
   */
   public class ParenthesesBalance {
   
   public static void main(String[] args){
   Scanner in = new Scanner(System.in);
   int cases = in.nextInt();
   in.nextLine();
   
   while(cases-- > 0)
   System.out.println(check(in.nextLine()) ? "Yes": "No");
   
   in.close();
   }
   
   public static boolean check(String str){
   int[] stack = new int[128];
   int pos = 0;
   
   for(char c: str.toCharArray()){
   if(c == '(')
   stack[pos++] = 1;
   else if(c == ')' && (pos == 0 || stack[--pos] != 1))
   return false;
   else if(c == '[')
   stack[pos++] = 2;
   else if(c == ']' && (pos == 0 || stack[--pos] != 2))
   return false;
   }
   
   return pos == 0;
   }
   
   }