Addition Of Polynomials Using Linked List

Link Copied To Clipboard !

addition-of-polynomials-using-linked-list Data Structures

Given two polynomials, represented by a linked list, write a function to add these polynomials and set the result to new polynomial represented by a linked list.

Adding polynomials means adding the coefficients of polynomial terms having equal power and appending the remaining terms of both polynomials.

Addition Of Polynomials Using C++ | Linked List Implementation


#include<iostream>
using namespace std;

class Node{
    private:
        int coeff;
        int power;
        char sign;
        Node* next;
        friend class Polynomial;
};

class Polynomial{
    private:
        Node* head = NULL;

        void sort(){
            if(this->head == NULL) return;
            Node* tmp = head;
            bool sorted =  true;
            while(sorted){
                sorted = false;
                Node* inner = head;
                while(inner->next != NULL){
                    if(inner->power < inner->next->power){
                        int tmpCoeff = inner->coeff;
                        int tmpPower = inner->power;
                        char tmpSign = inner->sign;

                        inner->coeff = inner->next->coeff;
                        inner->power = inner->next->power;
                        inner->sign = inner->next->sign;

                        inner->next->coeff = tmpCoeff;
                        inner->next->power = tmpPower;
                        inner->next->sign = tmpSign;

                        sorted = true;
                    }
                    inner = inner->next;
                }
            }
        }
    public:
        Polynomial(){
            this->head = NULL;
        }

        void create(){
            this->head = NULL;

            int coeff, power;
            char again = 'n';
            do{
                cout<<"enter coefficient"<<endl;
                cin>>coeff;
                cout<<"enter power"<<endl;
                cin>>power;

                Node* node = new Node[1];
                node->coeff = coeff;
                node->power = power;
                node->sign = coeff < 0 ? '-' : '+';
                if(this->head == NULL){
                    this->head = node;
                }else{
                    Node* tmp = this->head;
                    while(tmp->next != NULL){
                        tmp = tmp->next;
                    }
                    tmp->next = node;
                }

                sort();

                do{
                    cout<<"enter another node ? y/n"<<endl;
                    cin>>again;
                }while(again != 'n' && again != 'y');
                
            }while(again != 'n');
        }

        Polynomial add(Polynomial& p){
            Node* a = this->head;
            Node* b = p.head;
            Polynomial* result = new Polynomial[0];
            bool compared = false;
            while(a != NULL){
                compared = false;
                b = p.head;
                while(b != NULL){
                    if(b->power == a->power){
                        Node* addedNode = new Node[1];
                        addedNode->power = b->power;
                        addedNode->next = NULL;
                        addedNode->coeff = a->coeff + b->coeff;
                        addedNode->sign = addedNode->coeff < 0 ? '-': '+';
                        if(result->head == NULL){
                            result->head = addedNode;
                        } else{
                            Node* shifted = result->head;
                            while(shifted->next != NULL){
                            shifted = shifted->next;
                            }
                            shifted->next = addedNode;
                        }
                        compared = true;
                    }
                    b = b->next;
                }
                if(!compared){
                    Node* addedNode = new Node[1];
                    addedNode->power = a->power;
                    addedNode->coeff = a->coeff;
                    addedNode->sign = a->sign;
                    addedNode->next = NULL;
                   if(result->head == NULL){
                       result->head = addedNode;
                   } else{
                       Node* shifted = result->head;
                       while(shifted->next != NULL){
                           shifted = shifted->next;
                       }
                       shifted->next = addedNode;
                   }
                }
                a = a->next;
            }
            //remaining from b
            b = p.head;
            bool exists = false;
            while(b != NULL){
                a = result->head;
                while(a != NULL){
                    if(b->power == a->power){
                        exists = true;
                    }
                    a = a->next;
                }
                if(!exists){
                    Node* toAdd = new Node[1];
                    toAdd->power = b->power;
                    toAdd->coeff = b->coeff;
                    toAdd->sign = b->sign;
                    toAdd->next = NULL;
                   if(result->head == NULL){
                       result->head = toAdd;
                   } else{
                       Node* shifted = result->head;
                       while(shifted->next != NULL){
                           shifted = shifted->next;
                       }
                       shifted->next = toAdd;
                   }
                }
                b = b->next;
            }
            sort();
            return *result;
        }

        void display(){
            if(this->head == NULL){
                cout<<"Polynomial Not Set !"<<endl;
                return;
            }else{
                Node* tmp = head;
                char sign;
                while(tmp != NULL){
                    if(tmp == head){
                        cout<<tmp->coeff<<"x^"<<tmp->power<<" ";
                    }else{
                        cout<<tmp->sign<<abs(tmp->coeff)<<"x^"<<tmp->power<<" ";
                    }
                    tmp = tmp->next;
                }
                cout<<endl;
            }
        }

        // ~Polynomial(){
        //     delete head;
        //     cout<<"head destroyed !"<<endl;
        // }
        
};

int main(){
    Polynomial p1, p2;
    bool exit = false;
    do{
        cout<<"===================================="<<endl;
        cout<<"select option :"<<endl;
        cout<<"1: set first polynomial"<<endl;
        cout<<"2: set second polynomial"<<endl;
        cout<<"3: display two polynomials"<<endl;
        cout<<"4: add two polynomials"<<endl;
        cout<<"5: for exit"<<endl;
        int ch;
        cin>>ch;
        cout<<"===================================="<<endl;
        switch(ch){
            case 1:
                p1.create();
                break;
            case 2:
                p2.create();
                break;
            case 3:
                p1.display();
                p2.display();
                break;
            case 4:
                cout<<"result of addition is:"<<endl;
                p1.add(p2).display();
                break;
            case 5:
                exit = true;
                cout<<"exiting..."<<endl;
                break;
            default:
                cout<<"invalid selection !"<<endl;
                break;
        }
    }while(!exit);
    return 0;
}

Feel free to modify the code as you like.


You May Also Like