class ExprLogic
{

// ----------------------------------------- //	
	
	String []Variabile;                      // se retin variabilele ce apar in formula ex : X3,X5 ...
	
	int nrVariabile;                         // numarul variabilelor ce apar in expresie 
	
	String exprLogic;                        // expresia logica de transformat
	
	String exprPrel;                         // expresia logica dupa eliminarea uneia sau a mai multe variabile
	
// ----------------------------------------- //	
	
	ExprLogic (String expr)
	{ 
	  int indx;
	  
	  String s;
	  
	  nrVariabile = -1;                   
	  
	  exprLogic = new String(expr);          // se retine expresia
	  exprLogic = "("+expr+")";
	  
	  Variabile = new String[30];            // se initializeaza sirul de variabile
	  
	  for (indx = 0; indx <= 30; indx ++)    // se considera maxim 30 de variabile
	     {
	     	 s = new String("X");            // se costruieste variabila Xindx care se cauta in expresie
	     	 s = s.concat(s.valueOf(indx));
	     	 
	     	 if (exprLogic.indexOf(s)!= -1 ) // daca variabila apare => creste numarul de variabile iar aceasta se retine
	     	    { 
	     	      nrVariabile ++ ;
	     	      
	     	      Variabile[nrVariabile] = new String(s);
	     	      
	     	    }  
	     	 
	     }
		     
	 }
	 

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


    String elimVarPeLow (int nrVar, String expr)	
    {
      boolean apar, cont, neg, next;
      
      int pozitie =-1, indxStanga=-1, indxDreapta=-1;
      
      String subS,subS1;
      
      char chr;
      
      apar = true;
      
      next = false;
  

      while (apar) 
      
          { if (next) 
              { pozitie = expr.indexOf(Variabile[nrVar],pozitie+1);}  // se cauta variabila in expresie
            else{
               pozitie = expr.indexOf(Variabile[nrVar]);}
                 
             neg = false; 
  
             if (pozitie == -1)                                      // daca nuse gaseste
                 
                 apar = false;                                       // se iese 
             
             else                                                    // daca este gasita 
                { if (expr.length()!=pozitie+Variabile[nrVar].length())
                     chr = expr.charAt(pozitie+Variabile[nrVar].length());
                  else chr ='o';
              	  if ((chr<='9' &&  chr>='0'))                      // se testeaza daca nu apare o cifra dupa variabila
              	     next = true;
              	  else                  	                                                     // astfel incat sa se confunde ex: X11 cu X1
                     {
                	   cont = true;                	                 
                	   indxStanga = pozitie;                         // se cauta produse in care intra variabila  
                	  
                	   while (cont)
                	                   	    
                	     if (indxStanga == 0)
                	         break;
                	     else                             // daca nu este la inceputul expresiei se face cautare 
                			{										 // spre stanga 	
                	          chr = expr.charAt(pozitie - 1);
                	          
                	          if (chr == '!')
                	             { neg = true;                       // se neaga deci devine 1 
                	               indxStanga --; 
                	               break;
                	             }  
 
                	          chr = expr.charAt(indxStanga - 1); 
                	          if (chr != '(' && chr != '+')          // cat timp nu se intanlesc caracterele  ( sau +                	         
                                  indxStanga --;                     // indicele se decrementeaza 
                              else
                                  break;    
                             }
                            
    	                    
    	             
    	               cont = true;                                  // se incepe o cautare la dreapta
                	
                	   indxDreapta = pozitie + Variabile[nrVar].length();                	                 	
                	 
                	   while (cont)                                	
                	   
                	     if (indxDreapta != expr.length())           // daca nu se afla la cap de sir
                	        {
							  chr = expr.charAt(indxDreapta);	                	     
                	          
                	          if (neg)
                	           {
                	           	if ( chr == '*' || chr =='+' || chr ==')')          // daca nu este ) sau +
                	              cont = false;
                	            }  
     
                	          else 
                	              
                	          if (chr != ')' && chr != '+')          // daca nu este ) sau +
                	    
                                  indxDreapta ++;                       
                              else             
    	                        {
    	                          cont = false;
    	                     
    	                          if (expr.charAt(indxDreapta)=='+') // semnul se pastreaza la stanga aici se sterge 
    	                         
    	                             indxDreapta++;
    	                           if (chr == ')' && expr.charAt(indxStanga-1)!='(') 
                	                if (indxStanga!=0) 
                	                  indxStanga--;       	                     
    	                         } 
    	                     }    
    	                  else 
    	                    {  cont = false;                         // daca s-a ajuns la capat se sterge semnul din stanga
    	                       if (indxStanga!=0)
    	                          indxStanga --;
    	                    }
    	                	             
    	          	  subS=new String(expr.substring(0,indxStanga)); // se elimina factorul din expresie
    	         
    	         	  subS1 =new String(expr.substring(indxDreapta,expr.length()));
    	              if (!neg)
    	         	    subS = subS+subS1;
    	              else 
    	                subS = subS+"1"+subS1; 
    	         	  expr = new String (subS);

    	            }
    	         } 
    	      
    	      }        

    	 return expr;     
    	                   
    }
    	                
    	                
// ----------------------------------------- //    	                


