C++

Forum

 
Polynomial Class...

Pages: 12
hentaiw (273)
Design and implement a class that is a class for polynomials. The polynomial
anxn + an-1xn-1 +...+ a0
will be implemented as a linked list. Each node will contain an int value for the power of x
and an int value for the corresponding coefficient. The class operations should include
addition, subtraction, multiplication, and evaluation of a polynomial. Overload the operators +, −, and * for addition, subtraction, and multiplication. Evaluation of a polyno-
mial is implemented as a member function with one argument of type int. The evaluation
member function returns the value obtained by plugging in its argument for x and per-
forming the indicated operations.


That's a nice project,I take it for my revision...

My class I made so far :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
namespace KudyNode
{
	class Polynomial
	{
	public:
		//CONSTRUCTORS
		Polynomial(int theA,int theN,Polynomial* theLink) : a(theA),n(theN),link(theLink){};
		//ACCESSORS
		int getA() const {return a;}
		int getN() const {return n;}
		Polynomial* getLink() const {return link;}
		//MUTATORS
		void setA(int theA){a = theA;}
		void setN(int theN){n = theN;}
		void setPol(int theA,int theN){a = theA;n = theN;}
		void setLink(Polynomial* theLink){link = theLink;}
		//OVERLOADED OPERATORS
		Polynomial operator + (Polynomial* & object);
		Polynomial operator - (Polynomial* & object);
		Polynomial operator * (Polynomial* & object);
		friend ostream& operator << (ostream& out,const Polynomial& object);
		friend istream& operator >> (istream& in,Polynomial& object);
		//DESTRUCTORS
		virtual ~Polynomial();
	private: //a*x^n
		int a;
		int n;
		Polynomial* link;
	};
}


Polynomial for 3x^2 + 6x + 3 should create 3 nodes of type Polynomial :
1st node : [3][2][->2nd node]
2nd node : [6][1][->3rd node]
3rd node : [3][0][NULL]

My 1st question here is about :

Polynomial operator + (Polynomial* & object);


should the signature be an object or pointer to an object in order to perform addition ?

More question will occur though this project,please support along...I'll post in the same post.
Last edited on
Moschops (7244)
should the signature be an object or pointer to an object in order to perform addition ?


Up to you. I would hazard that if I had two polynomial objects and I wanted to add them, I would expect to be able to add the objects directly and not have to pass pointers to objects to add the actual objects together. I would expect addition involving pointers of objects to be pointer arithmetic.
hentaiw (273)
If I use :

Polynomial Polynomial::operator + (Polynomial object)

I cannot have pointer pointed to the class that call + operator...but have to use this pointer

1
2
3
4
5
6
7
 
Polynomial Polynomial::operator + (Polynomial object)
{
	Polynomial *head1 = this;//Left operand
	Polynomial *head2 = &object;//Right operand
	
	return object;
}


This is just a stub...I use

*head1 = this so I can start check the N to see if it equals then add 2 value A together.

but using this is the only way ?
Last edited on
andywestken (4094)
operator+, operator-, etc should take an object or object ref, not a pointer. Or you break the operator semantics.

1
2
3
 
int3 = int1 + int2;
dbl3 = dbl1 + dbl2;
poly3 = poly1 + poly2; // :-)


i.e. your operator+ should behave like all other operator+s

If you do need to use pointers to add, implement a method of some kind.

Reading the problem description, it sounds to me like the Polynomial class should contain a linked list of nodes (or terms). Not that it should be a node in the linked list itself.

Polynomial = list of nodes
Last edited on
hentaiw (273)
Reading the problem description, it sounds to me like the Polynomial class should contain a linked list of nodes (or terms). Not that it should be a node in the linked list node itself.


Ah right,you mean I should make a list class that has private member of class type Polynomial* ?

If I do so , I have to delete the *link in Polynomial class and put it in new class I think
Last edited on
andywestken (4094)
Sort of.

The outer class is the Polynomial. Inside is has a pointer to a list of nodes (Term is the name used in algebra).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
class Polynomial
{
private:
    class Term
    {
    public:
        ....
        Term* nextTerm;
         int a;
         int n;
         ...
    };

    Term* firstTerm; // for example

