Question

A polynomial can be represented using linked list, storing coefficient and exponent of each component of polynomial in a node of it. Write a class in C++ to implement polynomials in three variables x, y and z (a polynomial may also have a constant term). Your class should implement methods for following operations.
• Add two polynomials.
• Multiply two polynomials.
Use a two way header list for implementation. Your program should print the coefficient and exponent of each component of output polynomial.

Answer 1

#include <bits/stdc++.h>

using namespace std;

class Term

{

public:

    int x_expo;

    int coeff;

    int y_expo;

    int z_expo;

    Term *next;

};

// function to create a node in the linked list

void createNode(Term **head, int c, int xe, int ye, int ze)

{

    Term *newNode = new Term();

    Term *curr = *head;

    newNode->coeff = c;

    newNode->x_expo = xe;

    newNode->y_expo = ye;

    newNode->z_expo = ze;

    newNode->next = NULL;

    if (*head == NULL)

    {

        *head = newNode;

        return;

    }

    while (curr->next != NULL)

        curr = curr->next;

    curr->next = newNode;

    return;

}

void removeDuplicates(Term *head)

{

    Term *p1, *p2, *dup;

    p1 = head;

    // Pick elements one by one

    while (p1 != NULL && p1->next != NULL)

    {

        p2 = p1;

        // Compare the picked element with rest of the elements

        while (p2->next != NULL)

        {

            if (p1->x_expo == p2->next->x_expo && p1->y_expo == p2->next->y_expo && p1->z_expo == p2->next->z_expo)

            {

                // Add their coefficients and put it in 1st element

                p1->coeff = p1->coeff + p2->next->coeff;

                dup = p2->next;

                p2->next = p2->next->next;

                // remove the 2nd element

                delete (dup);

            }

            else

                p2 = p2->next;

        }

        p1 = p1->next;

    }

}

Term *addPolynomials(Term *p1, Term *p2)

{

    Term *p = NULL;

    while (p1 != NULL && p2 != NULL)

    {

        // if the powers of all variables is the same we add the coefficients and if its not we create two separate nodes for the two powers

        if (p1->x_expo == p2->x_expo && p1->y_expo == p2->y_expo && p1->z_expo == p2->z_expo)

        {

            createNode(&p, p1->coeff + p2->coeff, p1->x_expo, p1->y_expo, p1->z_expo);

            p1 = p1->next;

            p2 = p2->next;

        }

        else

        {

            createNode(&p, p1->coeff, p1->x_expo, p1->y_expo, p1->z_expo);

            createNode(&p, p2->coeff, p2->x_expo, p2->x_expo, p2->x_expo);

            p1 = p1->next;

            p2 = p2->next;

        }

    }

    // if there are remaining elements in the polynomials we add it to the resulting polynomials

    while (p1 != NULL || p2 != NULL)

    {

        if (p1 != NULL)

        {

            createNode(&p, p1->coeff, p1->x_expo, p1->y_expo, p1->z_expo);

            p1 = p1->next;

        }

        if (p2 != NULL)

        {

            createNode(&p, p2->coeff, p2->x_expo, p2->x_expo, p2->x_expo);

            p2 = p2->next;

        }

    }

    // to remove the duplicate elements present in the resulting polynomials

    removeDuplicates(p);

    return p;

}

// function to multiply two polynomials

Term *multiplyPolynomials(Term *p1, Term *p2)

{

    Term *poly3 = NULL;

    // Create two pointer and store the address of 1st and 2nd polynomials

    Term *ptr1, *ptr2;

    ptr1 = p1;

    ptr2 = p2;

    while (ptr1 != NULL)

    {

        while (ptr2 != NULL)

        {

            int coeff, x_power, y_power, z_power;

            // Multiply the coefficient of both polynomials and store it in coeff

            coeff = ptr1->coeff * ptr2->coeff;

            // Add the corresponding powers of both polynomials and store it in power

            x_power = ptr1->x_expo + ptr2->x_expo;

            y_power = ptr1->y_expo + ptr2->y_expo;

            z_power = ptr1->z_expo + ptr2->z_expo;

            createNode(&poly3, coeff, x_power, y_power, z_power);

            ptr2 = ptr2->next;

        }

        ptr2 = p2;

        ptr1 = ptr1->next;

    }

    // to remove duplicate elements in the linked list

    removeDuplicates(poly3);

    return poly3;

}

// function to print polynomials

void printPoly(Term *head)

{

    while (head != NULL)

    {

        cout << head->coeff << "x" << head->x_expo << "y" << head->y_expo << "z" << head->z_expo;

        head = head->next;

        if (head != NULL)

            cout << " + ";

    }

}

int main()

{

    Term *p1 = NULL, *p2 = NULL, *p = NULL, *m = NULL;

    // creating the first polynomial

    createNode(&p1, 7, 2, 2, 2);

    createNode(&p1, 5, 1, 1, 1);

    createNode(&p1, 3, 0, 0, 0);

    // creating the second polynomial

    createNode(&p2, 8, 1, 1, 1);

    createNode(&p2, 9, 2, 2, 2);

    createNode(&p2, 3, 0, 0, 0);

    cout << "POLYNOMIAL 1 = ";

    printPoly(p1);

    cout << endl;

    cout << "POLYNOMIAL 2 = ";

    printPoly(p2);

    cout << endl;

    cout << "ADDITION = ";

    p = addPolynomials(p1, p2);

    printPoly(p);

    m = multiplyPolynomials(p1, p2);

    cout << endl;

    cout << "MULTIPLICATION = ";

    printPoly(m);

    return 0;

}

//SAMPLE OUTPUT

******************************************************************************************
PLEASE LIKE IT RAISE YOUR THUMBS UP
IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT SECTION
******************************************************************************************