원형 연결 리스트 - 다항식의 연산(덧셈, 곱셈: 클래스와 operator, 반복자)

[연결 리스트]

1. 여러가지 연결 리스트 개념과 코드 : hello70825.tistory.com/158

2. 여러가지 연결 리스트를 이용한 알고리즘 문제 풀이: hello70825.tistory.com/159

3. 이중 연결 리스트 - 다항식의 연산(덧셈, 곱셈 : 구조체와 함수): hello70825.tistory.com/160

4. 이중 연결 리스트 - 다항식의 연산(덧셈, 곱셈 : 클래스와 operator): hello70825.tistory.com/219

5. 원형 연결 리스트 - 다항식의 연산(덧셈, 곱셈: 클래스와 operator, 반복자): hello70825.tistory.com/223

 

 

=========================================================================

 

이번 글도 과제입니다. 4번째 글 코드를 짤 때, 수업에서 막 배열을 이용해서 만지작 거리는 수업이였는데, 교수님이 배열 언급없이 클래스와 operator를 이용해서 다항식의 연산을 구현하라고 하셔서 연결리스트로 만들다가 비슷한걸 2개나 만들게 됐네요

 

코드는 4번째 글에 있는 코드를 변형해서 만든 것이라 4번째 글을 읽고 오신 분이라면 좀 더 이해하기 수월할 것이라고 생각이 됩니다. 그런데 둘 다 코드가 수백줄이 넘어가서 굳이 4번째 글을 읽고 올 필요는 없습니다.

 

4번째 글 코드와 현재 글 코드의 차이점

	4번째 글 코드	현재 글 코드
연결리스트 조작	포인터 변수를 이용해 직접 접근하여 조작	반복자를 이용해 간접 접근으로 조작
머리노드 기본값	nullptr	0*x^9999로 설정
꼬리노드 유무	이중연결리스트이므로 있음	원형연결리스트이므로 없음
capacity 변수	있음	없음

 

이번 코드는 원형 연결 리스트입니다. 자료구조론 교재에서는 머리노드에 기본값이 있기 때문에 교재에 맞게 다항식이 만들어지면 값이 있는 노드를 만들고 바로 헤드노드에 저장하도록 만들었습니다. 헤드노드의 값은 테스트케이스로 입력되지 않는 수인 계수가 0이고, 지수가 9999인 단항식을 머리노드로 넣어서 값을 넣는 방식으로 코드를 짰습니다.

 

 

============================================================================

 

입력 형식

입력 형식은 한 다항식에 (계수,지수)를 연속적으로 적고, 공백을 기준으로 다항식 A(x), B(x), C(x)를 받는 것 입니다. 

 

ex)

A(x)

B(x)

C(x)

위와 같을 경우

(1,3)(1,2)(3,1) (1,2)(5,1)(7,0) (5,4)(1,0)

으로 적을 수 있습니다.

 

아니면 순서를 섞어서

(3,1)(1,3)(1,2) (5,1)(7,0)(1,2) (1,0)(5,4)

가 들어와도 잘 정리된 다항식이 나옵니다.

 

종료 조건은 #만 입력하고 엔터를 누르면 프로그램이 끝납니다.

 

주의할 점

- 다항식이 0이 아니여야함(T(x), D(x)도 포함)

- 입력값: 지수는 자연수 범위, 계수는 정수 범위입니다.

 

ex) (0,0) (1,0) (0,1)(1,2)

A(x) = 0이라 불가능

C(x) = (1,2)가 있어서 (0,1)같은 무의미한 값을 붙여도 가능

 

ex) (1,-1) (2,2) (3,3)

A(x) = x^(-1)로 지수가 음수이므로 불가능

 

ex (1,1)(1,1)(1,1) (2,2) (3,3)

이떄 A(x) = 3x로 나옴

 

===========================================================================

기능 설명

 

클래스

1. 단항식, Term : 계수, 지수, 다음 노드의 주소를 가지고 있는 클래스

2. 다항식, Polynomial: 헤드노드, 곱하기에서 사용할 val 포인터 변수 사용

3. Polynomial:: iterator: 반복자. 반복자를 이용하여 연결리스트 조작을 함

 

오퍼레이터

1. >> : 입력값을 받을 때

2. << : 출력을 할 때

3. * : 다항식끼리 곱하기

4. +: 다항식끼리 더하기

5. iterator ==: 주소값이 서로 같은지 확인

6. iterator != : 주소값이 서로 다른지 확인

7. iterator ++: 다음 단항식으로 넘어감

 

함수

1. operator >>

• find_error(string x): 입력값 x가 입력 형식에 맞게 입력됐는지 확인

2. Polynomial

• create_term(coef, exp): 계수가 coef, 지수가 exp인 단항식을 새로 만들어줌
• add_term(coef, exp): create_term(coef, exp)를 이용하여 다항식에 단항식을 내림차순으로 연결함
• sMultPoly(int c, int e): 다항식A와 다항식B를 서로 곱하여 새로 만든 다항식 T에 넣어줌
• begin: 반복자(iterator)로 접근해야하므로 머리노드를 가져올 때 begin을 사용함

3. Polynomial::iterator

