/** Program Checking for Balanced Parentheses */

class ParenMatcher {
   private String inputString, outputString;

   private boolean match (char c, char d) { // this boolean method
                                            // returns true if and
      switch (c) {                          // only if c and d are
         case '(' : return (d == ')');          // matching pairs
         case '[' : return (d == ']');       // of parentheses (),
         case '{' : return (d == '}');      // square brackets [],
         default : return false;                  // or braces { }
      }  
   }//end match

   public void parenMatch() {
      Stack parenStack = new Stack(); // the parenStack holds left parens
                                              // and is popped when right
      int n = inputString.length();             // parens are encountered
      int i = 0;      // i is the index of the ith input string character
      char c,d;                       // c and d hold characters to match
      
      while (i < n) {
         d = inputString.charAt(i);    // d is assigned the ith character
         if (d == '(' || d == '[' || d == '{') {      // push each of the
                                       // three types of left parentheses
            parenStack.push(new Character(d));        
         } else if (d == ')' || d == ']' || d == '}') {  // match each of
                                  // the three types of right parentheses
            if (parenStack.empty()) {
               output("More right parentheses than left parentheses");
               return;
            } else {
               c = ((Character)parenStack.pop()).charValue();
               if (!match(c,d)) {// if c doesn't match the right parenthesis
                  output("Mismatched parentheses: "+ c +" and " + d);
                  return;
            
               }//end if
            }//end if
         }//end if
         ++i;               // increase index i to scan next input char
      }//end while

      if (parenStack.empty()) {
         output("Parentheses are balanced properly");
      } else {
         output("More left parentheses than right parentheses");
      }//end if
   }//end parenMatch

   private void output(String s) {
      outputString = s;
   }//end output

   public void setInput(String input) {
      inputString = input;
   }//end setInput

   public String getOutput() {
      return outputString;
   }//end getOutput

}//end class ParenMatcher