[자료구조 - C++] Assignment 1 다항식 계산기 만들기

해당 과제에서는 다항식 ADT(Abstract Data Type)를 사용해서 다항식 계산기를 만드는 것을 목표로 한다.

 

1) polynomial.h

 

구현해야 하는 함수들 : 

Polynomial (const Polynomial& source) : copy constructor
• ~Polynomial() : destructor
• Polynomial& operator= (const Polynomial& source): Assignment operator
• Polynomial operator+ (const Polynomial& source) : Sum of polynomials
• Polynomialoperator- (const Polynomial& source): Subtraction of polynomials
• Polynomial operator* (const Polynomial& source): Multiplication of polynomials
• Polynomial Derivative(): compute the derivative of polynomial
• bool operator == (const Polynomial& source): check if left and 
right polynomial are identical and return true/false accordingly.
• float Eval(float x) : evaluate polynomial at x
• void CreateTerm(const float coef, const int exp): create a 
new polynomial term of coef * x^(exp).exp must be non-negative value. If the 
same exponent term already exists, replace its coefficient with the new one.

이미 구현되어 있는 함수들 :

Polynomial() : default constructor
• Print() : print the current polynomial.
• Capacity():maximum number of terms this polynomial can store
• Terms() : returns the number of non-zero terms currently stored in this polynomial
• GetTerm(int x) : get the access of a term (x is the index of that term).

2) polynomial.cpp

 

실제로 위 polynomial.h에 정의되어 있는 함수를 polynomial.cpp 파일에서 구현한다.

 

주의사항 : 

1. Make sure you implement the copy constructor and assignment operator correctly so that assigning one polynomial to the other using = operator or creating a new polynomial from an existing polynomial object work correctly. : Copy Constructor와 Assignment Operator을 제대로 만들 것.
2. Make sure that CreateTerm() resizes the array if more terms are created than the current object can handle. Stress tests will be conducted : 만약 temrArray가 감당할 수 있는 capacity보다 더 많은 값을 입력받는다면 capacity를 재설정할 것.
3. When a new term is added using CreateTerm(), if there is no term existing in the current polynomial of a given exponent, you need to create a new term. If the same exponent term exists, then you need to replace its coefficient with the new one : CreateTerm() 함수를 이용해서 항을 추가할 때, 이미 존재하는 항의 지수와 같지 않다면 새로 추가하고, 이미 존재하는 항의 지수와 동일할 때에는 새로 입력되는 항의 계수로 존재하는 항의 계수를 대체한다.
4. CreateTerm() does not need to be called the descending order of exponent term, but the termArray must be internally arranged in a descending order. For example, if you call CreateTerm(3,1) to create a polynomial term 3x, and then you create a higher order term by calling CreateTerm(2,2), then the resulting polynomial should be 2x^2+3x (not 3x+2x^2). : 지수의 크기대로 내림차순으로 CreateTerm() 함수를 호출할 필요는 없지만 내재적으로 termArray는 내림차순으로 정리되어야만 한다. 
5. If a term has a zero (or close to zero, abs(coef) < 1.0e-6) coefficient, then you need to remove that term from the polynomial. For example, if p1=2x^2+1 and p2=2x^2+x+1, then p1-p2 will make the coefficient of x^2 term zero, so the result should be –x-1. : 만약 항의 계수가 0이라면 다항식에서 해당 항을 제거해야 한다.
6. We provided print() function that prints out the given polynomial as the following form. "cnx^n+cn-1x^(n-1)+ .... +c1x^1+c0". Do not change print() function because this will be used to check your code. You must manage your polynomial terms in a descending order because print function does not automatically sort the order of terms. : print() 함수가 정렬을 시켜주지 않으므로 따로 다항식을 지수의 내림차순으로 정렬하라. print() 함수를 건들지 말 것.
7. You are not allowed to use STL library. : STL library를 사용하지 말 것.

3) 전체 파일

 

3-1) polynomial.h

#ifndef polynomial_h
#define polynomial_h

#include <typeinfo>
#include <iostream>
#include <math.h>


class Polynomial;

class Term {
	friend class Polynomial;

private:
	float coef;
	int exp;
};

class Polynomial
{
public:
	// Default constructor p(x) = 0
	Polynomial()
	{
		capacity = 10;
		terms = 0;
		termArray = new Term[capacity];
        
	};
	
