/*
 * ParenArray.java
 */

import java.io.*;

public class ParenArray {
    

    //check if c1 and c2 are matching symbols
    public boolean isMatching(char c1, char c2) {
        if (c1=='(' && c2==')')
            return true;
        if (c1=='[' && c2==']')
            return true;
        //added for tutoral 2
	if (c1=='{' && c2=='}')
            return true;
	//let o=<h4>
	//    O=</h4>
        if (c1=='o' && c2=='O')
            return true;
        
	return false;
    }
    
    public boolean isParenMatch(String X) {
        Stack S = new ArrayStack(); 
        for (int i=0; i< X.length(); i++) {
            char symbol = X.charAt(i);
            if(symbol == '<')
	    {
	       if(i+3>=X.length()) 
		   return false;
	       //furst to check if it is <h4>, if yes, push it onto the stack
	       if(X.charAt(i+1)=='h' && X.charAt(i+2)=='4' && X.charAt(i+3)=='>') 
	       {   
		   S.push( new Character('o') ); //i just use 'o' to denote <h4>
                   System.out.println("Push "+"<h4>");
	       }
	       //otherwise to check if it is </h4>, if yes, push it into the stack
	       else if(i+4>=X.length())
	       { 
		   return false;
	       }
	       else if(X.charAt(i+1)=='/' && X.charAt(i+2)=='h' && X.charAt(i+3)=='4' && X.charAt(i+4)=='>')
	       {
	          if (S.isEmpty()) 
                    return false;

                   char popSymbol = ((Character)S.pop()).charValue();
                   System.out.println("POP " + popSymbol);
                   if ( ! isMatching( popSymbol, 'O') )
                    return false;	       
	       }
	       else return false;
	    }
      }
      if (S.isEmpty())
            return true;
        else
            return false;
    }
    
    // Tester Method
    public static void main (String[] args) throws IOException {
        BufferedReader stdr;
        stdr = new BufferedReader(new InputStreamReader(System.in));
        
        System.out.println("Please input a sequence:");
        String line = stdr.readLine();
        
        ParenArray paren= new ParenArray();
        if ( paren.isParenMatch(line) )
            System.out.println("The parentheses in the input sequence MATCH!");
        else
            System.out.println("The parentheses in the input sequence DO NOT MATCH!");
    }
}