• next(): 다음 단항식을 가져옴
• new_next(new_next, t): t = 0이면 현재 단항식의 다음 단항식은 new_next임. t = 1이면 new_next의 다음 단항식은 현재 단항식임
• plus(new_coef): 현재 단항식의 계수에 new_coef를 더해줌(다항식의 덧셈, 곱셈중 지수의 계수가 같을 때 사용)
• coef(): 현재 단항식의 계수를 가져옴
• exp(): 현재 단항식의 지수를 가져옴

4. evalPoly(x): 다항식의 변수에 값을 넣으면 어떤 값이 나오는지 확인함

 

 

===========================================================================

 

코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
 
bool find_error(string x); // 입력 값 오류 찾기
 
bool sharp = false; // #이 나오면 중단
bool error_flag = false; // 입력형식이 오류인 입력 값은 전부다 새로 입력 받게 함
 
class Term {
public:
    int coef;
    int exp;
    Term* next;
    Term() :coef(0), exp(0), next(nullptr) {};
};
 
class Polynomial {
public:
    Term* head;
    Polynomial* val; // sMultPoly 함수에서 사용
    Polynomial() :head(nullptr), val(nullptr) {
        Term* new_term = create_term(0, 9999);
        head = new_term;
        new_term->next = head;
    };
 
    // 반복자 구현
    class iterator {
        Term* current;
    public:
        iterator(Term* p) : current(p) {}
        iterator& operator++() {
            current = current->next;
            return *this;
        }
        Term* next() { return current->next; }
        void new_next(Term* new_next, int t) {
            if (t == 0) current->next = new_next;
            else new_next->next = current;
        }
        void plus(int new_coef) { current->coef += new_coef; }
        int coef() { return current->coef; }
        int exp() { return current->exp; }
        bool operator !=(const iterator t) { return current != t.current; }
        bool operator ==(const iterator t) { return current == t.current; }
    };
 
    iterator begin() {
        return iterator(head);
    }
 
    // term을 만들어줌
    Term* create_term(int c, int e) {
        Term* new_term = new Term();
        new_term->coef = c;
        new_term->exp = e;
        return new_term;
    }
    // 식에 항을 반복자를 이용하여 지수의 내림차순으로 추가/변경
    void add_terms(int coef, int exp) {
        Term* term = create_term(coef, exp);
        Polynomial::iterator ait = (*this).begin(); // 반복자 사용
        if (ait.next() == head) {
            ait.new_next(term, 0);
            ait.new_next(term, 1);
        }
        else {
            Polynomial::iterator ait2 = (*this).begin(); // 겹치는 지수가 없으면 ait와 ait2 사이에 Term을 넣을 예정
            ++ait2;
            int flag = 0; //제일 크면 3, ait와 ait2 사이에 있으면 2, ait와 같으면 1, 제일 작으면 0
            do {
                if (ait.exp() > term->exp && term->exp > ait2.exp()) {
                    flag = 2;
                    break;
                }
                if (ait.exp() == term->exp) {
                    flag = 1;
                    break;
                }
                ++ait;
                ++ait2;
            } while (ait != (*this).begin());
            if (flag == 2) {
                ait.new_next(term, 0);
                ait2.new_next(term, 1);
            }
            else if (flag == 1) {
                ait.plus(term->coef);
            }
            else {
                Polynomial::iterator ait3 = (*this).begin();
                Polynomial::iterator ait4 = ++(*this).begin();
                for (; ait4 != (*this).begin(); ++ait4) {
                    ait3 = ait4;
                }
                ait3.new_next(term, 0);
                ait4.new_next(term, 1);
            }
        }
    }
 
    // 4.다항식의 단항 곱셈
    void sMultPoly(int c, int e) {
        Polynomial::iterator ait = (*val).begin();
        ++ait;
        do {
            add_terms(ait.coef() * c, ait.exp() + e);
            ++ait;
        } while (ait != (*val).begin());
    }
 
    // add_poly가 오름차순으로 값을 추가하는 것이므로 +, *는 add_poly만 사용해서 넣어줌
    // 3.다항식의 덧셈
    Polynomial operator+(Polynomial& poly) {
        Polynomial new_poly = Polynomial();
        Polynomial::iterator ait = (*this).begin();
        ++ait;
        do {
            new_poly.add_terms(ait.coef(), ait.exp());
            ++ait;
        } while (ait != (*this).begin());
        ait = poly.begin();
        ++ait;
        do {
            new_poly.add_terms(ait.coef(), ait.exp());
            ++ait;
        } while (ait != poly.begin());
        return new_poly;
    }
 
    // 5.다항식의 곱셈
    Polynomial operator*(Polynomial& poly) {
        Polynomial new_poly = Polynomial();
        new_poly.val = this;
        Polynomial::iterator ait = poly.begin();
        ++ait;
        do {
            new_poly.sMultPoly(ait.coef(), ait.exp());
            ++ait;
        } while (ait != poly.begin());
        return new_poly;
    }
 
