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

struct Node 
{
    int coeff;
    int exp;
    struct Node* next;
};

struct Node* insertTerm(struct Node* start, int coeff, int exp) 
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->coeff = coeff;
    newNode->exp = exp;
    newNode->next = NULL;

    if (start == NULL) 
    {
        return newNode;
    }

    struct Node* temp = start;
    while (temp->next != NULL) 
    {
        temp = temp->next;
    }
    temp->next = newNode;
    return start;
}

void displayPolynomial(struct Node* start) 
{
    struct Node* temp = start;
    if (temp == NULL) {
        printf("0\n");
        return;
    }
    
    while (temp != NULL) 
    {
        if (temp->coeff > 0 && temp != start) {
            printf(" + ");
        } else if (temp->coeff < 0) {
            if (temp == start) printf("-");
            else printf(" - ");
        }

        int absCoeff = abs(temp->coeff);
        
        if (temp->exp == 0) 
        {
            printf("%d", absCoeff);
        } 
        else if (temp->exp == 1) 
        {
            if (absCoeff == 1) printf("x");
            else printf("%dx", absCoeff);
        }
        else 
        {
            if (absCoeff == 1) printf("x^%d", temp->exp);
            else printf("%dx^%d", absCoeff, temp->exp);
        }

        temp = temp->next;
    }
    printf("\n");
}

struct Node* addPolynomials(struct Node* poly1, struct Node* poly2) 
{
    struct Node* result = NULL;
    
    while (poly1 != NULL && poly2 != NULL) 
    {
        if (poly1->exp > poly2->exp) 
        {
            result = insertTerm(result, poly1->coeff, poly1->exp);
            poly1 = poly1->next;
        } 
        else if (poly1->exp < poly2->exp) 
        {
            result = insertTerm(result, poly2->coeff, poly2->exp);
            poly2 = poly2->next;
        } 
        else 
        {
            int sumCoeff = poly1->coeff + poly2->coeff;
            if (sumCoeff != 0) 
            {
                result = insertTerm(result, sumCoeff, poly1->exp);
            }
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }

    while (poly1 != NULL) 
    {
        result = insertTerm(result, poly1->coeff, poly1->exp);
        poly1 = poly1->next;
    }

    while (poly2 != NULL) 
    {
        result = insertTerm(result, poly2->coeff, poly2->exp);
        poly2 = poly2->next;
    }

    return result;
}

void main() 
{
    struct Node* poly1 = NULL;
    struct Node* poly2 = NULL;
    struct Node* polySum = NULL;

    clrscr();

    poly1 = insertTerm(poly1, 3, 4);
    poly1 = insertTerm(poly1, 2, 3);
    poly1 = insertTerm(poly1, -4, 2);
    poly1 = insertTerm(poly1, 7, 0);

    poly2 = insertTerm(poly2, 5, 3);
    poly2 = insertTerm(poly2, 4, 2);
    poly2 = insertTerm(poly2, -5, 0);

    printf("P(x) = ");
    displayPolynomial(poly1);

    printf("Q(x) = ");
    displayPolynomial(poly2);

    polySum = addPolynomials(poly1, poly2);
    printf("\nP(x) + Q(x) = ");
    displayPolynomial(polySum);

    getch();
}