    String elimVarPeHigh (int nrVar, String expr)	
    {
      boolean apar, cont,cont1,next, neg = false;
      
      int pozitie = -1, indxStanga=-1, indxDreapta=-1;
      
      String subS,subS1;
      
      char chr;
      
      apar = true;
      
      
      next = false;
      
      while (apar) 
      
         { if (next)
            {
            pozitie = expr.indexOf(Variabile[nrVar],pozitie+1);               // se cauta variabila in expresie
              next = false; 
            }  
           else 
             pozitie = expr.indexOf(Variabile[nrVar]);
             neg = false;             
             
             if (pozitie == -1)                                      // daca nuse gaseste
                 
                 apar = false;                                       // se iese 
             
             else                                                    // daca este gasita 
                { 
                  if (expr.length()!=pozitie+Variabile[nrVar].length())
                     chr = expr.charAt(pozitie+Variabile[nrVar].length());
                  else chr ='o';
                  
                  if (chr<='9' &&  chr>='0')                      // se testeaza daca nu apare o cifra dupa variabila
              	     next = true;
              	  else                                                   // astfel incat sa se confunde ex: X11 cu X1
                     {
                	   cont = true;                	                 
                	   indxStanga = pozitie;                         // se cauta produse in care intra variabila  
                	          	  	                	   
                	   while (cont)
                	                   	    
                	     if (indxStanga != 0)                        // daca nu este la inceputul expresiei se face cautare 
                			{										 // spre stanga 	
                	          chr = expr.charAt(indxStanga - 1);

                	          if (chr == '!')                        // cat timp nu se intanlesc caracterele  ( sau +                	         
 		                         { 
 		                           neg = true;               	    
                                   indxStanga --;                     // indicele se decrementeaza 
                                   cont1 = true;                                   
                                   while(cont1)   
                                     if (indxStanga != 0)             // daca nu este la inceputul expresiei se face cautare 
                			           {						 // spre stanga 	
                	                     chr = expr.charAt(indxStanga - 1);
                	                    
                	         
                	                      if (chr != '(' && chr != '+')   
                	    
                                             indxStanga --;                     // indicele se decrementeaza                                        
                                                
                         
                                          else             
                                             {     	                
    	                                      cont1 = false;
    	                                      cont = false;  break;     // altfel se iese din bucla
    	                                     }
    	                               }
    	                    	      else             
                                          {     	                
    	                                   cont1 = false;
    	                                   cont = false;  break;     // altfel se iese din bucla
    	                                  } 
    	                    	                          
    	                           }  else break;
    	                           
    	                          }
    	                         else cont = false;  
 
    	               cont = true;                                  // se incepe o cautare la dreapta
                	
                	   indxDreapta = pozitie + Variabile[nrVar].length();        
                	         	                 	
                	   while (cont)                                	
                	   
                	     if (indxDreapta == expr.length())        
                	         break;
                	     else       // daca nu se afla la cap de sir
                	        {
							  chr = expr.charAt(indxDreapta);	                	                     	         
                	          cont1 = true;
                	          if (!neg)                 	          
                	           if ( chr == '*' || chr =='+' || chr ==')')          // daca nu este ) sau +
                	              cont = false;
    	                       
    	                       if (neg)   	                           
    	                         
    	                         while (cont1)                                	
                	   
                	               if (indxDreapta != expr.length())           // daca nu se afla la cap de sir
                	                  {
							            chr = expr.charAt(indxDreapta);	                	                     	                         	                     
                	                     if (chr != ')' && chr != '+')          // daca nu este ) sau +
                	    
                                            indxDreapta ++;                       
                                         else             
    	                                   { 
    	                                     if (chr == ')' && expr.charAt(indxStanga-1)=='+')
    	                                      if (indxStanga!=0)
    	                                         indxStanga --;
    	                                     cont1 = false; cont = false;
    	                     
    	                                     if (expr.charAt(indxDreapta)=='+') // semnul se pastreaza la stanga aici se sterge 
    	                         
    	                                        indxDreapta++;
    	                     
    	                                    }      
    	                                }    
    	                            else 
    	                             {  cont = false;                         // daca s-a ajuns la capat se sterge semnul din stanga
    	                                cont1 = false;
    	                                if (indxStanga!=0)
    	                                indxStanga --;
    	                             }         
    	                          
    	                         }
   
    	                                 
    	          	  subS=new String(expr.substring(0,indxStanga)); // se elimina factorul din expresie
    	         
    	         	  subS1 =new String(expr.substring(indxDreapta,expr.length()));
    	          
    	              if (neg)
    	             	  subS = subS+subS1;
    	              else
    	                  subS = subS+"1"+subS1;
    	         	  expr = new String (subS);

    	            }
    	         } 
    	      
    	      }        
    	 return expr;     
    	                   
    }
	      	                
    	                
// ----------------------------------------- //  



