import java.io.*;                 
import java.util.*;               
import java.lang.Integer;
import java.lang.*;
class StackX
{
private final int SIZE = 20;
private char[] st;
private int top;
public StackX()           // constructor
   {
   st = new char[SIZE];    // make array
   top = -1;
   }
public void push(char j)   // put item on stack
   { st[++top] = j; }
public char pop()          // take item off stack
   { return st[top--]; }
public char peek()         // peek at top of stack
   { return st[top]; }
public boolean isEmpty()  // true if nothing on stack
   { return (top == -1); }


public boolean CheckExp(String value)
{ 
	int in = 4;
	StackX stack = new StackX();
	char[] OpArray = new char[in];
 
	OpArray[0] = '+';
    OpArray[1] = '-';
    OpArray[2] = '*';
    OpArray[3] = '/';
    
	//char OpenParenthese = '(';
    //char CloseParanthese = ')';
    
    if (value.charAt(0)=='+' || value.charAt(0)=='-' || value.charAt(0)=='*' || value.charAt(0)=='/'){
	return false;
}
    
    if (value.charAt(value.length()-1)=='+' || value.charAt(value.length()-1)=='-' || value.charAt(value.length()-1)=='*' || value.charAt(value.length()-1)=='/'){
	return false;
     }//end if
    
    
    for (int i = 0;i<value.length();i++) {
       for (int p=0 ; p<OpArray.length; p++){
    
	       if(value.charAt(i)=='+' && value.charAt(i+1)== OpArray[p] || value.charAt(i)=='-' && value.charAt(i+1)== OpArray[p] || value.charAt(i)=='*' && value.charAt(i+1)== OpArray[p] || value.charAt(i)=='/' && value.charAt(i+1)== OpArray[p]){
             return false;}
                                             }
                                         }


for (int j = 0;j<value.length();j++) {
	
	
	   
       if (value.charAt(j) == '(')         { 
    	
    	stack.push(value.charAt(j)); 
	                                       }//end if    
	
       else{ 
    	     if (value.charAt(j)== ')')
    	        {    stack.pop();
	                 
	            }//end if
    	     else continue;
	       }//end else

                                     }//end for
if(stack.isEmpty()==true) {
	
	return true;
                          }//end if
else return false;

}//end chekExp 


}// end class StackX 