    // 6.다항식의 값 계산
    int evalPoly(int x) {
        long long res = 0;
        Polynomial::iterator ait = (*this).begin();
        ++ait;
        do {
            res += ait.coef() * pow(x, ait.exp());
            ++ait;
        } while (ait != (*this).begin());
        return res;
    }
 
};
 
 
// 1.다항식의 입력
istream& operator>>(istream& is, Polynomial& poly) {
    string x;
    is >> x;
    if (error_flag) return is;
 
    // #이 나오면 종료하게 만들어줌. B와 C에 #이 나온다면 오류처리
    sharp = false;
    if (x == "#") {
        sharp = true;
        error_flag = true;
        return is;
    }
 
    // 입력 형식에 오류가 있는지 확인함
    error_flag = find_error(x);
    if (error_flag) {
        return is;
    }
 
    //이제 파싱하여 숫자들을 뽑아냄
    char s[1000];
    int n = 0;
    strcpy(s, x.c_str());
    for (int i = 0; i < strlen(s); i++) {
        if (s[i] == ')') n += 1;
    }
 
    for (int i = 0; i < n; i++) {
        char* p, * q;
        if (i == 0) p = strtok(s, ",");
        else p = strtok(NULL, ",");
        for (int j = 1; j <= strlen(p); j++) p[j - 1] = p[j];
        q = strtok(NULL, ")");
 
        int coef = stoi(p);
        int exp = stoi(q);
        // 계수가 0이면 그냥 통과
        if (coef == 0) {
            continue;
        }
 
        // 지수가 음수이면 오류 처리
        if (exp < 0) {
            error_flag = true;
            return is;
        }
        poly.add_terms(coef, exp);
    }
 
    return is;
}
 
bool find_error(string x) {
    bool error = false;
    string a = "(", b = ")", c = ",";
    int l = 0, r = 0, comma = 0; // l = (의 개수, r = )의 개수
 
    // (,) 형식으로 되어있는지 확인
    for (int i = 0; i < x.size(); i++) {
        if (error) break;
        string y;
        y = x[i];
        if (i == 0 && y != a) error = true;
 
        if (y == a) { // (일 때
            if (l == r && r == comma) l += 1;
            else error = true;
        }
        if (y == b) { // )일 때
            if (l == comma && l == r + 1) r += 1;
            else error = true;
        }
        if (y == c) { // ,일 때
            if (l - 1 == comma && comma == r) comma += 1;
            else error = true;
        }
    }
    if (!(l == comma && l == r)) error = true;
    if (error) return error;
 
    //숫자가 정상적으로 들어있는지 확인
    int num = 0;
    for (int i = 0; i < strlen(x.c_str()); i++) {
        if ('0' <= x.c_str()[i] && x.c_str()[i] <= '9') num++;
        if (x.c_str()[i] == ',' || x.c_str()[i] == ')') {
            if (num == 0) error = true;
            num = 0;
        }
    }
    if (error) return error;
 
    //이제 괄호랑 콤마는 정상적이므로 안에 들어있는 숫자가 정상적인지 학인
    char s[1000];
    strcpy(s, x.c_str());
    char* p = strtok(s, ",");
    for (int i = 0; i < l; i++) {
        if (error) break;
        int minus = 0; // - 부호가 1개만 있어야함
        if (i != 0) p = strtok(NULL, ",");
 
        if (p[1] == '-') minus = 2;
        else minus = 1;
 
        for (int k = minus; k < strlen(p); k++) {
            if (!(48 <= int(p[k]) && int(p[k]) <= 57))
            {
                error = true;
            }
        }
 
        if (error) break;
        p = strtok(NULL, ")");
        if (p[0] == '-') minus = 1;
        else minus = 0;
        for (int k = minus; k < strlen(p); k++) {
            if (!(48 <= int(p[k]) && int(p[k]) <= 57)) error = true;
        }
    }
    return error;
}
 
// 2.다항식의 출력
ostream& operator<<(ostream& os, Polynomial& p) {
    Polynomial::iterator ait = p.begin();
    ++ait;
    do {
        if (ait.exp() == 0) {
            os << ait.coef();
            break;
        }
        if (ait.coef() == 1) { os << 'x'; }
        else if (ait.coef() == -1) { os << "-x"; }
        else { os << ait.coef() << 'x'; }
 
        if (ait.exp() != 1) { os << '^' << ait.exp(); }
        ++ait;
        if (ait.coef() > 0) { os << '+'; }
    } while (ait != p.begin());
    return os;
}
 
int main()
{
    while (true) {
        Polynomial a, b, c, d, t;
        int x;
        error_flag = false;
 
        cout << "> Input polynomials a, b, c: ";
        cin >> a;
        if (sharp) break;
        cin >> b;
        cin >> c;
        if (error_flag) {
            cout << "입력 형식이 맞는지 확인해주세요." << endl << endl;
            continue;
        }
        cout << "A(x) = " << a << endl;
        cout << "B(x) = " << b << endl;
        cout << "C(x) = " << c << endl;
        t = a * b;
        d = t + c;
        cout << "T(x) = " << t << endl;
        cout << "D(x) = " << d << endl;
        cout << "> Input x value: ";
        cin >> x;
        cout << "A*B+C = " << d.evalPoly(x) << endl << endl;
    }
}