Student project in 2021
During the semester the students will (individually) work on a larger project. They will step by step create a Polynom class and its test environment. For every time you have to create a small additional task built on the previous results. We publish the solutions of every steps after some delay, so if you are disrupted for a while you still can catch up later.
Submit the solutions on Canvas as one single C++ source file containing the main() function given in the task.
Task 1: Create a pretty printer for polynoms
Write a pretty printer function for polynoms which returns a string representation of the polynom. The polynom is given by its coefficients, stored in a std::vector (the lower coefficients are in the lower indexes). We can suppose, that the highest element of the vector is not 0.
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>
std::string to_string(std::vector<int> v);
int main()
{
std::vector<int> v = { -2, 0, 5, -3, 8};
std::string s = to_string(v);
std::cout << s << '\n';
return 0;
}
Expected result is:
8X^4-3X^3+5X^2-2Consider the edge cases: 0 degree polynom, no constant tag, negatives, etc.. Write a main() function which tests your function with various cases. Use the std::to_string() function to convert numbers to string.
Submit your solution to Canvas by 26th March, 23:59h.
Solution
Video:
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
#include <iostream>
#include <vector>
#include <string>
std::string to_string(std::vector<int> v);
std::string coeff_to_string(std::vector<int> v, size_t idx);
int main()
{
// test cases: each line is a polynom
std::vector<std::vector<int>> polynoms{
{ 42, 0, 5, 0, 8, 9 },
{-42, 0, 5, 0, 8,-9 },
{ 0, 0, 5, 0, 8,-9 },
{ 0, 0,-5, 0, 8,-9 },
{ 8 }, // test constant polynom
{ -8 },
{ 0 }, // test null polynom
{ } // consider empty as null polynom
};
polynoms.push_back( std::vector<int>{} ); // empty vector
for ( auto vec : polynoms ) // execute to:string() for all
{
std::string s = to_string(vec);
std::cout << s << '\n';
}
return 0;
}
std::string to_string(std::vector<int> v)
{
// special cases: empty vector and null polynom
if ( v.empty() || (1 == v.size() && 0 == v[0]) )
{
return "0";
}
std::string res;
// never check size_t or any unsigned value with >= 0
for (size_t i = v.size(); i > 0; --i)
{
res += coeff_to_string( v, i-1);
}
return res;
}
// helper function to process one coefficient
std::string coeff_to_string(std::vector<int> v, size_t i)
{
std::string r;
int coeff = v[i];
if ( 0 == coeff ) // if zero, skip
return r;
// print the sign if necessary
if ( coeff < 0 )
; // nothing to do: std::to_string(coeff) prints - sign
else if ( i < v.size()-1 )
r += "+"; // write + sign only when not highest degree
r += std::to_string(coeff);
if( i > 0 ) // write X^i only for degree > 0
{
r += "X^";
r += std::to_string(i);
}
return r;
}
Task 2: Evaluate a polynom
Write a function to evaluate polynoms at a value t.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>
std::string to_string(std::vector<int> v);
int main()
{
// task 1
std::vector<int> v = { -2, 0, 5, -3, 8};
std::string s = to_string(v);
std::cout << s << '\n';
// task 2
std::cout << "tP(-2) == " << evaluate( v, -2);
std::cout << "\t P(0) == " << evaluate( v, 0);
std::cout << "\tP(42) == " << evaluate( v, 42);
return 0;
}
Expected result is:
8X^4-3X^3+5X^2-2
P(-2) == 170 P(0) == -2 P(42) == 24680122Write a main() function which tests your function with various cases. Submit your solution (one single c++ source file) to Canvas in mail by 12 April (Monday) 24h.
Soultion
We will use the Horner’s method to evaluate the polinomial.
p(x) = a0 + a1x + a2x^2 + … + anx^n = a0 + x( a1 + x( a2 + … xan … ) )
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
#include <iostream>
#include <vector>
#include <string>
std::string to_string(std::vector<int> v);
std::string coeff_to_string(std::vector<int> v, size_t idx);
int evaluate( std::vector<int> v, int t);
int main()
{
std::vector<std::vector<int>> polynoms{ // test data
{ -2, 0, 5,-3, 8 },
{ 42, 0, 5, 0, 8, 9 },
{-42, 0, 5, 0, 8,-9 },
{ 0, 0, 5, 0, 8,-9 },
{ 0, 0,-5, 0, 8,-9 },
{ 8 },
{ -8 },
{ 0 },
{ }
};
polynoms.push_back( std::vector<int>{} ); // empty vector
for ( auto vec : polynoms )
{
std::string s = to_string(vec);
std::cout << s << ':';
std::cout << "\tP(-2) == " << evaluate( vec, -2);
std::cout << "\t P(0) == " << evaluate( vec, 0);
std::cout << "\tP(42) == " << evaluate( vec, 42);
std::cout << '\n';
}
return 0;
}
std::string to_string(std::vector<int> v)
{
if ( v.empty() || (1 == v.size() && 0 == v[0]) )
{
return "0";
}
std::string s;
for (size_t i = v.size(); i > 0; --i)
{
s += coeff_to_string( v, i-1);
}
return s;
}
std::string coeff_to_string(std::vector<int> v, size_t i)
{
std::string s;
int coeff = v[i];
if ( 0 == coeff )
return s;
if ( coeff < 0 )
; // nothing to do: to_string(coeff) prints - sign
else if ( i < v.size()-1 )
s += "+";
s += std::to_string(coeff);
if( i > 0 )
{
s += "X^";
s += std::to_string(i);
}
return s;
}
int evaluate( std::vector<int> v, int t)
{
int res = 0; // the result
if ( ! v.empty() ) // just do not crash on invalid input
{
for ( size_t i = v.size()-1; i > 0; --i)
{
res += v[i]; // ( ... + ai )
res *= t; // x * ( ... )
}
res += v[0]; // + a0
}
return res;
}
The output is:
$ ./a.out
X^4-3X^3+5X^2-2: P(-2) == 170 P(0) == -2 P(42) == 24680122
9X^5+8X^4+5X^2+42: P(-2) == -98 P(0) == 42 P(42) == 1201123518
-9X^5+8X^4+5X^2-42: P(-2) == 394 P(0) == -42 P(42) == -1151318742
-9X^5+8X^4+5X^2: P(-2) == 436 P(0) == 0 P(42) == -1151318700
-9X^5+8X^4-5X^2: P(-2) == 396 P(0) == 0 P(42) == -1151336340
8: P(-2) == 8 P(0) == 8 P(42) == 8
-8: P(-2) == -8 P(0) == -8 P(42) == -8
0: P(-2) == 0 P(0) == 0 P(42) == 0
0: P(-2) == 0 P(0) == 0 P(42) == 0
0: P(-2) == 0 P(0) == 0 P(42) == 0Task 3: Write a Polynom class
Write a (non-templated) class to represent polynoms. Write constructor(s)
to initialize a polynom with a vector<> or to create a “0” polynom.
Write member functions to return the string representation and evaluate a
polynom (like to_string() and evaluate() in the prevous tasks). Write a
deg() member function to return the degree of the polynom (rank of the
highest coefficient), and a coeff(i) member function to return the
coefficient i. The member function coeff(i) should return 0 if
i is higher than the degee of the polynom.
Separate the interface and the implementation of the class. Write a header file polynom.h for the interface and a source file polynom.cpp for the implementation.
This is a sample, how we want to use the class. Consider the doubled brace pairs { { … } } at the construction of the std::vector of Polynoms. This is necessary, because the inner brace pair { 42, 0, 5, 0, 8, 9 } is specifying the initialization of a vector (like earlier), and the outer pair is the parenthesis for the Polynom constructor.
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
// pmain.cpp
#include <iostream>
#include "polynom.h"
int main()
{
std::vector<Polynom> polynoms{
{ { -2, 0, 5,-3, 8 } },
{ { 42, 0, 5, 0, 8, 9 } },
{ {-42, 0, 5, 0, 8,-9 } },
{ { 0, 0, 5, 0, 8,-9 } },
{ { 0, 0,-5, 0, 8,-9 } },
{ { 8 } },
{ { -8 } },
{ { 0 } },
{ { } }
};
polynoms.push_back( Polynom{} ); // default constructor
int t1 = -2;
int t2 = 0;
int t3 = 42;
for ( auto poly : polynoms )
{
std::string s = poly.to_string();
std::cout << s << "\t\t";
std::cout << "deg = " << poly.deg() << "\t\t"; // degree
for ( int i = 9; i >= 0; --i ) // print coeffs 9..0
{
// if i > deg() then this should be 0
std::cout << poly.coeff(i) << " ";
}
// evaluate the polynom at t1, t2, t3
std::cout << "\neval("<< t1 <<") == "<< poly.eval(t1);
std::cout << "\teval("<< t2 <<") == "<< poly.eval(t2);
std::cout << "\teval("<< t3 <<") == "<< poly.eval(t3);
std::cout << '\n';
}
return 0;
}
The expected result is:
$ g++ -Wall -Wextra pmain.cpp polynom.cpp -o pmain
$ ./pmain
8X^4-3X^3+5X^2-2 deg = 4 0 0 0 0 0 8 -3 5 0 -2
eval(-2) == 170 eval(0) == -2 eval(42) == 24680122
9X^5+8X^4+5X^2+42 deg = 5 0 0 0 0 9 8 0 5 0 42
eval(-2) == -98 eval(0) == 42 eval(42) == 1201123518
-9X^5+8X^4+5X^2-42 deg = 5 0 0 0 0 -9 8 0 5 0 -42
eval(-2) == 394 eval(0) == -42 eval(42) == -1151318742
-9X^5+8X^4+5X^2 deg = 5 0 0 0 0 -9 8 0 5 0 0
eval(-2) == 436 eval(0) == 0 eval(42) == -1151318700
-9X^5+8X^4-5X^2 deg = 5 0 0 0 0 -9 8 0 -5 0 0
eval(-2) == 396 eval(0) == 0 eval(42) == -1151336340
8 deg = 0 0 0 0 0 0 0 0 0 0 8
eval(-2) == 8 eval(0) == 8 eval(42) == 8
-8 deg = 0 0 0 0 0 0 0 0 0 0 -8
eval(-2) == -8 eval(0) == -8 eval(42) == -8
0 deg = 0 0 0 0 0 0 0 0 0 0 0
eval(-2) == 0 eval(0) == 0 eval(42) == 0
0 deg = 0 0 0 0 0 0 0 0 0 0 0
eval(-2) == 0 eval(0) == 0 eval(42) == 0
0 deg = 0 0 0 0 0 0 0 0 0 0 0
eval(-2) == 0 eval(0) == 0 eval(42) == 0Write a main() function which tests your function with various cases. Submit your solution (one single c++ source file) to Canvas in mail by 26 April (Monday) 24h.
Solution
To implement the polynom class we will create a polynom.h for the interface of the class, and the polynom.cpp as the implementation.
In the polynom.h header file (inside the mandatory include guards), we define the class. The constructor will take a std::vector - the same we used in the earlier version as the parameter of the to_string() and eval() function. The constructor has a default parameter: an empty vector. Without parameter (e.g. as a default constructor) we create an empty representation, which is the 0 polynom.
The deg(), coeff(), eval() and to_string() functions are the public interface of the class. See the deg() functon as implemented inside the class declaration. Also, consider that it is valide to call the deg() function with a parameter higher than the degree of the polynom. In that case deg() returns 0.
The only data member will be the __coeffs - a vector of integers. The normalize() and coeff_to_string() functions are private members, as they are not part of the interface of the class.
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
#ifndef POLYNOM_H
#define POLYNOM_H
#include <vector>
#include <string>
//
// invariant: the highest element >0
//
class Polynom
{
public:
Polynom( std::vector<int> v = {} );
int coeff(size_t i) const;
size_t deg() const { return _coeffs.size() > 0 ?
_coeffs.size()-1 : 0; }
int eval(int t) const;
std::string to_string() const;
private:
std::vector<int> _coeffs;
std::string coeff_to_string(size_t i) const;
void normalize();
};
#endif // POLYNOM_H
The polynom.cpp contains the implementation of the rest of the methods. Most of the functions are straightforward to rewrite from global function to member.
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
#include <vector>
#include <string>
#include "polynom.h"
Polynom::Polynom( std::vector<int> v)
: _coeffs( std::move(v) ) // C++11 move semantics,
{ // it is ok just copy with:_coeffs(v)
normalize();
}
void Polynom::normalize()
{
for (auto i=_coeffs.size(); i>0 && 0==_coeffs[i-1]; --i)
{
_coeffs.pop_back();
}
}
int Polynom::coeff(size_t i) const
{
return _coeffs.empty()||i>deg()||i<0 ? 0 : _coeffs[i];
}
std::string Polynom::to_string() const
{
if ( _coeffs.empty() )
{
return "0";
}
std::string s;
for (size_t i = _coeffs.size(); i > 0; --i)
{
s += coeff_to_string(i-1);
}
return s;
}
std::string Polynom::coeff_to_string(size_t i) const
{
std::string s;
int coeff = _coeffs[i];
if ( 0 == coeff )
return s;
if ( coeff < 0 )
; // nothing to do: std::to_string(coeff) prints - sign
else if ( i < deg() )
s += "+";
s += std::to_string(coeff);
if( i > 0 )
{
s += "X^";
s += std::to_string(i);
}
return s;
}
int Polynom::eval(int t) const
{
int res = 0 ;
if ( ! _coeffs.empty() )
{
for ( size_t i = _coeffs.size()-1; i > 0; --i)
{
res += _coeffs[i];
res *= t;
}
res += _coeffs[0];
}
return res;
}
Task 4: Write a Polynom class template with operators
Write a class template for the version of the Polynom. The interface is similar than the prevoius non-templated class, but extend it with some operators. (As it is a class template, you will write only a header file and a main.cpp for test). (2 pts)
Write operators for the template Polynom class. If p1 and p2 are polynoms, then let p1(t) is the evaluation of p1 at t. Also, implement the global operators p1 + p2, and p1 - p2 (2pts).
A test program:
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
#include <iostream>
#include "polynom.h"
int main()
{
Polynom<double> p1{ {42, 0, 5, 0, 8, 9} };
Polynom<double> p2{ {-2, 6,-3, 9, 1 } };
int t1 = 0;
int t2 = 1;
int t3 = -2;
auto poly = p1 + p2;
std::cout << "p1 = " << p1.to_string() << '\n';
std::cout << "p2 = " << p2.to_string() << '\n';
std::cout << "p1+p2 = " << poly.to_string() << '\n';
std::cout << "\np1(" << t1 << ") == " << p1(t1);
std::cout << " p1(" << t2 << ") == " << p1(t2);
std::cout << " p1(" << t3 << ") == " << p1(t3);
std::cout << "\np2(" << t1 << ") == " << p2(t1);
std::cout << " p2(" << t2 << ") == " << p2(t2);
std::cout << " p2(" << t3 << ") == " << p2(t3);
std::cout << "\n(p1+p2)(" << t1 << ") == " << poly(t1);
std::cout << " (p1+p2)(" << t2 << ") == " << poly(t2);
std::cout << " (p1+p2)(" << t3 << ") == " << poly(t3)
<< '\n';
return 0;
}
The expected result is:
$ g++ -Wall -Wextra pmain.cpp -o pmain
$ ./pmain
p1 = 9X^5+8X^4+5X^2+42
p2 = 1X^4+9X^3-3X^2+6X^1-2
p1+p2 = 9X^5+9X^4+9X^3+2X^2+6X^1+40
p1(0) == 42 p1(1) == 64 p1(-2) == -98
p2(0) == -2 p2(1) == 11 p2(-2) == -82
(p1+p2)(0) == 40 (p1+p2)(1) == 75 (p1+p2)(-2) == -180Write a main() function which tests your function with various cases, including other types than double. Submit your solution as one single source into canvas (separating polynom.h and main.cpp with /****/) by 12th May (Wednesday) 23:59h.
If you have time, implement p1 * p2 and p1 / p2 but these are just extras… Also, think how could you implement the + operator allowing to add a Polynom<int> to a Polynom<double>?