    ...

};


This approach should make operator+, etc easier to code.

Not sure about making Term a nested class. It might be nice to be able to get at terms from outside.

Andy
Last edited on
hentaiw (273)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
class Term
	{
	public:
		//CONSTRUCTORS
		Term(int theA,int theN,Term* theLink) : a(theA),n(theN),link(theLink){};
		//ACCESSORS
		int getA() const {return a;}
		int getN() const {return n;}
		Term* getLink() const {return link;}
		//MUTATORS
		void setA(int theA){a = theA;}
		void setN(int theN){n = theN;}
		void setPol(int theA,int theN){a = theA;n = theN;}
		void setLink(Term* theLink){link = theLink;}
		//OVERLOADED OPERATORS
		Term operator + (Term object);
		Term operator - (const Term& object);
		Term operator * (const Term& object);
		friend ostream& operator << (ostream& out,const Term& object);
		friend istream& operator >> (istream& in,Term& object);
		//DESTRUCTORS
		//virtual ~Term();
	private: //a*x^n
		int a;
		int n;
		Term* link;
	};

class Polynomial
	{
	public:
		friend ostream& operator << (ostream& out,const Polynomial& object);
		friend istream& operator >> (istream& in,Polynomial& object);
	private:
		Term* top;	
	};


This is the current work,I plus overloaded << and >> to revise the lesson...Thank you !

The Polynomial should support adding modifying or deleting a Term
andywestken (4094)
Your Term looks ok. Now you just need operator+, operator-, operator* for the Polynomial and your class declarations are pretty much complete. Apart from the "eval" method(s).

Have you done templates yet? If so, consider implementing a generic list and then using that to implement your polynomial (you may well have already written a list?)

Andy

PS You will need extra interal methods. I can think of a couple of possibilities, but it does depend on how you go about your implement. As does your final choice of Term versus const Term& for the i/p params of you operators.
Last edited on
hentaiw (273)
I didn't learn english algebra,could you shortly explain "evaluation of a polynomial" I don't understand so I havn't created it yet.

And also all of the operations I think they need the word virtual,as we can add 2 terms of the same coefficient and add 2 polynomial too...

can an operator be virtual in this case?

Have you done templates yet? If so, consider implementing a generic list and then using that to implement your polynomial (you may well have already written a list?)


I learnt template,but this exercice seems to require int for A and N,what do you mean by generic list ? A list with double coefficient or exponent or sth ?
Last edited on
andywestken (4094)
To evaluate a polynomial means to calculate its value for a given x.

For example, the evaluation of 2x2 - x + 4 with x = 3 gives 19

No, the operators do not need virtual. You only want to be able to add Polynomial class instances together.

If the template comment was unclear, I'd carry on the way you've started.
Last edited on
hentaiw (273)
1
2
3
4
5
6
7
8
9
10
11
12
 
class Polynomial
	{
	public:
		Polynomial() : top(NULL){};
		void addNew(int theA,int theN);
		bool isEmpty() const;
		//OVERLOADED OPERATORS
		friend ostream& operator << (ostream& out,const Polynomial& object);
		friend istream& operator >> (istream& in,Polynomial& object);
	private:
		Term* top;	
	};


That was up to now...

I now have difficult on the output and input of the polynomial...

My addnew :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void Polynomial::addNew(int theA,int theN)
{
	if(isEmpty())
	{
		top = new Term(theA,theN,NULL);
	}
	else
	{
		Term *temp = top;
		while(top->getLink() != NULL)
			top = top->getLink();
		//When reach end !
		top->setLink(new Term(theA,theN,NULL));
		top = temp;
	}
}


My output :

1
2
3
4
5
6
7
8
9
10
11
 
ostream& operator << (ostream& out,const Polynomial& object)
{
	Term *temp = object.top;
	while(object.top->getLink() != NULL)
	{
		out << *temp;
		temp = temp->getLink();
	}
	out << temp->getA();
	return out;
}


The code output what I wanted but the compiler shout an error (has stopped working error)
I think it encounters an infinite loop but can't figure out where...


