//Autor: Johannes Ullmann, joli@ull.at
//MatNr: 0126489
//BspNr: 1206
//Created: 2001-10-23
//Last edited: 2001-11-08
//Beschreibung: Polynomdivision von 2 Polynomen :
//	 1. Das Programm zerlegt die beiden eingabe Strings in Array of Integer
//  2. Die Polynome werden Dividiert, Ergebnis & Rest wird in Array of float gespeichert
//	 3. Falls Fehler ==> Ausgabe:"FALSCHE EINGABE" & Abbruch des Programmes
//	 3. Quotient und Rest werden Ausgeben richtig formatiert ausgegeben


import eprog.*;		//EprogIO Verwenden

public class divpoly 
{
	
	static float Rest[]= new float[10];	//Globale Variable für den Rest der Divison
	static boolean Fehler = false;		//Globale Variable zur Fehlerbehandlung
	static boolean KeinRest = false;		//Wird gesetzt wenn Rest=0
	static boolean[] Errors = new boolean[6];		// Hilfs variable für fehlersuche
	
	public static int getExponent(String PolynomTeil)
	//Liefert den Exponenten des Polynom Teils zurück 
	//aufgebaut in der Art "axy" wobei a=-999..+999, y=0..9!
	{
		int Exp = 0;
		if (PolynomTeil.indexOf('x')==-1) Exp=0; //Wenn kein x vorhanden ist ==> Exp=0
		//Wenn x ohne Exponent Exp=1:
		else if (PolynomTeil.indexOf('x') == PolynomTeil.length()-1) Exp=1;
		else  //x mit Exponent
		{
			Exp = Character.getNumericValue(PolynomTeil.charAt(PolynomTeil.length()-1));	
			//Fehler wenn Exp mehr als eine Stelle hat
			if(PolynomTeil.length() > PolynomTeil.indexOf('x')+2) {Fehler=true; Errors[0]=true;}
		}
		//EprogIO.println("EXPONENT:"+Exp);	//Debug
		return Exp;	
	}
	