    String evalExpr (int nrVar, String expr)	
    { 
     int indx;
     
     boolean apare,cont;
     
     char chr;
     
     int poz;
     
     String subS, subS1;
     
     for(indx = 0; indx <= nrVariabile; indx ++)       // se cauta dependenta expresiei de alte variabile
       { 
        poz = expr.indexOf(Variabile[indx]);
         
         if (poz != -1 )
           if (expr.length()==poz+Variabile[indx].length())
              return Variabile[indx]; 
           else      
             if (!(expr.charAt(poz+Variabile[indx].length())>='0' && expr.charAt(poz+Variabile[indx].length())<='9')) 
              return Variabile[indx]; 
        }

     cont = true;
     
     while (cont) 												// cat timp exista paranteze 
         { 
            cont = false; 
            
            apare = true;
     		
     		while (apare)         							    // se cauta expresii de genu : !() si se inlocuiesc cu 1
        		{ 
         			indx = expr.indexOf("!()");
         
         			if (indx != -1) 
           				{
           					subS=new String(expr.substring(0,indx)); 
    	         
    	    				subS1 =new String(expr.substring(indx+3,expr.length()));
    	          
      	    				subS = subS+"1"+subS1;
      	    				
      	    				expr = new String (subS);
      	    				
      	    				cont = true;
            			}       
         			else	
             			apare = false;
       			}        
       
       		apare = true;
       
       		while (apare)           							 // se cauta expresii de genu : () si se inlocuiesc cu 0
       			{ 
         			indx = expr.indexOf("()");
         
         			if (indx != -1) 
           				{
           					subS=new String(expr.substring(0,indx));          
    	         
    	    				subS1 =new String(expr.substring(indx+2,expr.length()));
    	          
	      	    			subS = subS+"0"+subS1;
      	    				
      	    				expr = new String (subS);
      	    				
      	    				cont = true;
            			}       
         			else
             			apare = false;
       			}        
      
       		apare = true; 

      		while (apare)         								  // se cauta expresii de genu : !(1) si se inlocuiesc cu 0
       			{ 
         			indx = expr.indexOf("!(1)");
         
         			if (indx != -1) 
           				{
           					subS=new String(expr.substring(0,indx)); 
    	         
    	    				subS1 =new String(expr.substring(indx+4,expr.length()));
    	          
      	    				subS = subS+"0"+subS1;
      	    				
      	    				expr = new String (subS);
      	    				
      	    				cont = true;
            			}       
         			else	
             			apare = false;
       			}        

	  		apare = true; 
	  
	  		while (apare)       								  // se cauta expresii de genu : (1) si se inlocuiesc cu 1  
       			{ 
         			indx = expr.indexOf("(1)");
         
         			if (indx != -1) 
           				{
           					subS=new String(expr.substring(0,indx)); 
    	         
    	    				subS1 =new String(expr.substring(indx+3,expr.length()));
    	          
      	    				subS = subS+"1"+subS1;
      	    				
      	    				expr = new String (subS);
      	    				
      	    				cont = true;
            			}       
         			else
             			apare = false;
        		}        
        
        	apare = true;
        
        	while (apare)                                        // se cauta expresii de genu : !(0) si se inlocuiesc cu 1
       			{ 
         			indx = expr.indexOf("!(0)");
	         
         			if (indx != -1) 
           				{
           					subS=new String(expr.substring(0,indx)); 
	    	         
    	    				subS1 =new String(expr.substring(indx+4,expr.length()));
    	          
      	    				subS = subS+"1"+subS1;
      	    				
      	    				expr = new String (subS);
      	    				
      	    				cont = true;
            			}       
         			else
             			apare = false;
        		}        
        
        	apare = true; 
        
         	while (apare)                                        // se cauta expresii de genu : (0) si se inlocuiesc cu 0
       			{ 
         			indx = expr.indexOf("(0)");
         
         			if (indx != -1) 
           				{
           					subS=new String(expr.substring(0,indx)); 
    	         
    	    				subS1 =new String(expr.substring(indx+3,expr.length()));
    	        
      	    				subS = subS+"0"+subS1;
      	    				
      	    				expr = new String (subS);
      	    				
      	    				cont = true;
            			}       
         			else
             			apare = false;
        		}        
        		
        		
        	apare = true; 
        
         	while (apare)                                        // se cauta expresii de genu : (0) si se inlocuiesc cu 0
       			{ 
         			indx = expr.indexOf("1*1");
         
         			if (indx != -1) 
           				{
           					subS=new String(expr.substring(0,indx)); 
    	         
    	    				subS1 =new String(expr.substring(indx+3,expr.length()));
    	        
      	    				subS = subS+"1"+subS1;
      	    				
      	    				expr = new String (subS);
      	    				
      	    				cont = true;
            			}       
         			else
             			apare = false;
        		}        
		   
		   apare = true; 
        
         	while (apare)                                        // se cauta expresii de genu : (0) si se inlocuiesc cu 0
       			{ 
         			indx = expr.indexOf("1+1");
         
         			if (indx != -1) 
           				{
           					subS=new String(expr.substring(0,indx)); 
    	         
    	    				subS1 =new String(expr.substring(indx+3,expr.length()));
    	        
      	    				subS = subS+"1"+subS1;
      	    				
      	    				expr = new String (subS);
      	    				
      	    				cont = true;
            			}       
         			else
             			apare = false;
        		}        
		
		
		}
  
  if (expr.indexOf("1") != -1) 
  
     return "1";                  // expresia este egala cu 1
  
  else    
     
     return "0";                  // expresia este egala cu 0;
     }
}