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

struct node {
    int pow,coeff;
    struct node* next;
};


void create(int coeff, int pow, struct node** head) {
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->pow = pow;
    newNode->coeff = coeff;
    newNode->next = NULL;
    if(*head == NULL) {
        *head = newNode;
    } else {
        struct node* cur = *head;
        while(cur->next != NULL) {
            if(cur->pow == pow) {
                cur->coeff = coeff;
                return;
            } else
                cur = cur->next;
        }
        if(cur->pow == pow)
            cur->coeff = coeff;
        else {
            cur->next = (struct node*) malloc(sizeof(struct node));
            cur->next = newNode;
        }
    }
}

struct node* add(struct node* p1, struct node* p2) {
    struct node* res = NULL;
    while(p1 && p2) {
        if(p1->pow > p2->pow) {
            create(p1->coeff, p1->pow, &res);
            p1 = p1->next;
        }
        else if(p2->pow > p1->pow) {
            create(p2->coeff, p2->pow, &res);
            p2 = p2->next;
        } 
        else {
            create(p1->coeff+p2->coeff, p1->pow, &res);
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    if(p1 || p2) {
        if(p1) {
            create(p1->coeff, p1->pow, &res);
            p1 = p1->next;
        }
        if(p2) {
            create(p2->coeff, p2->pow, &res);
            p2 = p2->next;
        }
    }
    return res;
}

void display(struct node* head) {
    struct node* cur = head;
    while(cur->next != NULL) {
        printf("%d x^ %d + ", cur->coeff, cur->pow);
        cur = cur->next;
    }
    printf("%d x^ %d", cur->coeff, cur->pow);
    printf("\n");
}

int main()
{
    struct node* p1 = NULL, *p2 = NULL, *res = NULL;
    int cn,pn,n=1,poly,dp, choice;
    while(1)
    {
      printf("\n1.Add an Expression\n2.Add\n3.Display\n0.Exit\nEnter your choice: ");
      scanf("%d",&choice);
      switch(choice)
      {
        case 1:
            printf("\nEnter an Choice Polynomial 1 or 2:");
            scanf("%d",&poly);
            printf("\nEnter Cofficient: ");
            scanf("%d",&cn);
            printf("\nEnter Power: ");
            scanf("%d",&pn);
            if(poly==1)
                create(cn,pn,&p1);
            else if(poly==2)
                create(cn,pn,&p2);
            break;
        case 2:
            if(p1||p2) {
                res = add(p1, p2);
                display(res);
            } else
                printf("Polynomials are empty\n");
            break;
        case 3:
            printf("\n1.Display(p1)\n2.Display(p2)\n3.Diplay(res)\nEnter choice: ");
            scanf("%d",&dp);
            if(dp==1) {
                if(p1 != NULL)
                    display(p1);
                else
                    printf("Polynomial 1 is empty\n");
            }
            else if(dp==2)
                if(p2 != NULL)
                    display(p2);
                else
                    printf("Polynomial 2 is empty\n");
            else
                if(res != NULL)
                    display(res);
                else
                    printf("Addition is required\n");
            break;
        case 0:
            return 0;
        default:
            printf("\nInvalid Input\n");
      }
    }
    return 0;
}