import java.util.Stack;
import java.util.Scanner;

/**
 * Class that can check a string for matching delimiters.
 *   @author Dave Reed
 *   @version 1/10/17
 */
public class DelimiterChecker {
  private static final String DELIMITERS = "()[]{}<>";

    /**
   * Determines if the string has matching delimiters, i.e., () [] {} <>.
   * @param expr the string to be checked
   * @return true if all parentheses in expr match
   */
  public static boolean check(String expr) {
      Stack<Character> delimStack = new Stack<Character>();

      for (int i = 0; i < expr.length(); i++) {
         char ch = expr.charAt(i);
         if (DelimiterChecker.isLeftDelimiter(ch)) {
             delimStack.push(ch);
         }
         else if (DelimiterChecker.isRightDelimiter(ch)) {
             if (!delimStack.empty() && DelimiterChecker.match(delimStack.peek(), ch)) {
                 delimStack.pop();
             }
             else {
                 return false;
             }
         }
     }  

    return delimStack.empty();
  }

  /**
   * Private helper method that determines whether a character is a left delimiter.
   * @param ch the character to be tested
   * @return true if ch is a left delimiter
   */
  private static boolean isLeftDelimiter(char ch) {
      int index = DelimiterChecker.DELIMITERS.indexOf(ch);
      return (index >= 0) && (index % 2 == 0);
  }

  /**
   * Private helper method that determines whether a character is a right delimiter.
   * @param ch the character to be tested
   * @return true if ch is a right delimiter
   */
  private static boolean isRightDelimiter(char ch) {
      int index = DelimiterChecker.DELIMITERS.indexOf(ch);
      return (index >= 0) && (index % 2 == 1);
  }

  /**
   * Private helper method that determines whether two characters are matching delimiters.
   * @param left the left (opening) character
   * @param right the right (closing) character
   * @return true if left and right are matching left and right delimiters
   */  
  private static boolean match(char left, char right) {
      int indexLeft = DelimiterChecker.DELIMITERS.indexOf(left);
      int indexRight = DelimiterChecker.DELIMITERS.indexOf(right);
      return (indexLeft >= 0) && (indexLeft + 1 == indexRight);
  }
    
  //////////////////////////////////////////////////////
  
  public static void main(String[] args) {
      Scanner input = new Scanner(System.in);
      
      System.out.println("Enter an expression: ");
      String expr = input.nextLine();
      while (!expr.equals("")) {
          if (DelimiterChecker.check(expr)) {
              System.out.println("OK");
          }
          else {
              System.out.println("BAD");
          }
          
          System.out.println("Enter another (or return to quit): ");
          expr = input.nextLine();
      }
      input.close();
  }
}