C++ How to add polynomial using linked list

Question

Take a look at the code, what am I doing wrong in the operator overloading while adding polynomials (lists)? It's not printing the desired answer. e.g.

P1: 5x^12 + 2x^9 + 4x^7 + 6x^6 + 1x^3

P2: 7x^8 + 2x^7 + 8x^6 + 6x^4 + 2x^2 + 3^x + 40

Answer: 5x^12 + 2x^9 + 7x^8 + 6x^7 + 14x^6 + 6x^4 + 1x^3 + 2x^2 + 3^x + 40

What is the correct way to add them?

#include <stdio.h>
#include <iostream>

using namespace std;

//Node is defined
class node {
public:
    //value will contain data
    int value1;
    int value2;
    //next stores location
    node *next;

    //Default Constructor
    node()
    {
        value1 = 0;
        value2 = 0;
        next = NULL;
    }
};

//mylist is defined
class mylist {
public:

    //head will keep notice of beginning of the list
    node* head;

    //track number of nodes
    int count = 0;

    //default constructor
    mylist() {}

    //constructor


    //insert at beginning
    void insert_at_beginning(int new_value1, int new_value2)
    {
        //creating new node
        node *new_node = new node();

        //increasing count
        count++;

        //copying value to new_node
        new_node->value1 = new_value1;
        new_node->value2 = new_value2;
        //pointing head to new_node when we have empty list
        if (head == NULL)
        {
            head = new_node;
        }
        //when list isn't empty
        else
        {
            /* new_node->next points where heads points*/
            new_node->next = head;

            /* Updating head node to point to newly added node*/
            head = new_node;
        }
    }

    //inert node or item at Specific Location
    void insert_at_loc(int location, double new_val1, double new_val2)
    {
        //temp node to keep track of location
        node* temp = head;

        //x acts as counter
        int x = count;

        //check if location is valid or not
        if (count < location) {
            cout << ("\n --Invalid Location Node Can't be Added at this Location -- ") << endl;
        }
        else {
            //traversing thourgh list finding specific location to add node
            while (x != NULL) {
                if (x == (count - location + 2)) {

                    //found location now creating new node and fixing links
                    node *new_node1 = new node();

                    //increasing count
                    count++;
                    new_node1->value1 = new_val1;
                    new_node1->value2 = new_val2;
                    //new_node1->next points to temp->next
                    new_node1->next = temp->next;

                    //temp-next points to newly added new_node1
                    temp->next = new_node1;
                }
                else {
                    temp = temp->next;
                }
                x--;
            }

        }

    }

    //printing list
    void printList()
    {
        cout << endl << "Linked-List : ";
        node* temp = head;

        while (temp != NULL) {
            cout << temp->value2 << "x^" << temp->value1 << "--> ";
            temp = temp->next;
        }
    }

    void del(int del_loc) {

        //temp1 to keep track location
        node* t1 = head;

        //if location is head 
        if (del_loc <= 1) {
            head = t1->next;

            //free memory
            delete(t1);

            //decrementing count
            count--;
        }
        //location is other than head
        else if (del_loc < count) {
            for (int y = count; y != (count - del_loc + 2); y--) {
                t1 = t1->next;
            }
            //fixing links
            node* t2 = t1->next;
            t1->next = t2->next;

            //free memory
            delete t2;

            //decrementing count
            count--;
        }
        else {
            cout << "\n **Sorry Location Doesn't Exist **" << endl;
        }
    }

    //Display Number of Nodes
    void count_func() {
        cout << "\n\n No. of Nodes Present in Linked List : " << count << endl;
    }

    void mylist::operator+=(const mylist& l2) {
        node *temp_l1 = head;
        node *temp_l2 = l2.head;
        mylist answer;

        while ((temp_l1 != NULL) && (temp_l2 != NULL)) {
            if (temp_l1 != NULL && temp_l2 == NULL) {
                answer.insert_at_beginning(temp_l1->value1, temp_l1->value2);
                temp_l1 = temp_l1->next;
            }

            if (temp_l1 == NULL && temp_l2 != NULL) {
                answer.insert_at_beginning(temp_l2->value1, temp_l2->value2);
                temp_l2 = temp_l2->next;
            }

            if (temp_l1 != NULL && temp_l2 != NULL) {
                if (temp_l1->value1 == temp_l2->value1) {
                    answer.insert_at_beginning(temp_l1->value1, (temp_l1->value2+temp_l2->value2) );
                    if (temp_l1 != NULL)
                        temp_l1 = temp_l1->next;
                    if (temp_l2 != NULL)
                        temp_l2 = temp_l2->next;
                }
                else if (temp_l1->value1 > temp_l2->value1 ) {
                    answer.insert_at_beginning(temp_l1->value1, temp_l1->value2);
                    temp_l1 = temp_l1->next;

                }
                else if (temp_l1->value1 < temp_l2->value1) {
                    answer.insert_at_beginning(temp_l2->value1, temp_l2->value2);
                    temp_l2 = temp_l2->next;

                }
            }
        }
        node *temp_ans = answer.head;
        while (temp_ans != NULL) {
            cout << temp_ans->value2 << "z^" << temp_ans->value1 << "--> ";
            temp_ans = temp_ans->next;
        }

    }
};



