//package www.JavaDS_Examples.Stack;

import java.io.*;
/**A class to check for balance in input with respect to characters like '{,(,{' . The class uses stack to find out the correctness 
of the input . for each character encountered, if it is a opening bracket , it is pushed into the stack .On the other hand
if a closing bracket is encountered, the stack is popped  and checked for correct opening character . If not found, the algorithm st
ops
and returns false.*/
public class BalancedBraces {
        
   public boolean balanceInput(String input){
      /*stack used for manipulating the input */
      Stack stack=new ArrayStack(); 
      boolean balancedSoFar=true; // boolean used to check the correctness
      int i=-1;
      /*do this while loops, the character we are about to extract is less than the total length 
       and the input is balanced so far*/
      while(balancedSoFar && i<input.length()-1){ 
         //get character at ith position
         char c=input.charAt(++i);         
         if(c=='{' || c=='[' || c=='(')           
            stack.push(new StackElementImpl(c));
         //encountered a closing kind of bracket , so pop and check for corresponding opening bracket
         else if(c=='}' || c==']' || c==')')         

         if(!stack.isEmpty()){          //is stack empty?? 
            //get character from the top of the stack 
            // char temp=(Character)((StackElementImpl)stack.top()).get();stack.pop();  
            if(!isMatching(c,temp))         // does the brackets match ??? if not set the balancedSoFar to false
            balancedSoFar=false;
         //stack is empty , breaking from the while loop and returning false;                           
         }else             
            balancedSoFar=false;
                                
      }
      
      //return true if both the stack is empty and it is balanced so far
      return balancedSoFar && stack.isEmpty(); 
   }
        
/*A small function to check for matches.*/
   private boolean isMatching(char c,char justPopped){
      switch(c){
         case '}':
            return '{'==justPopped;
         case ']' :
            return '['==justPopped;
         case ')' :
            return '('==justPopped;
      }
      return false;
   }
        
   public static void main(String [] args) throws Exception{
      BufferedReader in=new BufferedReader(new InputStreamReader(new FileInputStream(args[0])));
      BalancedBraces braces=new BalancedBraces();
      String s=null;
      while((s=in.readLine())!=null)
      System.out.println(s+" is balanced :" +braces.balanceInput(s));           
   }
        
        
}