#include <stdio.h>
#include <stdlib.h>

typedef struct _node{
  int exp;
  double coeff;
  struct _node *next;
}node;

node *create_node(int e, double c){
  node *new;
  new = (node*)malloc(sizeof(node));
  new->exp = e;
  new->coeff = c;
  new->next = NULL;
  return new;
}

node* read_poly(node *p){
  int e; double c;

  node *new,*r,*s;
  
  while(1){
    scanf("%d", &e);

    if (e < 0)
      break;
    
    scanf("%lf", &c);

    new = create_node(e,c);
    
    if(p == NULL){
      p = new;
      continue;
    }
  
    s = p; r = NULL;
    while((s != NULL) && (s->exp > e)){
      r = s;
      s = s->next;
    }
    new->next = s;
    
    if(r == NULL)
      p = new;
    else
      r->next = new;
  
  }
  return p;
}

void print_term(double c, int e){
  if (e == 0)
    printf("%g", ((c>=0)?c:-c));
  else{
    if(c == 1 || c == -1)
      printf("x^{%d}", e);
    else
      printf("%g x^{%d}", ((c>=0)?c:-c), e);
  }
}

void print_poly(node *p){
  double c;

  if(p == NULL)
    return;
    
  if (p->coeff < 0) printf("- ");   print_term(p->coeff,p->exp);

  p = p->next;

  while(p != NULL){
    if (p->coeff < 0)
      printf(" - ");
    else
      printf(" + ");
    
    print_term(p->coeff,p->exp);
    p = p->next;
  }
  printf("\n");
}

node* add(node *p1, node *p2){
  node *q = NULL, *new, *t;
  
  while((p1 != NULL)&&(p2 != NULL)){
    if(p1->exp > p2->exp){
      new = create_node(p1->exp,p1->coeff);
      p1 = p1->next;
    }
    else if(p1->exp < p2->exp){
      new = create_node(p2->exp,p2->coeff);
      p2 = p2->next;
    }
    else{
      if(p1->coeff+p2->coeff != 0){
	new = create_node(p1->exp,p1->coeff+p2->coeff);
	p1 = p1->next; p2 = p2->next;
      }
      else{
	p1 = p1->next; p2 = p2->next;
	continue;
      }
    }
    if(q == NULL)
      q = new;
    else{
      t = q;
      while(t->next != NULL)
	t = t->next;
      t->next = new;
    }
  }
  t = q;
  while(t->next != NULL)
    t = t->next;
  while(p1 != NULL){
    new = create_node(p1->exp,p1->coeff);
    t->next = new;
    t = t->next;
    p1 = p1->next;
  }
  while(p2 != NULL){
    new = create_node(p2->exp,p2->coeff);
    t->next = new;
    t = t->next;
    p2 = p2->next;
  }
    
  return q;
}

node* subtract(node *p1, node *p2){
  node *q = NULL, *new, *t;
  
  while((p1 != NULL)&&(p2 != NULL)){
    if(p1->exp > p2->exp){
      new = create_node(p1->exp,p1->coeff);
      p1 = p1->next;
    }
    else if(p1->exp < p2->exp){
      new = create_node(p2->exp,-p2->coeff);
      p2 = p2->next;
    }
    else{
      if(p1->coeff-p2->coeff != 0){
	new = create_node(p1->exp,p1->coeff-p2->coeff);
	p1 = p1->next; p2 = p2->next;
      }
      else{
	p1 = p1->next; p2 = p2->next;
	continue;
      }
    }
    if(q == NULL)
      q = new;
    else{
      t = q;
      while(t->next != NULL)
	t = t->next;
      t->next = new;
    }
  }
  t = q;
  while(t->next != NULL)
    t = t->next;
  while(p1 != NULL){
    new = create_node(p1->exp,p1->coeff);
    t->next = new;
    t = t->next;
    p1 = p1->next;
  }
  while(p2 != NULL){
    new = create_node(p2->exp,-p2->coeff);
    t->next = new;
    t = t->next;
    p2 = p2->next;
  }
    
  return q;
}

node* multiply(node *p1, node *p2){
  node *q = NULL, *new, *t, *r, *s2;
  int e; double c;

  if(p1 == NULL || p2 == NULL){
    printf("Cannot multiply. Only one polynomial provided!\n\n");
    return NULL;
  }
  
  while(p1 != NULL){
    s2 = p2;
    while(s2 != NULL){
      e = p1->exp + s2->exp;
      c = (p1->coeff)*(s2->coeff);

      if(q == NULL){
	q = create_node(e,c);
	s2 = s2->next;
	continue;
      }
      
      t = q;
      while(t != NULL){
      	if(t->exp <= e)
	  break;
	r = t;
	t = t->next;
      }
      
      if(t != NULL && t->exp == e){
      	t->coeff += c;
	if(t->coeff == 0){
	  r->next = t->next;
	  free(t);
	}
      }
      else{
      	new = create_node(e,c);
      	new->next = t;
      	r->next = new;
      }
      s2 = s2->next;
      
    }
    p1 = p1->next;
  }
  return q;
}

int main(){
  int choice;
  node *p1 = NULL, *p2 = NULL, *q = NULL;
  printf("\n1. Add polynomials\n"
	 "2. Subtract polynomials\n"
	 "3. Multiply polynomials\n"
	 "4. Exit\n"
	 "\n***All polynomials will be read as a sequence of exponents (integers) and coefficients (reals). Negative integer entered as exponent indicates end of the sequence.\n\n");
  
  while(1){
    printf("\nChoice: ");
    scanf("%d", &choice);
    switch(choice){
    case 1: printf("\nWrite the first polynomial:\n   ");
      p1 = read_poly(p1);
      print_poly(p1);
      printf("Write the second polynomial:\n   ");
      p2 = read_poly(p2);
      print_poly(p2);
      q = add(p1,p2);
      printf("\nSum of the two polynomials is\n   ");
      print_poly(q);
      break;
    case 2: printf("\nWrite the first polynomial:\n   ");
      p1 = read_poly(p1);
      printf("Write the second polynomial:\n"   );
      p2 = read_poly(p2);
      q = subtract(p1,p2);
      printf("\nDifference of the two polynomials is\n"   );
      print_poly(q);
      break;
    case 3: printf("\nWrite the first polynomial:\n   ");
      p1 = read_poly(p1);
      printf("Write the second polynomial:\n   ");
      p2 = read_poly(p2);
      q = multiply(p1,p2);
      if(q != NULL){
	printf("\nProduct of the two polynomials is\n   ");
	print_poly(q);
      }
      break;
    case 4: printf("Bye!\n\n");
      exit(0);
    default: printf("Invalid choice!\n\n");
      break;
    }
  }
  return 0;
}