[C++] 자료구조 9주차 과제6

과제 4 다항식 입력, 출력, 계산하는 프로그램을 연결리스트로 구현한다. (리스트 반복자 반드시 사용)

다항식은 객체(class)로 생성해야 하며, 다항식 연산을 위하여 연산자 오버로딩 기능을 이용한다. 

• 다항식 a, b, c를 입력받아 문제에 주어진 연산을 수행한다.(다양한 입력 예를 테스트하는 것을 추천함)
• 다항식 입력은 (계수, 지수) 표현 형태를 이용한다.
• 다항식의 출력 형식은 첨부파일과 같은 형식을 따른다. 
• 첨부파일의 프로그램 코드를 실행한다.
• 헤드노드를 갖는 원형연결리스트로 구현한다.(리스트 반복자 반드시 사용)
• 문자열 입력으로 .이 입력될 때까지 재입력을 받도록 한다.
• 헤더와 메인 파일은 분리하지 않고 한 개의 cpp파일을 제출한다. 
• 입력값을 반복적으로 받을 수 있게 하고, .(마침표)를 입력하면 프로그램을 종료하도록 한다.

입력물: 다항식 a, b, c, 정수 x

출력물: 첨부파일의 프로그램 코드를 실행한 결과물(출력 결과물).

 

* 연산자 오버로딩을 구현해야함.

* 프로그램 내용 외에 다른 내용이 출력된다면 감점이 될 수 있으니 유의바람.

 

Code

#include <iostream>
 
using namespace std;
 
template <class T> class CircularListWithHeader;  // 전방선언
 
struct Term
{
    int coef;
    int exp;
    Term Set(int c, int e) { coef = c; exp = e; return *this; }  // c*x^e
};
 
template <class T>
class Node
{
public:
    friend class CircularListWithHeader<T>;
    Node(T element = 0, Node* next = 0)
    {
        data = element;
        link = next;
    }
private:
    Term data;
    Node* link;
};
 
template <class T>
class CircularListWithHeader
{
public:
    CircularListWithHeader() { head = 0; last = 0; current = 0; };
    void InsertBack(T data);
    class iterator
    {
        Node<T>* current;
    public:
        iterator(Node<T>* p) : current(p) {}
        iterator& operator++()  // 사전증가
        {
            current = current->link;
            return *this;  // current가 current->link가 된 상태의 list가 return됨
        }
        iterator operator++(int)  // 사후증가
        {
            iterator old = *this;
            current = current->link;
            return old;  // return 후에 current 증가
        }
        T& operator*() const { return current->data; }  // 내용을 주면 주소로 받음
        T* operator->() const { return &current->data; }  // 주소를 넘겨주면 pointer type으로 받음
        bool operator!=(const iterator t) { return current != t.current; }  // 동등검사
        bool operator==(const iterator t) { return current == t.current; }
    };
    iterator begin() {
        return iterator(head);
    }
    iterator end() {
        return iterator(head);
    }
 
private:
    Node<T>* head;  // 첫 노드
    Node<T>* last;  // 마지막 노드
    Node<T>* current;  // 현재 노드
    //int numOfNodes;  // 노드의 개수
};
 
template <class T>
void CircularListWithHeader<T>::InsertBack(T data)
{
    Term temp;
    temp.coef = 0;
    temp.exp = -1;
 
    Node<T>* NewNode = new Node<T>(data);
    if (head) {
        last->link = NewNode;
        last = NewNode;
        last->link = head;
    }
    else {
        Node<T>* HeadNode = new Node<T>(temp);
        HeadNode->link = NewNode;
        head = HeadNode;
        NewNode->link = head;
        last = NewNode;
    }
}
 
class Polynomial
{
public:
    Polynomial operator+(Polynomial&);  // *this와 B(x)를 더한 결과 반환, 연산자 오버로딩
    Polynomial operator*(Polynomial&);  // *this와 B(x)를 곱한 결과 반환, 연산자 오버로딩
    Polynomial sMultPoly(Term data);  // 다항식의 단항 곱셈
    friend istream& operator>>(istream&, Polynomial&);  // 다항식의 입력. 연산자 오버로딩
    friend ostream& operator<<(ostream&, Polynomial&);  // 다항식의 출력. 연산자 오버로딩
    int evalPoly(int x);  // *this에 x를 대입해서 계산한 결과 반환
 
private:
    CircularListWithHeader<Term> poly;
};
 
istream& operator>>(istream& in, Polynomial& p)
{
    Term term;
    string input_poly;
    int coef = 0;
    int exp = 0;
    int count = 1;
 
    input_poly.clear();  // string poly 초기화
    in >> input_poly;  // (계수,지수)(계수,지수)...꼴의 입력을 통째로 string으로 받아옴
 
    if (input_poly[0] == '.') exit(0);  // 1. . 종료 (문자열 입력으로 .이 입력될 때까지 재입력)
 
    for (int i = 0; i < input_poly.length(); i++)  // 계수, 지수는 0~9 정수
    {
        if (isdigit(input_poly[i])) {  // isdigit : 문자가 숫자 0~9 사이에 속하는지 검사하는 함수
            // isdigit 성립하면서 count가 홀수면 그것은 계수, 짝수면 지수
            if (count % 2 == 1) coef = input_poly[i] - '0';  // char 데이터형을 int로 변환하기 위해 -'0'
            if (count % 2 == 0) {
                exp = input_poly[i] - '0';
                p.poly.InsertBack(term.Set(coef, exp));
            }
            count++;
        }
    }
 
    return in;
}
 