	//Erzeugt aus dem Sting ein Array mit
	//ArrayIndex = Exponent, Inhalt = Koeffizient
	public static int[] polyStringToIntArray(String PolynomString)
	{																					
		int[]	PolynomArray = new int[10];	
		int Index=0, EndIndex=0, Count=0;
		
		do	//Anzahl der Polynom Elemente  bestimmen (Trennung bei '+' oder '-')
		{
			++Index;
			//Kein weiters Trennzeichen vorhanden
			if (PolynomString.indexOf('+',Index)==-1 && PolynomString.indexOf('-',Index)==-1) Index=-1;
			//Es gibt nur noch +
			else if (PolynomString.indexOf('-',Index) == -1) Index = PolynomString.indexOf('+',Index);
			//Es gibt nur noch -
			else if (PolynomString.indexOf('+',Index) == -1) Index = PolynomString.indexOf('-',Index);
			//naechstes Element (entweder + oder -)
			else Index = Math.min(PolynomString.indexOf('+',Index),PolynomString.indexOf('-',Index));	
			//for debug:
			//EprogIO.println("Index of -" + PolynomString.indexOf('-'));
			if(Index!=-1) Count++; //+1 wenn Wenn noch ein Trennzeichen (+ oder -) vorhanden ist 

		}while(Index!=-1);	//solange bis kein Trennzeichen mehr folgt
		
		String PolyTeile[] = new String[Count+1];		//Stringarray für die Polynomteile
		
		Index=0;
		
		//das Polynom in seine Teile zerlegen
		//und zwar vom Anfang bis zum nächsten Operator (+ oder -)
		for (int i=0; i<=Count; i++)
		{
			if (Index==0 && PolynomString.charAt(0)=='-') Index=1;
			//Kein weiters Trennzeichen ==> Letzer Teil	 
			if (PolynomString.indexOf('+',Index)==-1 && PolynomString.indexOf('-',Index)==-1) EndIndex=-1;
			//Es kommen nur mehr positive Teile
			else if (PolynomString.indexOf('-',Index) == -1) EndIndex = PolynomString.indexOf('+',Index);
			//Es kommen nur mehr negative Teile
			else if (PolynomString.indexOf('+',Index) == -1) EndIndex = PolynomString.indexOf('-',Index);
			//der Teil der am nächsten ist 
			else EndIndex = Math.min(PolynomString.indexOf('+',Index),PolynomString.indexOf('-',Index));
		
			//nur bei - den Operator mitkopieren
			if (Index!=0 && PolynomString.charAt(Index-1)=='+') Index++;
			//Es ist nur ein PolynomTeil
			if (EndIndex==-1 && Index==0) PolyTeile[i]=PolynomString;
			//Das letzte Element geht bis zum String Ende 
			else if (EndIndex==-1 && Index!=0) PolyTeile[i]=PolynomString.substring(Index-1);
			//Das Erste Element geht von O weg 
			else if (Index==0) PolyTeile[i]=PolynomString.substring(Index,EndIndex);
			//alle Elemente in der Mitte
			else PolyTeile[i]=PolynomString.substring(Index-1,EndIndex);
			
			Index=EndIndex+1;	//Naechsten Operator ab anfang vom nächsten Teil suchen
		}
		
		//for Debug:
		//for (int i=0; i<PolyTeile.length; i++) EprogIO.println("PolyTeil["+i+"]="+PolyTeile[i]);
		
		//Speicher die Koeffizienten in ein Array 
		//wobei der ArrayIndex gleich dem Exponenten ist: 
		for (int i=0; i<=Count; i++)
		{	
			int Exponent = getExponent(PolyTeile[i]); //Exponenten des Polynom Teils Bestimmen
			int XIndex = PolyTeile[i].indexOf('x'); //An welcher Stelle das X steht
			
			//FEHLER: gleiche Teile mit Selben Exponent 	
			if(PolynomArray[Exponent] != 0) {Fehler=true; Errors[1]=true;}
			
			switch (XIndex)	//Wo steht x		
			{
				case -1 :
					//es gibt kein x ==> Koef=String
					PolynomArray[Exponent]=Integer.parseInt(PolyTeile[i]); 
					break;
				case 0 :
					PolynomArray[Exponent] = 1; //X steht am Anfang ==> Koef=1
					break;	
				case 1 :
					//Char vorm x = '-' ==> Koef=-1
					if (PolyTeile[i].charAt(0)=='-') PolynomArray[Exponent] = -1;
					//Char vorm x=koef:
					else PolynomArray[Exponent] = Character.getNumericValue(PolyTeile[i].charAt(0));
					break;
				default:	//sonst ist alles vorm x der Koeffizient
					PolynomArray[Exponent] = Integer.parseInt(PolyTeile[i].substring(0,XIndex));	
					break;
			}
			//FEHLER: Koeffizient(en) ausserhalb spez.
			if ((PolynomArray[Exponent] > 999) || (PolynomArray[Exponent] < -999)) 
				{Fehler=true;  Errors[2]=true;}
		}
		return PolynomArray;
	}

	//Polynom divison 
	public static float[] PolynomDivision(int[] Zaehler, int[] N )
	{
		int n=0 , m=0;
		float[] Q = new float[10]; //Quotient
		float[] Z = new float[10];
			
		for (int i=0; i<=9; i++) //Wandelt den Zähler vom Typ Int nach Float um!
		{
			Z[i] = Zaehler[i]; //Umwandeln
			if(Z[i]!=0) m=i;	//gleichzeitig den Grad des Z-Polys bestimmen	
		}
		
		//Grad des Nenner Polys bestimmen:	
		for (int i=0; i<=9; i++) if(N[i]!=0) n=i;	//n ist FEST!!!
		if (n>m) {Fehler=true; Errors[4]=true;}	//Nenner größer als Zähler?
		
		for(int k = (m-n); k>=0; k--)	//Polynom Divison
		{
			Q[k] = Z[n+k]/N[n];;		//den Koeffizient für den Quotient errechnen
		
			//Quotient mit Nenner Multipizieren und vom Zaehler Subtrahieren,	
			//und dies für alle Elemente des Nenners durchführen:
			for(int j = (n+k); j>=k; j--)	Z[j] = Z[j] - (Q[k]*N[j-k]);
			for (int i=0; i<=9; i++) if(Z[i]!=0) m=i;	//neues m bestimmen
			//m=Grad des Zaehler-Polys
		}	
		
		Rest = Z;		//Rest = das was noch im Zaehler steht!
		return Q;		//Quotient zurückgeben
	}

