public class Split
{
  
  static Val [] lauf = new Val[0];
  static String kknf;
  static String kdnf;
  static public void main( String[] args )
  {
	kknf = "";
	kdnf = "";

	Root root = new Root();
	root.head = split(args[0], root.head,"");
	lauf = sort(lauf);
	//root.head.print(); 
	printhead(lauf);
	gentable(lauf,root.head);
	System.out.println("-------KDNF:-------");
	System.out.println(kdnf.substring(1));
	System.out.println("-------KKNF:-------");
	System.out.println(kknf.substring(1));
  }
  
  public static Val [] sort(Val [] arry)
  {
	Val temp;
	int k;
	for(int i =1;i<arry.length;i++)
	{
		temp = arry[i];
		for(k=i;k!=0;k--)
		{
			
			
			arry[k] = arry[k-1];
			
			if (temp.name.compareTo(arry[k].name) > 0)
			{
				break;
			}
					
		}
		arry[k] =temp;
	}
	return arry;
		
  }
  
  public static String KDNF(Val [] lauf)
  {
  	String res = "";
	for(int i =0;i<lauf.length;i++)
	{
		if(lauf[i].val ==0)
		{ 
			res = res + "*" + "_" + lauf[i].name;
		}
		else
		{
			res = res + "*" + lauf[i].name;
		} 
	}
	res = res.substring(1);
	return "(" +res + ")";
  }
  
  public static String KKNF(Val [] lauf)
  {
  	String res = "";
	for(int i =0;i<lauf.length;i++)
	{
		if(lauf[i].val ==0)
		{ 
			res = res + "+"+ lauf[i].name;
		}
		else
		{
			res = res + "+"+ "_" + lauf[i].name;
		} 
	}
	res = res.substring(1);
	return "(" +res + ")";
  }
  
  static public Val [] addVar(String a,Val[] lauf)
  {
  	Val [] res = new Val [lauf.length+1];
	
	for(int i =0;i<lauf.length;i++)
	{
		if(lauf[i].name.equals(a))
			return lauf; 
		res[i] = lauf[i];
	}
	res[res.length-1] = new Val(0,a);
	return res;
  }
  
  static public void printhead(Val[] lauf)
  {
	System.out.println("Wahrheitstabelle:");
	for(int i =0;i<lauf.length;i++)
	{
		System.out.print(lauf[i].name + "\t");
	}
	System.out.println("result");
  }  
  
  static public void print(Val[] lauf,Term root)
  {
	
	for(int i =0;i<lauf.length;i++)
	{
		System.out.print(lauf[i].val+ "\t");
	}
	int value = root.getVal(lauf);
	System.out.println(value+"");
	if(value == 0)
	{
		kknf = kknf + "*" + KKNF(lauf);
	}
	else
	{
		kdnf = kdnf + "+" + KDNF(lauf);
	}
	
  }  
  
  static public void gentable(Val[] lauf,Term root)
  {
	int max = (int) Math.pow(2,lauf.length);
	for(int i =0;i<max;i++)
	{
		for(int k=0;k<lauf.length;k++)
		{
			lauf[lauf.length -1- k].val = (i/ (int)Math.pow(2,k))%2;
		}
		print(lauf,root);
	}
  }  
  
