Linked Lists

[scuzzo]

As with most of my work I have managed to make it through most of the work assigned to me except I always have one problem that I can't fix. Here is a program that takes in two polynomials and then allows you to add or subtract them. My problem is that if the polynomials are put in so that the exponent on one starts out as being higher that the initial exponent of the other the lists will not advance through the nodes. Can anyone point me to where the problem is, give me some ideas on how to fix it, anything?

#include <string>
#include <iostream>
using namespace std;
struct TermType
{
	int coefficient;
	int exponent;
	bool NegCoef;

	TermType* next;		
};

class Polynomial		
{
private:
	TermType* head;
	
public:
	// default constructor: create an empty polynomial
	Polynomial();				
// copy constructor: use the content of p1 to create a polynomial
	Polynomial(const Polynomial& p1);		
// release dynamic memory related to the polynomial
	~Polynomial();				
// assign the content of p1 to a polynomial
	void operator=(const Polynomial& p1);
// add a polynomial
	void operator+=(const Polynomial& p1);
// subtract a polynomial
	void operator-=(const Polynomial& p1); 
// read a polynomial
	void read();
// output a polynomial
	void print();
//new input function
	void insertTerm(bool,int,int);
};

Polynomial::Polynomial()
{
	head=NULL;
}
Polynomial::~Polynomial()
{
	TermType* newTerm=head;
	TermType* current=head;
	while(current != NULL)
  {
	  current = current->next;
      delete newTerm;
      newTerm=current;
  }



}
void Polynomial::operator-=(const Polynomial& p1)
{
	TermType* poly1=head;
	TermType* poly2=p1.head;
	int counter=0;
	while ((poly1!=NULL)||(poly2!=NULL))
	{
		if (poly2==NULL&&poly1!=NULL)
		{
			if (poly1->coefficient>0)
				cout<<"+";
			cout<<poly1->coefficient<<"x^"<<poly1->exponent;
			poly1=poly1->next;
		}
		if (poly1==NULL&&poly2!=NULL)
		{
			if (poly2->coefficient>0)
				cout<<"+";
			cout<<poly2->coefficient<<"x^"<<poly2->exponent;
			poly2=poly2->next;
		}
		if (poly1!=NULL&&poly2!=NULL)
		{
			if (poly1->exponent==poly2->exponent)
				{
					if(poly1->coefficient+poly2->coefficient>0)
						cout<<"+";
					cout<<poly1->coefficient-poly2->coefficient<<"x^"<<poly1->exponent;
							if (poly1!=NULL)
								poly1=poly1->next;
							if (poly2!=NULL)
								poly2=poly2->next;
							continue; 
				}
			if (poly1->exponent>poly2->exponent)
				{
					if (poly1->coefficient>0)
						cout<<"+";
					cout<<poly1->coefficient<<"x^"<<poly1->exponent;
						poly2=poly2->next;
					continue;
				}
			if (poly2->exponent>poly1->exponent)
				{
					if (poly2->coefficient>0)
						cout<<"+";
					cout<<poly2->coefficient<<"x^"<<poly2->exponent;
						poly1=poly1->next;				
					continue;
				}			
		}
	}
}
void Polynomial::operator+=(const Polynomial& p1)
{
	TermType* poly1=head;
	TermType* poly2=p1.head;
	int counter=0;
	while ((poly1!=NULL)||(poly2!=NULL))
	{
		if (poly2==NULL&&poly1!=NULL)
		{
			if (poly1->coefficient>0)
				cout<<"+";
	//		if (poly1->coefficient<0)
	//			cout<<"-";
			cout<<poly1->coefficient<<"x^"<<poly1->exponent;
			poly1=poly1->next;
		}
		if (poly1==NULL&&poly2!=NULL)
		{
			if (poly2->coefficient>0)
				cout<<"+";
			cout<<poly2->coefficient<<"x^"<<poly2->exponent;
			poly2=poly2->next;
		}
		if (poly1!=NULL&&poly2!=NULL)
		{
			if (poly1->exponent==poly2->exponent)
				{
					if(poly1->coefficient+poly2->coefficient>0)
						cout<<"+";
					cout<<poly1->coefficient+poly2->coefficient<<"x^"<<poly1->exponent;
							if (poly1!=NULL)
								poly1=poly1->next;
							if (poly2!=NULL)
								poly2=poly2->next;
							continue; 
				}
			if (poly1->exponent>poly2->exponent)
				{
					if (poly1->coefficient>0)
						cout<<"+";
					cout<<poly1->coefficient<<"x^"<<poly1->exponent;
						poly2=poly2->next;
					continue;
				}
			if (poly2->exponent>poly1->exponent)
				{
					if (poly2->coefficient>0)
						cout<<"+";
					cout<<poly2->coefficient<<"x^"<<poly2->exponent;
						poly1=poly1->next;				
					continue;
				}			
		}
	}
}
void Polynomial::insertTerm(bool negCoef, int coef, int exp)
{
	cout << "begin insert!" << endl;
	cout << negCoef << "    " << coef << "    " << exp << endl;

	TermType* newTerm = new TermType;
	if (negCoef == 1)
		newTerm->coefficient = 0 - coef;
	else
		newTerm->coefficient = coef;
	newTerm->exponent = exp;
	newTerm->next = NULL;

	TermType* current = head;
	if (head == NULL)
		head = newTerm;
	else
	{
		while (current->next != NULL)
		current=current->next;
		current->next = newTerm;
	}
	cout << "end insert!" << endl;
}
//read a polynomial
void Polynomial::read()
{
	string s;
	cout << "Enter a term (ex: +4x^3): ";
	cin >> s;
	int index = 0;
	bool firstTerm = 1;
	bool nowExp = 0;
	bool negativeCoef = 0;
	int coef = 0;
	int exp = 0;

	while (s[index] != '#')
	{
		cout << "char : " << s[index] << endl;
		if (s[index] == '+' || s[index] == '-')
		{
			cout << "+-" << endl;
			if (firstTerm == 0)
				{
					if (coef != 0)
					insertTerm(negativeCoef, coef, exp);
				}
			else
			{
				firstTerm = 0;
			}
			nowExp = 0;
			if (s[index] == '-')
				negativeCoef = 1;
			else
					negativeCoef = 0;
				coef = 0;
				exp = 0;
			}
			else if (s[index] == 'x')
			{
				cout << "x" << endl;
				if (s[index+1] != '^')
					{
						cout << "Incorrect formula!" << endl;
						head = NULL;
						break;
					}
			}
			else if (s[index] == '^')
			{
				cout << "^" << endl;
				nowExp = 1;
			}
			else if (s[index]>='0' && s[index]<='9')
			{
				cout << "number" << endl;
				if (nowExp == 0)
				coef = coef*10 + (s[index]-48);
				else
				exp = exp*10 + (s[index]-48);
			}
			else
			{
				cout << "The formula contains invalid characters: " << s[index] << endl;
				head = NULL;
				break;
			}
			index++;
		}
		if (coef != 0)
		insertTerm(negativeCoef, coef, exp);
		cout << "done!"<< endl;
}
void Polynomial::print()
{
	TermType* newTerm=head;
	while (newTerm != NULL)
	{
		if (newTerm->coefficient>0)
			cout<<"+";
		cout<<newTerm->coefficient<<"x^"<<newTerm->exponent;
		newTerm=newTerm->next;
	}
	cout << endl;
}
int main()
{
	Polynomial p, p1;	
	
		char option;
do //setting up a menu
	{
		
		cout << endl << endl << "Choose from:" << endl << endl;
		cout << "1. Enter first polynomial:" << endl;
		cout << "2. Enter second polynomial:" << endl;
		cout << "3. Print first polynomial:" << endl;
		cout << "4. Print second polynomial:"<<endl;
		cout << "5. Add polynomials:"<<endl;
		cout << "6. Subtract Polynomials:"<<endl;
		cout << "9. Exit:"<<endl;
		cin >> option;

		switch (option)
		{
		case '1':
			p.read();
			break;
		case '2':
			p1.read();
			break;
		case '3':
			p.print();
			break;
		case '4':
			p1.print();
			break;
		case '5':
			p+=(p1);
			break;
		case '6':
			p-=(p1);
			break;
		case '9':
			
		default:
			cout << "invalid input!!! Try it again." << endl;
		}
	} while (option != '9');
	return 0;
}