	// Copy constructor
	Polynomial(const Polynomial& source);

	// Destructor
	~Polynomial();

	// Assignment operator
	Polynomial& operator = (const Polynomial& source);

	// Sum of *this and source polynomials
	Polynomial operator+(const Polynomial& source);
	
	// Subtract of source polynomials from *this
	Polynomial operator-(const Polynomial& source);

	// Product of *this and source polynomials
	Polynomial operator*(const Polynomial& source);
	
	// Compute derivative of the current polynomial
	Polynomial Derivative();

	// Return true if left polynomial is identical to right polynomial
	bool operator==(const Polynomial& source);

	// Evaluate polynomial *this at x and return the result
	float Eval(float x);

	// Create a new term. If the term exists, overwrite its coefficient.
	void CreateTerm(const float coef, const int exp);


	// Print polynomial
	void Print()
	{
		if(terms == 0) std::cout << "0" << std::endl;
		else
		{
			for(int i=0; i<terms; i++)
			{
				float c = termArray[i].coef;
				int e = termArray[i].exp;
							
				if(c > 0 && i > 0)
				{
					std::cout << "+";
				}
				
				std::cout << c;
				if(e > 0) std::cout<<"x^"<<e;
			}
			std::cout << std::endl;
		}
    }
	
	int Capacity() const { return capacity; }
	int Terms() const { return terms; }
	Term& GetTerm(int x) const { return termArray[x]; } 

private:
	Term *termArray;
	int capacity; // max # of terms in this polynomial
	int terms;	  // current # of terms in this polynomial
};


#endif

3-2) polynomial.cpp

#include "polynomial.h"
#include <iostream>
#include <math.h>


//
// Implementation
//

// Copy constructor
Polynomial::Polynomial(const Polynomial& source)
{
    terms = source.terms;
    capacity = source.capacity;
    termArray = new Term[capacity];
    for(int i = 0; i < terms; i++)
        termArray[i] = source.termArray[i]; //deep copy
}

// Destructor
Polynomial::~Polynomial()
{
    delete[] termArray;
    terms = 0;
    capacity = 0;
    termArray = nullptr;    //initalize with nullptr
}


Polynomial& Polynomial::operator = (const Polynomial& source)
{

    if(this != &source)//when it's not same with the original
    {
        capacity = source.capacity;
        terms = source.terms;
        delete[] termArray;
        termArray = new Term[capacity];
        for(int i = 0; i < terms; i++)
            termArray[i] = source.termArray[i]; //deep copy
    }
    return *this;   //return pointer value
}



// Sum of *this and source polynomials
Polynomial Polynomial::operator +(const Polynomial& source)
{
    Polynomial c;
    int A_index = 0;
    int B_index = 0;
    while(A_index <= terms && B_index <= terms)   //it works when the indexes are smaller than the terms
    {
        if(termArray[A_index].exp == source.termArray[B_index].exp) //when original termArray's exp is same with the source.termArray's exp
        {
            float Coef_Sum = 0;
            Coef_Sum = termArray[A_index].coef + source.termArray[B_index].coef;    //add with coefficients
            if(Coef_Sum != 0)   //store in Polynomial c when coefficient is not 0
                c.CreateTerm(Coef_Sum, termArray[A_index].exp);
            
            A_index++;  // add 1 as A_index is used
            B_index++;  // add 1 as B_index is used
        }
        else if(termArray[A_index].exp > source.termArray[B_index].exp) //when termArray's exp is bigger than source.termArray.exp
        {
            c.CreateTerm(termArray[A_index].coef, termArray[A_index].exp);  //store termArray[A_index].coef and exp.
            A_index++;  //add 1 as only A_index is used.
        }
        else
        {
            c.CreateTerm(source.termArray[B_index].coef, source.termArray[B_index].exp);    //when termArray's exp is smaller than source.termArray.exp
            B_index++;//add 1 as only B_index is used.
        }
    }
    for(; A_index < terms; A_index++)   //add left termArray[A_index].coef and exp
        c.CreateTerm(termArray[A_index].coef, termArray[A_index].exp);
    for(; B_index < source.terms; B_index++)    //add left termArray[B_index].coef and exp
        c.CreateTerm(source.termArray[B_index].coef, source.termArray[B_index].exp);
    
    return c;
}