  static public Term split(String a,Term root,String not)
  {
  	//System.out.println(a);
	if (a.length() !=0)
	{
		if(a.charAt(0) == '_')
		{
		   
		    return split(a.substring(1),root,"_");
		}
		else if(a.charAt(0) == '(')
		{
			int i;
			int klammerC=1;
			for(i=1;klammerC!=0;i++)
			{
				//System.out.println(a.charAt(i) + "  " +klammerC + " " +i); 
				if(a.length()== i)
				{
					System.out.println("Fehleingabe");
					break;
				}
				
				if (a.charAt(i) == '(')
				{
					klammerC++;
				}
				else if(a.charAt(i) == ')')
				{
					klammerC--;
				}
				
				
			}
			
			root = new Var("temp12722");
			root = split(a.substring(i),root,"");
			if(root.exp.indexOf("temp12722") != -1)
			{
				root = split(a.substring(1,i-1),root,"");
				root.not = not;
			}
			else
			{
				//System.out.println(a.substring(1,i-1));
				root.term1 = split(a.substring(1,i-1),root.term1,"");
				root.term1.not = not;
			}
			return root;
			 
		}
		else if (isOperator(a.charAt(0)))
		{
			//System.out.println("split");
			//System.out.println(root.exp);
			
			
			Term temp = root;
			root = new Binop(a.charAt(0)+"");
			root.term1 = temp;
			root.term2 = split(a.substring(1),root.term2,"");
			root.not = not;
			return root;
			
		}
		else 
		{
			int i;
				
			for(i=0;a.length()>i && isOperator(a.charAt(i))==false;i++)
			{
				
			}
			if(a.length()==i)
			{
				root = new Var(a);
				lauf = addVar(a,lauf);
				split("",root,"");
				root.not = not;
				return root;				
			}
			else
			{	
				//System.out.println(a.substring(0,i) + " da split");
				root = split(a.substring(0,i),root,"");
				root.not = not;
				//System.out.println(a.substring(i) + " da split");
				root = split(a.substring(i),root,"");
				
				return root;
				
			}
		}
	}
	return root;
  }
  
  static boolean isOperator(char k)
  {
  	if(k=='+' || k=='*')
	{
		return true;
	}
	else
	{
		return false;
	}
  }
}



class Root
{
	Term head;

}


class Term
{
	
	Term term1;
	Term term2;
	String exp;
	String not;
	
	public Term(String exp)
	{
		this.exp = exp; 
	}
	
	public void print() {}
	public void split(String a){}
	public int getVal(Val[] lauf)
	{
		return 1;
	}
}

class Binop extends Term
{
	public Binop (String exp)
	{
		super(exp);
		//System.out.println(exp);
	}
	
	public void print()
	{
		System.out.println("Exp " +this + " "+  exp + " "+  not  +" zeigt auf Term1: " +term1+ " " +term1.exp + " "+  term1.not  +" Term2: " + term2+" " + term2.exp+ " "+  term2.not);
		term1.print();
		term2.print();	
	}
	
	public int getVal(Val[] lauf)
	{
		int val1 = term1.getVal(lauf); 
		int val2 = term2.getVal(lauf); 
	 	int val = -1;
		if(exp.equals("+"))
		{
			if(val1 == 0 && val2 == 0)
				val = 0;
			else if (val1 == 0 && val2 == 1)
				val = 1;
			else if (val1 == 1 && val2 == 0)
				val = 1;
			else if (val1 == 1 && val2 == 1)
				val = 1;
			
		}
		else
		{
			if(val1 == 0 && val2 == 0)
				val = 0;
			else if (val1 == 0 && val2 == 1)
				val = 0;
			else if (val1 == 1 && val2 == 0)
				val = 0;
			else if (val1 == 1 && val2 == 1)
				val = 1;
		}
		if(not.equals("_"))
		{
			if(val ==1)
				return 0;
			else
				return 1;
		}
		
		return val;	
	}
	
	
}


class Var extends Term
{
	public Var (String exp)
	{
		
		super(exp);
		//System.out.println(exp);
	}
	
	public int getVal(Val [] lauf)
	{
		for(int i=0; i<lauf.length;i++)
		{
			if(lauf[i].name.equals(exp))
			{
				
				int val = lauf[i].val;
				if(not.equals("_"))
				{
					if(val ==1)
						return 0;
					else
						return 1;
				}
				return val;
			}
			
		}
		return -1;
	}
	
}

class Val 
{
	int val;
	String name;
	public Val(int val,String name)
	{
		this.val = val;
		this.name = name;
	}
	
}