1. Homepage of Dr. Zoltán Porkoláb
    1. Home
    2. Archive
  2. Teaching
    1. Timetable
    2. Bolyai College
    3. C++ (for mathematicians)
    4. Imperative programming (BSc)
    5. Multiparadigm programming (MSc)
    6. Programming (C in English)
    7. Programming languages (PhD)
    8. Software technology lab
    9. Theses proposals (BSc and MSc)
  3. Research
    1. CodeChecker
    2. CodeCompass
    3. Templight
    4. Projects
    5. Publications
    6. PhD students
  4. Affiliations
    1. Dept. of Programming Languages and Compilers
    2. Ericsson Hungary Ltd

Student project

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-2

Consider 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:

cpp-mat-task-1-1.mkv

cpp-mat-task-1-2.mkv

cpp-mat-task-1-3.mkv

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) == 24680122

Write 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) == 0

Task 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) == 0

Write 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) == -180

Write 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>?


Financed from the financial support ELTE won from the Higher Education Restructuring Fund of the Hungarian Government.