class Node
{
public char Data;              // data item (key)
public Node leftChild;         // this node's left child
public Node rightChild;        // this node's right child

public void displayNode()      // display ourself
   {
   System.out.print(Data);
   
   }
}  // end class Node
class Tree
{
private Node root;             // first node of tree

//-------------------------------------------------------------
public Tree()                  // constructor
   { root = null; }            // no nodes in tree yet
//-------------------------------------------------------------
public void insert(char d)
{ 
  	
  char[] OpArray = new char[4];
  char[] CharArray = new char[d.length()];
  int j = 0;
  boolean IsMidOperator = false;
  
  OpArray[0] = '+';
  OpArray[1] = '-';
  OpArray[2] = '*';
  OpArray[3] = '/';
  
  
  for (int i=0; i<d.length();i++){
	  if(d.charAt(i) !='(' && d.charAt(i) != ')'){
	  
		  CharArray[j]= d.charAt(i);                 
	      j++;                                    }//end if
                                  }//end for

  
for(int l=0;l<CharArray.length;l++){
  
if (root == null){
	Node newNode = new Node();    // make new node
	
	  for (int p=0 ; p<OpArray.length; p++){
	    if(CharArray[CharArray.length/2]==OpArray[p])
	    	IsMidOperator = true;
	                                       }//end for
	if(IsMidOperator = true){
		newNode.Data = CharArray[CharArray.length/2];	
		root = newNode;        
		char[] CharArray1 = new char[CharArray.length/2];
		char[] CharArray2 = new char[CharArray.length/2];
		for(int u=0;u<CharArray.length/2-1;u++){
			CharArray1[u]=CharArray[u];
		for(int h=CharArray.length;h >CharArray.length/2;h++){
				CharArray2[h]=CharArray[h];
			                                      }                      }//end if
	else{
		newNode.Data = CharArray[CharArray.length/2+1];	
		root = newNode;
	
	    }//end else
	  
	  
                 }//end if
else{                               
    Node current = root;
    Node parent = current;
    
    while (current !=null){
    	if(getNumberOfChildren(parent)==0){
    	   parent.rightChild = 
                                        
                                           }//end if
    	
    
                         }//end while
     
     }//end else

                                    }//end for
	  
    
	

    

}



//-------------------------------------------------------------
public void Divid(String value)
{   
	char[] OpArray = new char[4];
    char[] CharArray = new char[value.length()];
    int j = 0;
    boolean IsMidOperator = false;
    int upper1 , upper2;
    int lower2, lower1;
    int mid1, mid2;
    
    OpArray[0] = '+';
    OpArray[1] = '-';
    OpArray[2] = '*';
    OpArray[3] = '/';
     
    
    for (int i=0; i<value.length();i++){
  	  if(value.charAt(i) !='(' && value.charAt(i) != ')'){
  	  
  		  CharArray[j]= value.charAt(i);                 
  	      j++;                                    }//end if
                                    }//end for
    for (int p=0 ; p<OpArray.length; p++){
	    if(CharArray[CharArray.length/2]==OpArray[p])
	    	IsMidOperator = true;
	                                       }//end for
    if(IsMidOperator = true){
    	insert(CharArray[CharArray.length/2]);
    	
    	upper1 = 0;
    	lower1 = CharArray.length/2-1;
    	
    	upper2 = CharArray.length/2+1;                    
    	lower2 = CharArray.length-1;
         
                            }//end if 
    else{
    	insert(CharArray[CharArray.length/2+1]);
        
      	upper1 = 0;
    	lower1 = CharArray.length/2;
    	
    	upper2 = CharArray.length/2+2;                    
    	lower2 = CharArray.length-1;
          
    
        }//end else
    
    while (upper1<lower1 && upper2<lower2){
        mid1 = (upper1+lower1)/2;
        mid2 = (upper2+lower2)/2;
        
        for(int u = 0;u<OpArray.length;u++){
           if(mid1 ==OpArray[u]){
        	
           
                                 }//end if	
           
        
        insert(CharArray[mid1]);
        insert(CharArray[mid2]);
        }//end for
        
        lower1 = mid1-1;
        upper2 = mid2+1;
        
    
                                                 }//end while
    
    
    
   
  
	
  
  
}//end Eval
//-------------------------------------------------------------
public Node find(char key)      // find node with given key
{                           // (assumes non-empty tree)
Node current = root;               // start at root
//while(current.Data != key)        // while no match,
   {
   //if(key < current.Data)         // go left?
      current = current.leftChild;
  // else                            // or go right?
      current = current.rightChild;
   if(current == null)             // if no child,
      return null;                 // didn't find it
   }
return current;                    // found it
}  // end find()



// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
   {
   Node successorParent = delNode;
   Node successor = delNode;
   Node current = delNode.rightChild;   // go to right child
   while(current != null)               // until no more
      {                                 // left children,
      successorParent = successor;
      successor = current;
      current = current.leftChild;      // go to left child
      }
                                        // if successor not
   if(successor != delNode.rightChild)  // right child,
      {                                 // make connections
      successorParent.leftChild = successor.rightChild;
      successor.rightChild = delNode.rightChild;
      }
   return successor;
   }
//-------------------------------------------------------------
public void traverse(int traverseType)
   {
   switch(traverseType)
      {
      case 1: System.out.print("\nPreorder traversal: ");
              preOrder(root);
              break;
      case 2: System.out.print("\nInorder traversal:  ");
              inOrder(root);
              break;
      case 3: System.out.print("\nPostorder traversal: ");
              postOrder(root);
              break;
      }
   System.out.println();
   }
//-------------------------------------------------------------
private void preOrder(Node localRoot)
   {
   if(localRoot != null)
      {
      localRoot.displayNode();
      preOrder(localRoot.leftChild);
      preOrder(localRoot.rightChild);
      }
   }
//-------------------------------------------------------------
private void inOrder(Node localRoot)
   {
   if(localRoot != null)
      {
      inOrder(localRoot.leftChild);
      localRoot.displayNode();
      inOrder(localRoot.rightChild);
      }
   }
//-------------------------------------------------------------
private void postOrder(Node localRoot)
   {
   if(localRoot != null)
      {
      postOrder(localRoot.leftChild);
      postOrder(localRoot.rightChild);
      localRoot.displayNode();
      }
   }
//-------------------------------------------------------------
public void displayTree()
   {
   Stack globalStack = new Stack();
   globalStack.push(root);
   int nBlanks = 32;
   boolean isRowEmpty = false;
   System.out.println(
   "......................................................");
   while(isRowEmpty==false)
      {
      Stack localStack = new Stack();
      isRowEmpty = true;

      for(int j=0; j<nBlanks; j++)
         System.out.print(' ');

      while(globalStack.isEmpty()==false)
         {
         Node temp = (Node)globalStack.pop();
         if(temp != null)
            {
            System.out.print(temp.Data);
            localStack.push(temp.leftChild);
            localStack.push(temp.rightChild);

            if(temp.leftChild != null ||
                                temp.rightChild != null)
               isRowEmpty = false;
            }
         else
            {
            System.out.print("--");
            localStack.push(null);
            localStack.push(null);
            }
         for(int j=0; j<nBlanks*2-2; j++)
            System.out.print(' ');
         }  // end while globalStack not empty
      System.out.println();
      nBlanks /= 2;
      while(localStack.isEmpty()==false)
         globalStack.push( localStack.pop() );
      }  // end while isRowEmpty is false
   System.out.println(
   "......................................................");
   }  // end displayTree()
//-------------------------------------------------------------

//-------------------------------------------------------------


}



public class CompExpresApp {
	public static void main(String[] args) throws IOException
    {
    String value;
    Tree theTree = new Tree();
    StackX theStack = new StackX(); 
    
 

    while(true)
       {
       putText("Enter first letter of ");
       putText("evaluate,leval, show, insert, find, or traverse: ");
       int choice = getChar();
       switch(choice)
          {
          case 'l':
        	  putText("Enter the expression to be evaluated : "); 
              value = getString();        
              theTree.Eval(value);
              break;
          case 'e':
        	  putText("Enter the expression to be evaluated : "); 
              value = getString();
              
              if(theStack.CheckExp(value)== true){
            	putText("expression was checked and approved");
            	putText("\n");
            	theTree.insert(value);                         
                                                  }//end if
                
              else {putText("Invalid syntax ");}
              putText("\n");
              
             //  if (theStack.CheckExp(value)== true)
             //      theTree.Eval(value);
             //  else {putText("Invalid syntax ");   
             //        breack;}
             // 
          break;
          
          case 's':
             theTree.displayTree();
             break;
          case 'i':
             putText("Enter value to insert: ");
             value = getString();
             //theTree.insert(value);
             break;
          case 'f':
             putText("Enter value to find: ");
             value = getString();
             //Node found = theTree.find("value");
             //if(found != null)
                {
                putText("Found: ");
               // found.displayNode();
                putText("\n");
                }
             //else
                putText("Could not find " + value + '\n');
             break;
          
          case 't':
             putText("Enter type 1, 2 or 3: ");
             value = getString();
             //theTree.traverse(value);
             break;
          default:
             putText("Invalid entry\n");
          }  // end switch
       }  // end while
    }  // end main()
//-------------------------------------------------------------
 public static void putText(String s)
    {
    System.out.print(s);
    System.out.flush();
    }
//-------------------------------------------------------------
 public static String getString() throws IOException
    {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    String s = br.readLine();
    return s;
    }
//-------------------------------------------------------------
 public static char getChar() throws IOException
    {
    String s = getString();
    return s.charAt(0);
    }

//-------------------------------------------------------------
 public static int getInt() throws IOException
    {
    String s = getString();
    return Integer.parseInt(s);
    }
//-------------------------------------------------------------

}