ostream& operator<<(ostream& out, Polynomial& p)
{
    CircularListWithHeader<Term> list;
    CircularListWithHeader<Term>::iterator iter = p.poly.begin();
    iter++;  // 헤더노드 다음 노드부터 출력
 
    while (1)  // 계수, x^ or x or none, 지수, +연산자 순으로 차례대로 출력
    {
        if (iter->coef > 1) out << iter->coef;  // possible coef 1~9 중 1보다 큰 계수만 출력
        if ((iter->coef == 1) && (iter->exp == 0)) out << iter->coef;  // 상수항이 1일 때의 예외처리
        if (iter->exp > 1) out << "x^";  // 지수가 2 이상이어야 x^num 꼴로 출력
        if (iter->exp == 1) out << "x";  // 지수가 1일땐 x만 출력
        if (iter->exp > 1) out << iter->exp;  // 지수가 2 이상일 때만 지수 따로 출력
        if (++iter != p.poly.end()) out << " + ";  // 계수가 1~9(양수)니까 +만 출력 (마지막 노드까지, 마지막 항 뒤에 + 출력 되지 않도록 주의)
        else break;
    }
    out << endl;
 
    return out;
}
 
Polynomial Polynomial::operator+(Polynomial& b)
{
    Term temp;
    CircularListWithHeader<Term>::iterator ai = poly.begin(), bi = b.poly.begin();
    Polynomial result;
    // 리스트가 비어있지 않을 때 헤더노드 다음으로 넘어감
    if (ai != NULL) { ai++; }
    bi++;
 
    while (ai != NULL && bi != NULL)  // 종료조건은 둘 다 exp == -1 일 때
    {
        if (ai->exp == bi->exp)
        {
            if (ai->exp == -1) break;  // ai가 null이라면 bi 그대로 return
            int sum = ai->coef + bi->coef;
            if (sum) result.poly.InsertBack(temp.Set(sum, ai->exp));  // 계수의 합이 0이 아닐때 노드 추가
            ai++; bi++;
        }
        else if (ai->exp < bi->exp)
        {
            result.poly.InsertBack(temp.Set(bi->coef, bi->exp));
            bi++;
        }
        else
        {
            result.poly.InsertBack(temp.Set(ai->coef, ai->exp));
            ai++;
        }
    }
    if (ai != NULL) {
        while (ai->exp != -1) {
            result.poly.InsertBack(temp.Set(ai->coef, ai->exp));
            ai++;
        }
    }
    if (ai == NULL) {
        while (bi->exp != -1) {
            result.poly.InsertBack(temp.Set(bi->coef, bi->exp));
            bi++;
        }
    }
 
    return result;
}
 
Polynomial Polynomial::sMultPoly(Term data)  // 2. sMultPoly(c,e)
{
    Term temp;
    CircularListWithHeader<Term>::iterator iter = poly.begin();
    Polynomial sMultResult;  // 계산 결과 저장
    iter++;
 
    // 기준이 되는 다항식의 각 항에, 입력된 단항식의 계수를 곱하고, 지수는 더해준다.
    while (1)
    {
        if (iter->exp == -1) break;  // iter가 null이라면 sMultResult 그대로 return
        int smult_coef = iter->coef * data.coef;
        int smult_exp = iter->exp + data.exp;
        sMultResult.poly.InsertBack(temp.Set(smult_coef, smult_exp));
        iter++;
    }
 
    return sMultResult;
}
 
Polynomial Polynomial::operator*(Polynomial& b)
{
    Term temp;
    CircularListWithHeader<Term>::iterator ai = poly.begin(), bi = b.poly.begin();
    Polynomial tempMult;  // sMultPoly이 return하는 polynomial 임시로 저장
    Polynomial MultResult;  // 계산 결과 저장
    ai++;
 
    // B(x)에 A(x)의 단항식을 차례대로 곱한다. 그 곱셈 결과들을 다 더해준다.
    while (1)
    {
        if (ai->exp == -1) return MultResult;
        tempMult = b.sMultPoly(temp.Set(ai->coef, ai->exp));
        MultResult = MultResult + tempMult;
        ai++;
    }
 
    return MultResult;
}
 
int Polynomial::evalPoly(int x)  // 2. evalPoly(c)
{
    CircularListWithHeader<Term>::iterator iter = poly.begin();
    iter++;
    int eval = 0;
 
    while (iter != poly.end())
    {
        eval += iter->coef * pow(x, iter->exp);
        iter++;
    }
 
    return eval;
}
 
int main()
{
    cout << "다항식 A,B,C 와 x 값을 입력하세요 >> ";
    while (1) {  // .받을때까지 재입력
        Polynomial a, b, c, d, t;  // a,b,c 다항식 읽고 생성, t=a*b, d=t+c
        int x;  // 다항식의 x에 대입할 값
        cin >> a;
        cin >> b;
        cin >> c;
        cout << "A(x) = " << a;
        cout << "B(x) = " << b;
        cout << "C(x) = " << c;
        t = a * b;
        d = t + c;
        cout << "T(x) = " << t;
        cout << "D(x) = " << d;
        cin >> x;
        cout << "x = " << x << " --> " << d.evalPoly(x) << '\n' << endl;
        cout << "다항식 A,B,C 와 x 값을 입력하세요 >> ";
    }
 
    return 0;
}

실행결과

 

점수 10/10

 

 

  ❤와 댓글은 큰 힘이 됩니다. 감사합니다 :-)