import java.util.*;

public class Polynome
{	private LinkedList monomes= new LinkedList();
		
	/** retourne le monome ŕ l'indice i de la liste */
	public Monome getMonome(int i) {
	return (Monome)(monomes.get(i));}
	
		
	/** Ajoute un monome m */
	public int Ajoute (Monome m) {
		int i=0;
		while (i<monomes.size() && getMonome(i).getDegre()!=m.getDegre()) i++;
		if (i<monomes.size()) 
			{double coef=getMonome(i).getCoef()+m.getCoef();
			  monomes.remove(i); 
			   if (coef!=0)
			   monomes.add(new Monome(coef,m.getDegre()));}
		else monomes.add(new Monome(m.getCoef(),m.getDegre()));
		return monomes.size();
	}
		
	 public String toString() {
	 if (monomes.size()==0) return "Polynome vide";
	 else {String resultat="P(x)="+getMonome(0).toString();
	 	for (int i=1;i<monomes.size();i++)
	 		{if (getMonome(i).getCoef()>=0) resultat=resultat+'+';
			 resultat=resultat+ getMonome(i).toString();
			}
		return resultat;}	 
	}	
	
	public double calcul(double x) {
		double resultat=0;
		for (int i=0;i<monomes.size();i++) {
			resultat=resultat+getMonome(i).calcul(x);}
		return resultat;
	}
	
	public double calculHorner(double x) {
		double resultat=0;
		double degre_precedent=0;
		Collections.sort(monomes);
		for (int i=0;i<monomes.size();i++) {
			Monome m=getMonome(i);
			for (int j=m.getDegre();j<degre_precedent;j++) resultat=resultat*x;
			resultat=resultat+m.getCoef();
			degre_precedent=m.getDegre();}
		for (int j=0;j<degre_precedent;j++) resultat=resultat*x;
		return resultat;
	}
		 
	 
	 public static void main(String[] args) {
	 	Polynome p=new Polynome();
		Monome m;
		do {m= new Monome(Keyboard.readDouble("Entrer le coefficient du monome:"),Keyboard.readInt("Entrer le degré du monome:"));
			p.Ajoute(m);}
		while (Keyboard.readString("Entrer un autre monome (O/N) :").equals("O"));
		System.out.println (p);
		double x;
		do {x=Keyboard.readDouble("Entrer la valeur de x :");
			System.out.println("P("+x+")="+p.calcul(x));
			System.out.println("P("+x+")="+p.calculHorner(x)+" (Horner)");
			}
		while (x!=0);
		}
		
}