	//das Polynom in der gewünschten Darstellung ausgeben:
	public static void printPolynom(float[] Polynom) 
	{
		int Laenge=0;
		//Polynomlänge bestimmen (Wertigkeit):
		for (int i=0; i<=9; i++) if(Polynom[i]!=0) Laenge=i;
		
		//Wenn das Polynom Leer ist nix machen:
		if (Laenge==0 && Polynom[0]==0) return;
		
		//Diese Schleife behandelt alle sonderfälle die Auftreten können
		//damit der AusgabeString exakt den Vorgaben der Spezifikation
		//entspricht.
		
		for (int i=Laenge; i>=0; i--)
		{
			if (Polynom[i]==0) continue;	//Koef. = 0 ==> nix ausgeben
			
			if (i!=Laenge && Polynom[i] > 0) EprogIO.print("+"); //schreibe + ausser beim 1.
			if (Polynom[i] == -1 && i!=0) EprogIO.print("-");	//wenn Koef=-1 dann schreibe -
			if ((Math.abs(Polynom[i]) != 1) || (i==0) )	//Koef ungeleich -1 bzw +1
			{ 	//Wenn Ganzahlig dann schreibe den Koef als Integer:
				if (Polynom[i] % 1 == 0) EprogIO.print((int)Polynom[i]);
				else EprogIO.print(Polynom[i]); //ansonsten als float
			}
			if (i!=0) EprogIO.print("x"); //ausser bei X^0 x schreiben
			if (i>1) EprogIO.print(i); //Koef schreiben wenn > 1 
		}
	}

	//Haupprogramm (Main Methode)
	public static void main (String[] args)
	{
		float Quotient[] = new float[10];	
		
		String NennerString = EprogIO.readWord();		//Zaehler Polynom Einlesen
		String ZaehlerString = EprogIO.readWord();		//Nenner Polynom Einlesen

		//Ueberprüfen ob Strings kleiner 40 zeichen sind
		if ((NennerString.length() > 40) || (ZaehlerString.length() > 40)) 
			{Fehler = true;  Errors[3]=true;}
		
		try
		{
			//Zaehler Polynom in Array of int umwandeln:
			int[] ZaehlerPolynom = polyStringToIntArray(NennerString);
			//Nenner Polynom in Array of int umwandeln
			int[] NennerPolynom = polyStringToIntArray(ZaehlerString);
			//Polynom Divison Durchfühen
			Quotient = PolynomDivision(ZaehlerPolynom,NennerPolynom);
			
			{	//Ist der Rest=0?
				int RL=0; //Wert. des RestPolynoms:
				for (int i=0; i<=9; i++) if(Rest[i]!=0) RL=i;
				if (RL==0 && Rest[0]==0) KeinRest=true;	
			}
		}
		
		catch(Throwable e) // Alles Exceptions Auffangen
		{
			Fehler = true;	
			Errors[4] = true;
		}
		
		//zum Debuggen:
		//for(int i = 0; i < Errors.length; i++) EprogIO.println("E["+i+"]="+Errors[i]);
		
		if (!Fehler)	//Wenn kein fehler dann Polynome Ausgeben!
		{
			//DEBUG OPTION:
			//for (int i=0; i<=9; i++) EprogIO.println("Q["+i+"]="+Quotient[i]);
			
			printPolynom(Quotient); //Ausgabe des Ergebnis
			EprogIO.print(" ");
			if (KeinRest) EprogIO.println("0");
			else printPolynom(Rest);		//Ausgabe des Rest
			EprogIO.println();	
		}
		//Fehlermeldung Ausgeben:
		else EprogIO.println("FALSCHE EINGABE");
	}	
}