문제들 종합 : 다항식 덧셈, 뺄셈, 곱셈 구현
#include <iostream>
using namespace std;
template <typename T> class Chain;
template <typename T>
class ChainNode {
private:
T data;
ChainNode<T>* link;
public:
ChainNode(T element = 0, ChainNode* next = NULL) {
data = element;
link = next;
}
T getData() { return data; }
ChainNode* Link() { return link; }
friend class Chain<T>;
template <typename T>
friend ostream& operator<<(ostream& os, Chain<T>& c); //출력
};
template <typename T>
class Chain {
private:
ChainNode<T>* first;
ChainNode<T>* last;
public:
Chain() { first = NULL; }
ChainNode<T>* getFirst() { return first; } //처음 노드 반환
ChainNode<T>* Insert(ChainNode<T>* x, T i) { //노드 추가
if (first) {
ChainNode<T>* temp = new ChainNode<T>(i, x->link);
x->link = temp; //x가 temp를 가르키도록
return x->link; //위치를 반환해야 그 다음 위치에 값을 대입
}
else { //기존 노드가 없을 경우
first = new ChainNode<T>(i);
return first;
}
}
int Length() {
int len = 0;
ChainNode* temp = first;
while (temp != NULL) {
temp = temp->link;
len++;
}
return len;
}
void Delete(ChainNode<T>* x) {
if (first == NULL) {
cout << "체인은 비어있다" << endl;
return;
}
if (x == first)
first = first->link; //다음 노드를 가리킨다
else {
ChainNode<T>* temp = first;
while (temp->link != x) {
temp = temp->link; //x 전 노드를 찾아간다
}
temp->link = x->link; //x 다음을 temp와 연결시켜 자연스럽게 x가 없어지도록 한다
}
delete x;
}
void InsertBack(const T& item) {
if (first) {
last->link = new ChainNode<T>(item);
last = last->link;
last->link = NULL;
}
else {
first = last = new ChainNode<T>(item);
first->link = NULL;
}
}
class ChainIterator {
private:
ChainNode<T>* current;
public:
ChainIterator(ChainNode<T>* startNode = NULL) { current = startNode; }
T getData() { return current->data; }
T& operator*() const { return current->data; }
T* operator->() { return ¤t->data; }
ChainIterator& operator++() {
current = current->link;
return *this;
}
ChainIterator operator++(int) {
ChainIterator old = *this;
current = current->link;
return old;
}
bool operator!=(const ChainIterator right) const {
return current != right.current;
}
bool operator==(const ChainIterator right) const {
return current = right.current;
}
bool operator&&(const ChainIterator right) const {
return current && right.current;
}
template <typename T>
friend ostream& operator<<(ostream& os, Chain<T>& c); //출력
};
ChainIterator begin() { return ChainIterator(first); }
ChainIterator end() { return ChainIterator(0); }
template <typename T>
friend ostream& operator<<(ostream& os, Chain<T>& c); //출력
};
template <typename T>
ostream& operator<<(ostream& os, Chain<T>& c) {
typename Chain<T>::ChainIterator i = c.begin();
while (i != c.end()) {
os << i.getData() << "->";
i++;
}
os << i.getData();
os << endl;
return os;
}
class Polynomial {
public:
struct Term {
int coef;
int exp;
Term Set(int c, int e) { coef = c; exp = e; return *this; };
};
private:
Chain<Term> poly;
public:
Polynomial() {}
void InsetTerm(Term& element) {
poly.InsertBack(element);
}
Polynomial operator+(Polynomial& b) {
Term temp;
Chain<Term>::ChainIterator ai = poly.begin(), bi = b.poly.begin();
Polynomial c;
while (ai && bi) {
if (ai->exp == bi->exp) {
int sum = ai->coef + bi->coef;
if (sum)
c.poly.InsertBack(temp.Set(sum, ai->exp));
ai++;
bi++;
}
else if (ai->exp < bi->exp) {
c.poly.InsertBack(temp.Set(bi->coef, bi->exp));
bi++;
}
else {
c.poly.InsertBack(temp.Set(ai->coef, ai->exp));
ai++;
}
}
while (ai != 0) {
c.poly.InsertBack(temp.Set(ai->coef, ai->exp));
ai++;
}
while (bi != 0) {
c.poly.InsertBack(temp.Set(bi->coef, bi->exp));
bi++;
}
return c;
}
Polynomial operator-(Polynomial& b) {
Term temp;
Chain<Term>::ChainIterator ai = poly.begin(), bi = b.poly.begin();
Polynomial c;
while (ai && bi) {
if (ai->exp == bi->exp) {
int sub = ai->coef - bi->coef;
if (sub)
c.poly.InsertBack(temp.Set(sub, ai->coef));
ai++;
bi++;
}
else if (ai->exp < bi->exp) {
c.poly.InsertBack(temp.Set(bi->coef, bi->exp));
bi++;
}
else {
c.poly.InsertBack(temp.Set(ai->coef, ai->exp));
ai++;
}
}
while (ai != 0) {
c.poly.InsertBack(temp.Set(ai->coef, ai->exp));
ai++;
}
while (bi != 0) {
c.poly.InsertBack(temp.Set(bi->coef, bi->exp));
bi++;
}
return c;
}
Polynomial operator*(Polynomial& b) {
Term temp;
Chain<Term>::ChainIterator ai = poly.begin(), bi = b.poly.begin();
Polynomial c;
while (ai != 0) {
while (bi != 0) {
int mul = ai->coef * bi->coef;
int e = ai->exp + bi->exp;
c.poly.InsertBack(temp.Set(mul, e));
bi++;
}
bi = b.poly.begin();
ai++;
}
return c;
}
friend ostream& operator<<(ostream& os, Polynomial& p);
};
ostream& operator<<(ostream& os, Polynomial& p) {
Chain<Polynomial::Term>::ChainIterator i = p.poly.begin();
while (1) {
Polynomial::Term term = *i;
os << term.coef << "x^(" << term.exp << ")";
if (++i != p.poly.end())
os << " + "; //끝이 아닐 경우 +
else {
os << " ";
break;
}
}
return os;
}
int main() {
Polynomial p1, p2, p3, p4, p5;
Polynomial res;
int n1, n2;
Polynomial::Term temp;
cout << "p1 다항식 원소의 개수를 입력하세요 : ";
cin >> n1;
for (int i = 0; i < n1; i++) {
int c, e;
cout << "계수와 지수 입력 : ";
cin >> c >> e;
temp.Set(c, e);
p1.InsetTerm(temp);
}
cout << "p2 다항식 원소의 개수를 입력하세요 : ";
cin >> n2;
for (int i = 0; i < n2; i++) {
int c, e;
cout << "계수와 지수 입력 : ";
cin >> c >> e;
temp.Set(c, e);
p2.InsetTerm(temp);
}
cout << "<다항식 p1>" << endl << p1 << endl;
cout << "<다항식 p2>" << endl << p2 << endl;
p3 = p1 + p2;
cout << "<다항식 p3 = p1 + p2 >" << endl << p3 << endl;
p4 = p1 - p2;
cout << "<다항식 p4 = p1 - p2 >" << endl << p4 << endl;
p5 = p1 * p2;
cout << "<다항식 p5 = p1 * p2 >" << endl << p5 << endl;
}
// 출력
* 곱셈에서 지수가 같은 항끼리 더하는 것은 구현하지 못했음 (다음에 시간 날때 다시 구현할게 ~ ㅠㅠ)
* 곱셈 결과 값에 8x과 12x를 더해야함 ㅜ ~ 그거 구현 해야함 !!