Using linked lists to add polynomials? Assistance

Question

Hello to anyone reading this. My problem with this program is that I seem to not be understanding how to add 2 polynomials which are entered sequentially into a linked list. I can add new polynomials or read the ones that are currently entered, but the adding and subtracting has given me issues. Here is what I currently have:

#include <iostream>
#include <cmath>
#include <cstddef>

using namespace std;

typedef float polyType;

struct polyInfo
{
int number;
int power;
polyInfo* link;
};

//typedef polyInfo* polyPtr;
//polyPtr head;
//polyPtr currPtr;
//polyPtr newNodePtr;

class Polynomial
{
private:
    polyInfo *head;
    int maxpow = 0;
public:
    Polynomial(){}

    void createPoly(int n, int p)
    {
        polyInfo *temp = new polyInfo();
        temp->power = p;
        temp->number = n;
        temp->link = head;
        head = temp;
        if (maxpow < p)
        {
            maxpow = p;
        }
    }

    void getPoly()
    {
        polyInfo *temp = head;
        while (temp != NULL)
        {
            if (temp->number != 0)
            {
                cout << temp->number << "x^" << temp->power << " ";
            }
            temp = temp->link;
        }
        cout << "\n";
    }

    void addPoly()
    {
        polyInfo *temp = head;
        while (temp != NULL)
        {
            if (temp->number != 0)
            {
                polyInfo *temp2 = head;
                temp2 = temp2->link;
                if (temp2->link != NULL)
                {
                    if (temp->power == temp2->power)
                    {
                        temp->number = (temp->number)+(temp2->number);
                        temp2->number = 0;
                        temp = temp->link;
                    }
                }
                else
                {
                    temp = NULL;
                }
            }
        }
    }

    void subtractPoly()
    {}
};

int main()
{
    int menuNum;//used to see which menu option user chooses
    int mainPower;
    int mainNumber;

    Polynomial mainPoly;
    bool menu = true;

    while (menu)
   {
       cout << "Enter 1 to create new polynomial"
            << "\nEnter 2 to read a polynomial"
            << "\nEnter 3 to add polynomials"
            << "\nEnter 4 to subtract polynomials"
            << "\nEnter 5 to end program :";
       cin >> menuNum;

       switch(menuNum)
       {
           case 1:
                  cout << "\nEnter the coefficient: ";
                  cin >> mainNumber;
                  cout << "\nEnter the exponent of X: ";
                  cin >> mainPower;
                  mainPoly.createPoly(mainNumber,mainPower);
                  break;
           case 2:
                  mainPoly.getPoly();
                  break;
           case 3:
                  mainPoly.addPoly();
                  break;
           case 4:
                  mainPoly.subtractPoly();
                  break;
           case 5:
                  cout << "End of program\n";
                  menu = false;
           default:
                  cout << "\nInvalid Input, please try again\n\n";
                  break;
       }
    }
    return 0;
}

I apologize for having almost no comments in the code. I usually go back through and add them in afterwards. I run a menu in main that allows you to enter in a new polynomial, read them out, add them, or subtract them. I have the methods for inputting a new one and reading them out to the user. I have gotten this far on the code for my addition and it does not work. The problem cannot be fixed with two separate lists though, which is the majority of what I've found online. It has to be done through the one list which contains a number and power in each node.

Answer 1

First of all: You are dealing with user input, which always could be invalid! If user inputs e. g. x7, operator>> will fail and cin will remain in error state (making subsequent stream operations fail as well), so you will be caught in an endless loop doing one and the same task again and again, depending on last successful input. If right the first user input is invalid, you don't get menuItem initialised at all and thus you even run into undefined behaviour! So:

