이중 연결 리스트 - 다항식의 연산(덧셈, 곱셈 : 클래스와 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

 

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

 

 

자료구조 과제로 한건데 과제는 class랑 operator로 구현하라고 했어서 올립니다.

이중 연결 리스트로 구현했습니다.

 

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

 

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

T(x) =  A(x) * B(x)이고, D(x) = T(x) + C(x)입니다. 그리고 x값을 입력 받는데 D(x)에 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로 나옴

 

 

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

 

코드

 

#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* prev;
    Term() :coef(0), exp(0), next(nullptr), prev(nullptr) {};
};
 
class Polynomial {
public:
    Term* head;
    Term* tail;
    Polynomial* val; // sMultPoly 함수에서 사용
    int capacity; // 항의 개수
    Polynomial() :head(nullptr), tail(nullptr), val(nullptr), capacity(0) {};
 
    // 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);
 
        if (head == nullptr) {
            head = term;
            tail = term;
            capacity += 1;
        }
        else {
            Term* dest = head;
            int flag = 0; //현재 노드의 지수보다 크면 2, 같으면 1, 제일 작은 지수값이면 0
            for (int i = 0; i < capacity; i++) {
                if (dest->exp < term->exp) {
                    flag = 2;
                    break;
                }
                if (dest->exp == term->exp) {
                    flag = 1;
                    break;
                }
                dest = dest->next;
            }
            if (flag == 2) {
                capacity += 1;
                if (dest == head) {
                    head->prev = term;
                    term->next = head;
                    head = term;
                }
                else {
                    term->prev = dest->prev->next;
                    dest->prev->next = term;
                    dest->prev = term;
                    term->next = dest;
                }
            }
            else if (flag == 1) {
                dest->coef += term->coef;
                if (dest->coef == 0) {
                    dest->prev->next = dest->next;
                    dest->next->prev = dest->prev;
                    delete dest;
                }
                delete term;
            }
            else {
                capacity += 1;
                tail->next = term;
                term->prev = tail;
                tail = term;
            }
        }
    }
 
    // 4.다항식의 단항 곱셈
    void sMultPoly(int c, int e) {
 
        for (Term* dest = val->head; dest != nullptr; dest = dest->next) {
            add_terms(dest->coef * c, dest->exp + e);
        }
    }
 
    // add_poly가 오름차순으로 값을 추가하는 것이므로 +, *는 add_poly만 사용해서 넣어줌
    // 3.다항식의 덧셈
    Polynomial operator+(Polynomial& poly) {
        Polynomial new_poly = Polynomial();
        for (Term* dest = head; dest != nullptr; dest = dest->next) {
            new_poly.add_terms(dest->coef, dest->exp);
        }
        for (Term* dest = poly.head; dest != nullptr; dest = dest->next) {
            new_poly.add_terms(dest->coef, dest->exp);
        }
        return new_poly;
    }
 
    // 5.다항식의 곱셈
    Polynomial operator*(Polynomial& poly) {
        Polynomial new_poly = Polynomial();
        new_poly.val = this;
        for (Term* dest = poly.head; dest != nullptr; dest = dest->next) {
            new_poly.sMultPoly(dest->coef, dest->exp);
        }
        return new_poly;
    }
 
    // 6.다항식의 값 계산
    int evalPoly(int x) {
        long long res = 0;
        for (Term* dest = head; dest != nullptr; dest = dest->next) {
            res += dest->coef * pow(x, dest->exp);
        }
        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;
 
    //이제 괄호랑 콤마는 정상적이므로 안에 들어있는 숫자가 정상적인지 학인
    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) {
    int k = p.capacity - 1;
    int z = 0;
    for (Term* dest = p.head; dest != nullptr; dest = dest->next) {
        if (dest->exp == 0) {
            os << dest->coef;
            continue;
        }
 
        if (dest->coef == 1) {
            os << 'x';
        }
        else if (dest->coef == -1) {
            os << "-x";
        }
        else {
            os << dest->coef << 'x';
        }
 
        if (dest->exp != 1) {
            os << '^' << dest->exp;
        }
        if (k != 0) {
            if (dest->next->coef > 0)os << '+';
            k--;
        }
    }
 
    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;
            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;
    }
}