EDIT : Now the output is fine It forgot while(object.top->getLink() != NULL) must be while(temp->getLink() != NULL) ! LOL! fine now...I'm working on the input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
istream& operator >> (istream& in,Polynomial& object)
{
	char next;
	int sign = 0;
	int theA,theN;
	cin.get(next);
	while(next != '\n')
	{
		if(next != ' ')
		{
			if(next == '-')
				if(sign == 0)
					sign = -1;
				else
					sign = -sign;
			else if(next == '+')
				if(sign == 0)
					sign = 1;
			else if(next >=0 && next <= 9)
			{
				cin.putback(next);
				cin >> theA;
				cin.get(next);
				cin.get(next);
				cin >> theN;
			}
			object.addNew(theA,theN);
			cin.get(next);
		}
	}
	return in;
}


I'll test it now.

EDIT 2 :

The evaluate a polynomial means to calculate it's value for a given x.

So the evaluation of 2x2 - x + 4 for 3 will give 19


Yep,Thanks !

EDIT 3 : input encounters problem...Infinite while again I think
Last edited on
hentaiw (273)
Here is my + for Polynomial...

I must ask...I really should divide the loop into 2 : Before NULL and in-NULL ???

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
Polynomial Polynomial::operator+ (const Polynomial& object)
{
	Term *factor1 = this->top;
	Term *factor2 = object.top;
	Polynomial result;
	bool valAdded = false;
	while(factor1->getLink() != NULL)
	{
		while(factor2->getLink() != NULL && !valAdded)
		{
			if(factor1->getN() == factor2->getN())
			{
				result.addNew(factor1->getA() + factor2->getA(),factor1->getN());
				valAdded = true;
			}
			else
				factor2 = factor2->getLink();
		}
		factor2 = object.top;
		if(!valAdded)
		{
			result.addNew(factor1->getA(),factor1->getN());
			valAdded = true;
		}
		factor1 = factor1->getLink();
		valAdded = false;
	}
	factor1 = this->top;
	return result;
}


I don't have any other way ?
Last edited on
andywestken (4094)
Hi

You addNew would prob be better as

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
void Polynomial::addNew(int theA,int theN)
{
	if(isEmpty())
	{
		top = new Term(theA,theN,NULL);
	}
	else
	{
		Term *temp = top;
		while(temp->getLink() != NULL) // use temp in loop
			temp = temp->getLink();
		//When reach end !
		temp->setLink(new Term(theA,theN,NULL));
		// this way you don't have to remember to reset top
	}
}


It might be better to keep your terms in order. So you need to test to see if the new link is a bigger term that the current link. If it is smaller, advance one link and try again. Until you get to the end.

This does raise the question of how you should handled equal terms with equal powers? Do you keep all of them? Or merge them? If the former, maybe you need a "simplify" method?

Having the terms in order will help with the add and subtract.

I think you add is a good start, but it's incomplete

If your terms are unordered, you will have to reset the inner loop to find all matches. And remember the terms which have not been added and deal with them after the loops end.

It might be better to modify the addNew to the terms are ordered, then it should be easier to implement add. And subtract, etc.

Also,

1
2
3
4
5
6
7
8
9
10
11
 
ostream& operator << (ostream& out,const Polynomial& object)
{
	Term *temp = object.top;
	while(object.top->getLink() != NULL) // <= this line does not look right?
	{
		out << *temp;
		temp = temp->getLink();
	}
	out << temp->getA(); // <= nor does this
	return out;
}
Last edited on
andywestken (4094)
Oh, and I'd leave the operator>> aside to start with. It could be tricky till you're sorted out the other parts.

What you need is a set of test cases. To start with, you can just code a set of functions, which report/return pass or fail. Later on you could load your test cases from a file if you can come up with a reasonably straightforwards way to store polymonials in a file.
hentaiw (273)
It took the whole day to manipulate the input...wow...how time-consuming


This will work for 5x as 5x = 5x^1 and 6 as 6 = 6x^0