Polynomial Polynomial::operator - (const Polynomial& source)
{
    Polynomial c;
    int A_index = 0;
    int B_index = 0;
    while(A_index <= terms && B_index <= terms)   //it works when indexes are smaller or same with temrs.
    {
        if(termArray[A_index].exp == source.termArray[B_index].exp) //when termpArray's exp and source.termArray's exp is same.
        {
            float Coef_Sum = 0;
            Coef_Sum = termArray[A_index].coef - source.termArray[B_index].coef;  //subtract with coefficients
            if(Coef_Sum != 0) //store in Polynomial C when coefficient is not 0
                c.CreateTerm(Coef_Sum, termArray[A_index].exp);
            A_index++;  // add 1 as A_index is used.
            B_index++;  // add 1 as B_index is used.
        }
        else if(termArray[A_index].exp > source.termArray[B_index].exp) //when termArray's exp is bigger than source.termArray's exp.
        {
            c.CreateTerm(termArray[A_index].coef, termArray[A_index].exp);  //store termArray[A_index].coef and exp.
            A_index++;  //add 1 as A_index is used.
        }
        else    //when termArray's exp is smaller than source.termArray's exp.
        {
            c.CreateTerm((-1)*(source.termArray[B_index].coef), source.termArray[B_index].exp); //store after multiply -1 at source.termArray[B_index].coef. exp is same.
            B_index++;  //add 1 as B_index is used.
        }
    }
    for(; A_index < terms; A_index++)   //store left termArray values.
        c.CreateTerm(termArray[A_index].coef, termArray[A_index].exp);
    for(; B_index < source.terms; B_index++)    //store left termArray multiply -1
        c.CreateTerm((-1)*(source.termArray[B_index].coef), source.termArray[B_index].exp);
    return c;
    
}

Polynomial Polynomial::operator * (const Polynomial& source)
{
    Polynomial c;
    float c_coef = 0;// temporarily store Polynomial c's coef.
    int c_exp = 0;// temporarily store Polynomial c's exp.
    
    for(int i = 0; i < terms; i++)  // Outer Loop: Use double for loop to manipulate two polynomials.(1st loop)
    {
        for(int j = 0; j < source.terms; j++)   //Outer Loop: (2nd loop)
        {
            c_coef = termArray[i].coef * source.termArray[j].coef;
            c_exp = termArray[i].exp + source.termArray[j].exp;
            int same = -5;  //temporarily store the index of same exp with original polynomial. Initialize with negative number.
            for(int k = 0; k < c.terms; k++)    //Inner: compare already stored c.termArray[].exp with c_exp by using single for loop.
            {
                if(c.termArray[k].exp == c_exp) //if exp is same then add c.termArray[].coef at c_coef.
                    same = k;   //store same exp index at temporary variable.
            }
            if(same != -5)  //when same exp index is stored in variable "same".
            c.termArray[same].coef += c_coef;   //store after add to original polynomial's coef.
            else    //while variable "same" has not changed.
            c.CreateTerm(c_coef, c_exp);    //create new Term.
        }
    }
    
    return c;
}

bool Polynomial::operator == (const Polynomial& source)
{
    bool ret;
    ret = true;    //initialize return as true.
    
    if(terms != source.terms)   //first of all, if terms are different than return false.
    {
        ret = false;
        return ret;
    }
    else
    {
        for (int i = 0; i < terms; i++)
        {
            if(termArray[i].coef != source.termArray[i].coef)   //Using loop, return false if temrArray.coef and source.temrmArray.coef is different.
                {
                    ret = false;
                    return ret;
                }
        
            if(termArray[i].exp != source.termArray[i].exp)   //Using loop, return false if temrArray.exp and source.temrmArray.exp is different.
            {
                ret = false;
                return ret;
            }
        }
    ret = true;     //if all same then return true.
    return ret;
    }
}

float Polynomial::Eval(float x)
{
    float ret = 0;
    
    float pow_x = x;    //temporary value for using power.
    for(int i = 0; i < terms; i++)   //loop that loop indexes once.
    {
        if(termArray[i].exp == 0) //when exp is 0.
            ret += termArray[i].coef; //add coef to ret.
        else //when exp is not 0
        {
            for(int j = 0; j < termArray[i].exp - 1; j++) //we need to subtract 1
                x *= pow_x;
            ret += (termArray[i].coef * x); //multiply factor's involution at coef.
            x = pow_x;
        }
    }
    return ret;
}