[helios]

My problem is that if the polynomials are put in so that the exponent on one starts out as being higher that the initial exponent of the other the lists will not advance through the nodes.

Sort them correctly before starting.

[scuzzo]

I am allowed to assume that the polynomials will be put in in correct order (ie. +4x^4+3x^3) with the largest exponent starting out the polynomial going to the smallest.

[helios]

So what's the problem, then?

[scuzzo]

My problem is that if the polynomials are put in so that the exponent on one starts out as being higher that the initial exponent of the other the lists will not advance through the nodes. Can anyone point me to where the problem is, give me some ideas on how to fix it, anything?

I just can't figure out why it's not advancing in this case.

[jsmith]

This doesn't directly solve your problem, but IMHO, you really should write some helper functions.

For example, write a function that returns the coefficient for a given term in a polynomial. If the coefficient does not exist, return 0. This will allow you to greatly simplify your code.

Another suggestion: if X and Y are integers, then X - Y can be written as X + (-Y). Therefore, your operator-= could simply negate the coefficients of the right-hand side then call operator+=. This will reduce your code by 40%. (As it stands now, every bug in operator-= most likely exists in operator+= and vice versa because the functions are so similar).

A third suggestion: neither operator+= nor operator-= should output the polynomial. write operator<< or a print function (if you are not familiar with writing operator<<) instead. This will further simplify operator+=.

A fourth suggestion, as a matter of writing code that is intuitive to use: if X, Y, and Z are integers, then in C++ I can write the line of code X = ( Y += Z ); which adds Z to Y, then assigns the new value of Y to X. Your declaration of operator+= and operator-= do not allow me to do this, because both return void. Rather, they should both return a Polynomial& (and be *this).

A fifth suggestion, which I'm sure you aren't allowed to do, but just in case... use std::vector<> rather than a custom linked list to hold the coefficients; this simplifies traversal of the coefficients and eliminates all the memory management you have to deal with by using a custom linked list implementation.

A sixth suggestion, in case the previous one won't work for you: write a dedicated linked list class and have Polynomial contain one. Now the linked list class deals with the memory management and Polynomial deals with adding coefficients. As it stands now, Polynomial has to do both.