if(std::cin >> menuItem)
{
    // good case
}
else
{
    // bad case!
    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

Minimal handling: clear error state and ignore the input that caused it, starting new in next loop. You might additionally inform the user about what he/she did...

Prefer appropriate names: getPoly prints out the polynomial to console, so rather rename it to printPoly. Similarly, your addPoly function looks rather like a normalize function (if though, yet needing some fixes...).

If you really want to add polynomials, well, then you need two of them! Then you need to decide: do you want to add the other polynomial to the current one or do you want to create a new one containing the result. This will influence the interface... You might want to create both. Be aware that for these operations, there are default function names: operator+ and operator+=. If you implement these, you can write code like this:

Polynomial x, y;
Polynomial z = x + y;
x += y;

Now you seem to allow to store polynomial elements in arbitrary order. This will require you to rely on O(n²) algorithms on addition and subtraction. Not that a good idea... Better: keep your polynomials normalised in the following meaning:

• If number is 0, don't store an element for. If an element gets null during operations, drop it.
• Keep elements sorted, addition and subtraction get linear complexity this way, and if first element is biggest element, you even can spare the maxpow member (it is equivalent to head->power then).

With all above, I recommend another interface. Usage afterwards will be:

// create an initial polynomial:
Polynomial x(1, 3);
x += Polynomial(2, 2);
x += Polynomial(3, 1);
x.print();
// output: 3x^1 + 2x^2 + 3x^1

The following code is not complete, you'll need to contribute some additions yourself (e. g. appropriate constructors for PolyInfo struct; by the way: make this one an inner class!)...

Polynomial(int n = 0, int p = 0)
    : head(nullptr)
{
    if(n)
    {
        head = new PolyInfo(n, p);
    }
}

static Polynomial operator+(Polynomial const& x, Polynomial const& y)
{
    PolyInfo* result;
    PolyInfo* tmp = nullptr;
    PolyInfo* ix = x.head;
    PolyInfo* iy = y.head;
    while(ix || iy)
    {
        if(ix && (!iy || ix->power > iy->power))
        {
            result = new PolyInfo(*ix);
            ix = ix->link;
        }
        else if(iy && (!ix || iy->power > ix -> power))
        {
            result = new PolyInfo(*iy);
            iy = iy->link;
        }
        else
        {
            int n = ix->number + iy->number;
            ix = ix->link;
            iy = iy->link;
            if(n == 0)
                // ignore this node!!!
                continue;
            result = new PolyInfo(n, ix->power);
        }
        result->link = tmp;
        tmp = result;
    }
    // yet in  r e v e r s e  order!
    result = nullptr;
    while(tmp)
    {
        PolyInfo* next = tmp->link;
        tmp->link = result;
        result = tmp;
        tmp = next;
    }
}

Polynomial& operator+=(Polynomial const& other)
{
    *this = *this + other;
    return *this;
}

First step done...

Pretty sure you do not want to repeat this code for operator-, so we might have a common function, so, make the current operator+ private and rename it and add an additional parameter to:

static Polynomial calculate
(
    Polynomial const& x, Polynomial const& y,
    int(*op)(int, int)
)
{ /* ... */ }

There now is yet one single line to change (in the case of two nodes with equal power):

int n = op(ix->number, iy->number);

Now add two new operators:

static Polynomial operator+(Polynomial const& x, Polynomial const& y)
{
    return calculate(x, y, [](int x, int y) { return x + y; });
}
static Polynomial operator-(Polynomial const& x, Polynomial const& y)
{
    return calculate(x, y, [](int x, int y) { return x - y; });
}

Now, for this working, we yet absolutely need a copy constructor and copy assignment, and to prevent memory leaks; a destructor (see rule of three) (but see below!!!):

Polynomial(Polynomial const& other)
{
    // make a deep copy by copying all elements
    // easiest is creating the copy in inverse order and
    // then reverting it similar as in calculate
    // have a common function for then!
}

Polynomial& operator=(Polynomial const& other)
{
    this->~Polynomial();
    new(this)Polynomial(other);
    return *this;
}

OK, above assignment operator is unusual and inefficient (but at least not incorrect, and it is easy to implement...), it deletes the current object and recreates it via the copy constructor. This will result in deleting all nodes and recreating them as needed. Better: reuse the nodes that exist already, copying the values from the other polynomial into. Then either create copies of the ones existing more in the other one or delete those that exist more in the current one. Leaving this as excercise. However, you then can make use of it in the copy constructor instead:

Polynomial(Polynomial const& other)
    : Polynomial()
{
    *this = other;
}

The destructor simply will delete all nodes existing.

For completeness: Rule of five...

It is not a must, but offers great optimisation opportunities:

Polynomial(Polynomial&& other)
    : Polynomial()
{
    std::swap(this->head, other->head);
    // swaps nullptr into other...
}

Polynomial& operator=(Polynomial&& other)
{
    std::swap(this->head, other->head);
    // huh, memory leak?
    // no, other will delete contents previously owned by this
    // as soon as running out of scope...
    return *this;
}

This looks like an excercise task, so you might not be allowed to, but if you are, use a STL container instead of your own linked list: e. g. std::list for a doubly linked list (makes iteration easier, especially avoids creation in inverse order and reverting afterwards), std::forward_list for a singly linked one, or even std::vector. This will relieve you from all memory management above, and default copy/move constructor/assignment and destructor would fit well for you (as the corresponding container equivalents will be called implicitly)...

Finally: All of above code is untested, there might be bugs in, but it should show you the way.