int main() {

    //creating linked_list
    mylist linked_list;
    mylist linked_list_1;
    mylist linked_list_2;
    mylist linked_list_ans;
    int menu = 0;

    int list_1_exp = 0;
    int list_1_exp_check = -100;
    double list_1_coef;
    char list_1_menu = 0;

    cout << " *********************** Enter 1st Polynomial in Ascending Order w.r.t Exponential *********************** " << endl;

    while (list_1_menu != 'E' || list_1_menu != 'e') {

        cout << " \nWould you like to add term in 1st Polynomial (y or n): " << endl;
        cout << " Enter 'E' to exit: " << endl;
        cout << " Your Choice: ";
        cin >> list_1_menu;

        if (list_1_menu == 'Y' || list_1_menu == 'y') {

            cout << "Enter the Exponent for the term : ";
            cin >> list_1_exp;

            if (list_1_exp > list_1_exp_check || list_1_exp_check == -100) {
                list_1_exp_check = list_1_exp;
            }
            else if (list_1_exp <= list_1_exp_check) {
                cout << " Invalid Exponent for the term (can't be Equal or Less than Last Term) " << endl;
                cout << " Please Enter Exponent Greater than " << list_1_exp_check << endl;
                cout << " Enter the Exponent for the term : ";
                cin >> list_1_exp;
                list_1_exp_check = list_1_exp;
            }

            cout << "Enter the Coefficent for the term : ";
            cin >> list_1_coef;

            linked_list_1.insert_at_beginning(list_1_exp, list_1_coef);

            linked_list_1.printList();
            cout << " NULL" << endl << endl;
        }
        else if (list_1_menu == 'N' || list_1_menu == 'n') {
            break;
        }
        else if (list_1_menu == 'E' || list_1_menu == 'e') {
            break;
        }
    }

    //priting list
    linked_list_1.printList();
    cout << " NULL" << endl << endl;

    int list_2_exp = 0;
    int list_2_exp_check = -100;
    double list_2_coef;
    char list_2_menu = 0;

    cout << " \n *********************** Enter 2nd Polynomial in Ascending Order w.r.t Exponential ***********************" << endl;

    while (list_2_menu != 'E' || list_2_menu != 'e') {

        cout << " \nWould you like to add term in 2nd Polynomial (y or n): " << endl;
        cout << " Enter 'E' to exit: " << endl;
        cout << " Your Choice: ";
        cin >> list_2_menu;

        if (list_2_menu == 'Y' || list_2_menu == 'y') {

            cout << "Enter the Exponent for the term : ";
            cin >> list_2_exp;

            if (list_2_exp > list_2_exp_check || list_2_exp_check == -100) {
                list_2_exp_check = list_2_exp;
            }
            else if (list_2_exp <= list_1_exp_check) {
                cout << " Invalid Exponent for the term (can't be Equal or Less than Last Term) " << endl;
                cout << " Please Enter Exponent Greater than " << list_2_exp_check << endl;
                cout << " Enter the Exponent for the term : ";
                cin >> list_2_exp;
                list_2_exp_check = list_2_exp;
            }

            cout << "Enter the Coefficent for the term : ";
            cin >> list_2_coef;

            linked_list_2.insert_at_beginning(list_2_exp, list_2_coef);

            linked_list_2.printList();
            cout << " NULL" << endl << endl;
        }
        else if (list_2_menu == 'N' || list_2_menu == 'n') {
            break;
        }
        else if (list_2_menu == 'E' || list_2_menu == 'e') {
            break;
        }
    }

    //priting list
    linked_list_2.printList();
    cout << " NULL" << endl << endl;

    linked_list_1.printList();
    cout << " NULL" << endl << endl;


    cout << " Addition " << endl;

    linked_list_1 += (linked_list_2);


    cout << "\nFinal List" << endl;
    linked_list_ans.printList();


    //program success
    system("pause");
    return 0;

}

I think that logic I'm trying for addition makes sense but it's not working. In the majority of cases it works as in if I have equal terms in the polynomial with the same degrees. It works fine for that but not for all cases. Please help!

Answer 1

The loop condition (temp_l1 != NULL) && (temp_l2 != NULL)guarantees that temp_l1 != NULL && temp_l2 == NULL and temp_l1 == NULL && temp_l2 != NULL are always false, so the bodies of corresponding ifs are never executed. Take them out of the loop (and convert them to loops of course).

PS: to quickly find problems like this, use a debugger.

Answer 2

Why not keep it simple instead:

Create a map<int, int>. Traverse through P1 and P2, insert indices as key and put coefficient as value. Increment the value of entry if the index or power already exist in the map, else create new entry with the index as key. After finishing the traversal of both P1 and P2, the map will compose of entries with index as key and sum of coefficients for each power/index in P1 and P2 as corresponding value.