Also work for 3x^2 - - 5x now equal 3x^2 + 5x ( - - = + )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
istream& operator >> (istream& in,Polynomial& object)
{
	cout << "Enter A Polynomial : " << endl;
	char next;
	int sign = 0;
	int theA,theN;
	cin.get(next);
	bool savedSign = false;

	while(next != '\n')
	{
		if(next != ' ')
		{
			if(next == '-')
			{
				if(sign == 0)
					sign = -1;
				else
					sign = -sign;
				cin.get(next);
				if(next != ' ')
				{
					cin.putback(next);
					cin.putback('-');
					savedSign = false;
				}
				else
				{
					cin.get(next);
					if(next != '+' && next != '-')
						cin.putback(next);
					else if(next == '-')
					{
						sign = -sign;
						savedSign = true;
						cout << "sign = " << sign;
						cin.putback(next);
					}
					else
						cin.putback(next);
				}
				cin.get(next);
			}
			else if(next == '+')
			{
				if(sign == 0)
					sign = 1;
				cin.get(next);
				if(next != ' ')
				{
					cin.putback(next);
					cin.putback('+');
				}
				cin.get(next);
			}
			if((next >= '0') && (next <= '9'))
			{
				
				cin.putback(next);
				cin >> theA;
				cin.get(next);//Take the word x
				if(next != 'x' && (next == ' ' || next == '\n'))
				{
					theN = 0;
					cin.putback(next);
				}
				else if(next == 'x')
				{
					cin.get(next);//Take '^' or ' '
					if(next == ' ' || next == '\n')
					{
						theN = 1;
						cin.putback(next);
					}
					else if(next = '^')
					{
						cin >> theN;
					}
				}
				if(sign >= 0)
					object.addNew(theA,theN);
				else if(sign < 0)
					object.addNew(-theA,theN);
				savedSign = false;
				if(!savedSign)
					sign = 0;
			}
		}
		cin.get(next);
	}
	return in;
}


It will know 5x^2 - -6x + 7 as 3 nodes... [5][2] [6][1] and [7][0],automically


The final output :

1
2
3
4
5
6
7
8
9
10
11
 
ostream& operator << (ostream& out,const Polynomial& object)
{
	Term *temp = object.top;
	while(temp->getLink() != NULL)
	{
		out << *temp;
		temp = temp->getLink();
	}
	out << *temp;
	return out;
}


Now I'm working with Addition,Subtraction,Multiplication and Evaluation Function... You could suggest how to perform correctly those operations...

I'll also relook at the addNew function,but usually they (user) will put a high-exponent first.
Last edited on
andywestken (4094)
How does you operator<< handle an empty polynomial?

Also, thinking about it a bit more, it might be better to implement add using a copy constructor and then your addNew.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void Polynomial::AddTermsToPolynomial(const Polynomial& object)
{
        Polynomial result(object); // copy constructor

	Term *factor1 = this->top;

	while(factor1->getLink() != NULL)
	{
		result.addNew(factor1->getA(), factor1->getN());
	}

	result.addNew(factor1->getA(),factor1->getN());

       reault.simplify(); // ???

	return result;
}
Last edited on
hentaiw (273)
Thank you very much,I'll work at things you mentioned

Include four constructors: a default constructor, a copy constructor, a constructor with a
single argument of type int that produces the polynomial that has only one constant term
that is equal to the constructor argument, and a constructor with two arguments of type
int that produces the one-term polynomial whose coefficient and exponent are given by the
two arguments. (In the previous notation the polynomial produced by the one-argument
constructor is of the simple form consisting of only a0. The polynomial produced by the
two-argument constructor is of the slightly more complicated form anxn.) Include a suit-
able destructor. Include member functions to input and output polynomials.


Some more of the subject.


I don't understand this one.
a constructor with a
single argument of type int that produces the polynomial that has only one constant term
that is equal to the constructor argument



EDIT 1 : I'm working on this again.THis is my << after handling an empty Polynomial...Plz check :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
ostream& operator << (ostream& out,const Polynomial& object)
{
	Term *temp = object.top;
	if(temp == NULL)
		out << "0";
	else
	{
		while(temp->getLink() != NULL)
		{
			out << *temp;
			temp = temp->getLink();
		}
		out << *temp;
	}
	return out;
}


EDIT 2 : I have to use while 2 times for BEFORE NULL & IN-NULL CASE...If I use Iterator q with q.begin() and q.end() I only have 1 case to solve...It automically loop throughout
Last edited on
andywestken (4094)
a constructor with a single argument of type int that produces the polynomial that has only one constant term that is equal to the constructor argument