// Compute derivative of the current polynomial
Polynomial Polynomial::Derivative()
{
    Polynomial c;
    
    for(int i = 0; i < terms; i++)  //Loop which loop indexes once.
    {
        if(termArray[i].exp != 0)    //when exp is not 0
        {
            termArray[i].coef *= termArray[i].exp;  //store coef * exp at termArray[i].coef
            termArray[i].exp -= 1;  //store exp subtract 1
            c.CreateTerm(termArray[i].coef, termArray[i].exp);
        }
    }
    return c;
}

void Polynomial::CreateTerm(const float coef, const int exp)
{
    
    if(terms == capacity)//if terms get bigger than origianl capacity then we should increase capacity and copy them to the new one.
    {
        capacity *= 2;  //doubling strategy
        Term *N_Term = new Term[capacity];
        for(int i = 0; i < terms; i++) // deliver copy value.
        {
            N_Term[i].coef = termArray[i].coef;
            N_Term[i].exp = termArray[i].exp;
        }
        delete[] termArray; //initialize termArray
        termArray = N_Term; //assign N_Term at termArray.
        
    }
    
    int same = -5;  //index which is used to find if there's any same exp. initialize with negative number.
    for(int i_exp = 0; i_exp < terms; i_exp++)
        if(termArray[i_exp].exp == exp) //if exp is same then store index at variable "same".
            same = i_exp;
    
    if(same == -5 && coef != 0 ) //store new if same has not changed and coef is not 0.
    {
        termArray[terms].coef = coef;
        termArray[terms].exp = exp;
    }
    else if(same != - 5)    //if exp is same then substitute index.coef. 
        termArray[same].coef = coef;
    
    for(int i = 0; i < terms; i++)//bubble sort
    {
        for(int j = 0; j < terms - i; j++)
        {
            if(termArray[j].exp < termArray[j+1].exp)
            {
                Term temp = termArray[j];
                termArray[j] = termArray[j+1];
                termArray[j+1] = temp;
            }
        }
    }
    terms++;
}

 

3-3) main.cpp

#include "polynomial.h"
#include <iostream>

int main()
{
	Polynomial f, g;
	
	f.CreateTerm(-4, 3);
	f.CreateTerm(2.3, 2);
	f.CreateTerm(-3, 0);
	
	std::cout << "f = ";
	f.Print();
    
	g.CreateTerm(3, 4);
	g.CreateTerm(-8, 0);
	g.CreateTerm(-4, 3);

    
    
	std::cout << "g = ";
	g.Print();
	
	g.CreateTerm(5, 2);
	std::cout << "g (creating a new term) = ";
	g.Print();
	
	// copy constructor test
	std::cout << "h (created from f) = ";
	Polynomial h = f;
	h.Print();
	
	// assignment operator test
	std::cout << "h (assigned from g) = ";
	h = g;	
	h.Print();
	
	// Add test
	std::cout << "f + g = ";
	h = f + g;	
	h.Print();
	
	// Subtract test
	std::cout << "f - g = ";
	h = f - g;
	h.Print();
	
    
    //Multiplication test
    std::cout << "f * g = ";
    Polynomial j;
    j = f * g;
    j.Print();
    
    
	// Equal test
	if(f == g)
		std::cout << "f and g are same" << std::endl;
	else
		std::cout << "f and g are different" << std::endl;
	
	// Eval test
	std::cout << "f(3.5) is " << f.Eval(3.5) << std::endl;
		
	// Derivative test
	Polynomial i = f.Derivative(); 
	std::cout << "Derivative of f = ";
	i.Print();
	
	return 0;
}

올바르게 작동시 도출되는 결과

코드 작성 후 도출된 결과(곱셈은 따로 main.cpp 조작을 통해 추가함)

점수 : 89/100

P.S. 수업이 끝나고 한 학기 후에서야 valgrind의 존재를 알게 됐다...역시나 첫번째 과제를 돌려보니 memory leak가 있었고 그건 바로 대입 연산자에서 delete[] termArray를 안해서였다. 이미 디폴트 생성자로 termArray 배열이 생성되어 있기 때문에 완전한 대입을 하기 위해서는 이미 있는 termArray 배열을 메모리 해제를 해줬어야 하는 것이다. 그래도 이제서야 과제 점수에 대한 의문점이 풀려서 다행이다.