package eksam0106;

import java.util.*;
//Ott Kingisepp
public class Answer {

   private String   name;
   private Answer   firstChild;
   private Answer   nextSibling;

   Answer (String n, Answer d, Answer r) {
      setName (n);
      setFirstChild (d);
      setNextSibling (r);
   }

   public void   setName (String n)        { name = n; }
   public String getName()                 { return name; }
   public void   setFirstChild (Answer d)  { firstChild = d; }
   public Answer getFirstChild()           { return firstChild; }
   public void   setNextSibling (Answer r) { nextSibling = r; }
   public Answer getNextSibling()          { return nextSibling; }

   @Override
   public String toString() {
      return leftParentheticRepresentation();
   }

   public String leftParentheticRepresentation() {
      StringBuffer b = new StringBuffer();
      b.append (getName());
      if (getFirstChild() != null) {
         b.append ("(");
         b.append (getFirstChild().leftParentheticRepresentation());
         Answer right = getFirstChild().getNextSibling();
         while (right != null) {
            b.append ("," + right.leftParentheticRepresentation());
            right = right.getNextSibling();
         }
         b.append (")");
      }
      return b.toString();
   }

   public static Answer parseTree (String s) {
      if (s == null) return null;
      if (s.length() == 0) return null;
      Answer root = null;
      Answer curr = null;
      Answer last = null;
      int state = 0; // begin
      Stack<Answer> stk = new Stack<Answer>();
      StringTokenizer tok = new StringTokenizer (s, "(),", true);
      while (tok.hasMoreTokens()) {
         String w = tok.nextToken().trim();
         if (w.equals ("(")) {
            state = 1; // from up
         } else if (w.equals (",")) {
            state = 2; // from left
         } else if (w.equals (")")) {
            state = 3; // from down
            stk.pop();
         } else {
            curr = new Answer (w, null, null);
            switch (state) {
               case 0: {
                  root = curr;
                  break;
               }
               case 1: {
                  last = stk.peek();
                  last.setFirstChild (curr);
                  break;
               }
               case 2: {
                  last = stk.pop();
                  last.setNextSibling (curr);
                  break;
               }
               default: {
                  // do not pop here but after ")"
               }
            } // switch
            stk.push (curr);
         }
      } // next w
      return root;
   }

   public int maxWidth() {
	   Answer v = firstChild;
	   int tmpWidth = countChildren(firstChild);
	   if(firstChild== null && nextSibling == null){
		   return 0 ;
	   }
	   if(firstChild != null && nextSibling == null){

	   Answer s = firstChild;
	   if(tmpWidth > s.maxWidth()){
		   return tmpWidth;
	   }
	   else{
		   return s.maxWidth();
	   }
	   }

	   if(firstChild == null && nextSibling != null){
		   Answer s = nextSibling;
		   int comp1 = s.maxWidth();
		   if(comp1>tmpWidth){
			   return comp1;
		   }
		   else{
			   return tmpWidth;
		   }
	   }
	   if(firstChild != null && nextSibling !=null){
		   if(firstChild.maxWidth() > nextSibling.maxWidth()){
			   if(tmpWidth >firstChild.maxWidth()){
				   return tmpWidth;
			   }
			   else{return firstChild.maxWidth();}

		   }
		   else{
			   if(tmpWidth>nextSibling.maxWidth()){
				   return tmpWidth;
			   }
			   else{return nextSibling.maxWidth();}
		   }
	   }
	   return 0;
   }
   public int countChildren(Answer v){
	   if(v ==null){
		   return 0;
	   }
	   int counter = 1;
	   while(v.nextSibling !=null){
		   counter++;
		   v = v.nextSibling;
	   }
	   return counter;
   }

   public static void main (String[] param) {
      Answer v = Answer.parseTree ("A(C,D(F,G,H(Y,U,I,O,P))");
      System.out.println (v);
      int n = v.maxWidth();
      System.out.println ("Maximum number of children: " + n); // 4
      // TODO!!! Your tests here!
   }
}