Linked List

scuzzo · #1 24-Apr-2009, 21:58

My problem:The overloaded += function which is supposed to add two polynomials only works when both linked lists are the same length and if the exponents are the same. I need real help and I am desperate. Please anyone who can throw me a bone here please jump in.

CPP / C++ / C Code:

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

	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);		

	// destructor 
// release dynamic memory related to the polynomial
	//~Polynomial();				

	// overloaded assignment operator 
// assign the content of p1 to a polynomial
	void operator=(const Polynomial& p1);

	// overloaded += operator
// add a polynomial
	void operator+=(const Polynomial& p1);

	// overloaded -= operator
// subtract a polynomial
	void operator-=(const Polynomial& p1); 

	// read a polynomial
	bool read(int, int);

	// read second polynomial
	bool readnewpoly(int, int);


	// output a polynomial
	void print();
	//output second polynomial
	void printnewpoly();

};

Polynomial::Polynomial()
{
	head=NULL;
}

bool Polynomial::read(int c, int e)
{
	TermType* newTerm = new TermType;
	newTerm->coefficient = c;
	newTerm->exponent = e;
	newTerm->next = NULL;
	
	TermType* currentNode = head;
	if (head == NULL)
	{
		head = newTerm;
	}
	else
	{
		while (currentNode->next != NULL)
			currentNode = currentNode->next;
		currentNode->next = newTerm;
	}
	return true;
}
void Polynomial::print()
{
	TermType* currentNode=head;
	while (currentNode!=NULL)
	{
		if (currentNode->coefficient>0)
			cout<<"+";
		cout<<currentNode->coefficient<<"x^"<<currentNode->exponent;
		currentNode=currentNode->next;
	}
}



void Polynomial::operator +=(const Polynomial &p1)
{

	TermType* currentNode=p1.head;
	TermType* checkNode=head;

	while (currentNode!=NULL)
	{
		bool write=false;
		int output=0;
		checkNode=head;
		while (checkNode!=NULL)
		{
			output=0;
			if (checkNode->exponent==currentNode->exponent)
			{
				cout<<checkNode->coefficient+currentNode->coefficient<<"x^"<<checkNode->exponent<<" ";
				write=true;
				output++;
			}
			if (write=false)
			{
				cout<<currentNode->coefficient<<"x^"<<currentNode->exponent;
				output++;
			}
			checkNode=checkNode->next;
		}
		currentNode=currentNode->next;
	}
}
int main()
{	
	Polynomial p, p1;
	int c, e;
		char option,choice;
do //setting up a menu
	{
		
		cout << endl << endl << "Choose from:" << endl << endl;
		cout << "1. Read in polynomial:" << endl;
		cout << "2. Print First Polynomial:" << endl;
		cout << "3. Read second polynomial:" << endl;
		cout << "4. Print Second Polynomial:"<<endl;
		cout << "5. Add two polynomials:"<<endl;
		cout << "8. Quit:"<<endl;
		cin >> option;

		switch (option)
		{
		case '1':
			do
			{
				cout<<"Please enter coefficient."<<endl;
				cin>>c;
				cout<<"Please enter exponent."<<endl;
				cin>>e;
				cout<<"Enter another term 'n' to quit?"<<endl;
				p.read(c,e);
				cin>>choice;
			}while(choice!='n');
		
			break;
		case '2':
			p.print();
			break;
		case '3':
			do
			{
				cout<<"Please enter coefficient."<<endl;
				cin>>c;
				cout<<"Please enter exponent."<<endl;
				cin>>e;
				cout<<"Enter another term 'n' to quit?"<<endl;
				p1.read(c,e);
				cin>>choice;
			}while(choice!='n');
		
			
			break;
		case '4':
			p1.print();
			break;
		case '5':
			p+=(p1);
			break;
		default:
			cout << "invalid input!!! Try it again." << endl;
		}
	} while (option != '8');
}

fakepoo · #2 27-Apr-2009, 08:13

A few points:

1) I can't see where you actually add the coefficients, just where you print out what would have been the result.

2) It doesn't look like you handle the case that p1 has exponents that "this" doesn't have. In that case, you need to add the new exponent to "this".

scuzzo · #3 28-Apr-2009, 19:16

The problem comes in the += overloaded operator. Everything works well unless as an example I enter one list as +4x^5 and the other list as +3x^4+2x^2 then the only output I get is the first list repeating twice. Please throw me some help here.

CPP / C++ / C Code:

#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);		

	// destructor 
// release dynamic memory related to the polynomial
	//~Polynomial();				

	// overloaded assignment operator 
// assign the content of p1 to a polynomial
	void operator=(const Polynomial& p1);

	// overloaded += operator
// add a polynomial
	void operator+=(const Polynomial& p1);

	// overloaded -= operator
// 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;
}
void Polynomial::operator+=(const Polynomial& p1)
{
	//cout<<"Start print"<<endl;
	TermType* poly1=head;
	TermType* poly2=p1.head;
	int counter=0;
	while ((poly1!=NULL)||(poly2!=NULL))
	{
		//counter++;
		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<<"+";
			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<<"+";
					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<<"+";
					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<<"+";
					if (poly2->coefficient<0)
						cout<<"-";
					cout<<poly2->coefficient<<"x^"<<poly2->exponent;
						poly1=poly1->next;				
					continue;
				}
			/*
			if (poly1->exponent<poly2->exponent)
				{
					if (poly1->coefficient>0)
						cout<<"+";
					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<<"+";
					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)
	{
		cout<<newTerm->coefficient<<"x^"<<newTerm->exponent;
		newTerm=newTerm->next;
	}
	cout << endl;
}
int main()
{
	Polynomial p, p1;	
	p.read();
	cout<<"Second Term:"<<endl;
	p1.read();
	//p.print();
	//p1.print();
	p+=(p1);
	system ("pause");
	return 0;
}

fakepoo · #4 29-Apr-2009, 08:02

This is just a continuation of the other thread. There is not a need to create another.

For each TermType in p1, find the same exponent in "this". If it exists, add the coefficient from p1's TermType to the coefficient of this's TermType. If it doesn't exist, insert p1's TermType to this. After doing this for each TermType, you should go through this's TermTypes and remove any with a coefficient of zero.

I can't make it any clearer without writing the code myself.

admin · #5 29-Apr-2009, 08:10

Threads merged.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Str_Misaligned in Double Link List	Peter_APIIT	C Programming Language	1	29-Feb-2008 21:50
Airport Log program using 3D linked List : problem reading from file	batrsau	C Programming Language	11	29-Feb-2008 08:44
Linked list: differing results on same code.	Howard_L	C Programming Language	17	29-Jun-2007 00:36
search linked list	itsmecathys	C++ Forum	20	18-Apr-2005 02:34

Linked List

Re: Linked List

Quick linked list problem

Re: Quick linked list problem

Re: Quick linked list problem