Sound like you need to be able to do things like

1
2
3
 
Polynomial poly(7);

cout << "poly = " << poly << endl;


poly = 7


And

1
2
3
 
Polynomial poly(4, 3);

cout << "poly = " << poly << endl;


poly = 4x3


Yes?

And your operator<< looks OK to me.

Andy
Last edited on
hentaiw (273)
My simplify :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
void Polynomial::simplify()
{
	Term *temp = top;
	int merge = 0;
	while(temp != NULL)
	{
		int expo = temp->getN();
		merge = temp->getA();
		Term * temp2 = temp;
		temp2 = temp2->getLink();
		while(temp2 != NULL)
		{
			if(temp2->getN() == temp->getN())
			{
				if(temp2->getA() >= 0)
					merge = merge + temp2->getA();
				else if(temp2->getA() < 0)
					merge = merge - temp2->getA();
				
			}
			temp2 = temp2->getLink();
		}
		temp = temp->getLink();
	}
}


You mean that I should have this function : to have 2x^2 + 3x - 2x = 2x^2 + 1x ,right ?

But now I got the problem of deleting the nod that had been used.I must have a pointer point to the node before or something ?

EDIT : Added 2 constructors : Plz check

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
class Polynomial
	{
	public:
		Polynomial() : top(NULL){};
		Polynomial(int theA) {addNew(theA,0);}; 
		Polynomial(int theA,int theN) {addNew(theA,theN);}
		void addNew(int theA,int theN);
		bool isEmpty() const;
		void simplify();
		void remove(Term* afterMe);
		//OVERLOADED OPERATORS
		Polynomial operator + (const Polynomial& object);
		Polynomial operator - (const Polynomial& object);
		Polynomial operator * (const Polynomial& object);
		friend ostream& operator << (ostream& out,const Polynomial& object);
		friend istream& operator >> (istream& in,Polynomial& object);
	private:
		Term* top;	
	};


EDIT 2 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
void Polynomial::simplify()
{
	Term *temp = top;
	int merge = 0;
	while(temp != NULL)
	{
		int expo = temp->getN();
		merge = temp->getA();
		Term * temp2 = temp;
		temp2 = temp2->getLink();
		while(temp2 != NULL)
		{
			if(temp2->getN() == temp->getN())
			{
				if(temp2->getA() >= 0)
					merge = merge + temp2->getA();
				else if(temp2->getA() < 0)
					merge = merge + temp2->getA();
				temp2->setA(0);
				temp2->setN(1);
			}
			temp2 = temp2->getLink();
		}
                temp->setA(merge);
		temp = temp->getLink();
                merge = 0;
	}
}


Instead of deleting the node,I set the A to 0 and N to 1.
But I still need to have a remove function,as I wrote like this :

1
2
3
4
5
6
 
void Polynomial::remove(Term* afterMe)
{
	Term* discard = afterMe->getLink();
	afterMe->setLink(discard->getLink());
	delete discard;
}


But how can I implement it to use in the simplify() instead of setting A and N like I did before.
Last edited on
hentaiw (273)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
Polynomial Polynomial::operator+ (const Polynomial& object)
{
	Term *factor1 = this->top;
	Term *factor2 = object.top;
	Polynomial result;
	bool valAdded = false;
	
	if(factor2->getN() > factor1->getN())
	{
		Term *temp = factor1;
		factor1 = factor2;
		factor2 = temp;
	}

	while(factor1 != NULL)
	{
		while(factor2 != NULL && !valAdded)
		{
			if((factor1->getN() == factor2->getN()) && !valAdded)
			{
				result.addNew(factor1->getA() + factor2->getA(),factor1->getN());
				valAdded = true;
			}
			factor2 = factor2->getLink();
		}//End 2
		if(!valAdded)
		{
			result.addNew(factor1->getA(),factor1->getN());
			valAdded = true;
		}
		valAdded = false;
		factor2 = object.top;
		factor1 = factor1->getLink();
	}//End 1

	return result;
}


This is + operator,but it got error in the output if poly 2 got higher exponent
Pages: 12