[c++] 연결리스트 이용한 다항식 덧셈/뺄셈/곱셈

1. 다항식 구성

: 계수 + 차수 ( 음수도 구별하도록 코드 작성하였음)

: string으로 식을 입력하면 (계수 + 차수)를 하나의 노드로 묶어 연결리스트에 삽입하는 setNode함수 작성

( 단, 식을 입력할 때 띄어쓰기 불가능하고 내림차순으로 작성해야함 )

 

1-1. 케이스

: string의 문자 하나씩 반복문 돌려가며 노드 구성하여 삽입 

: string[i] (i=0~len-1)

---

<Base> 음수 판별

: bool 자료형을 통해 default값을 false로 해놓고 음수인 경우 true로 설정하여 노드를 삽입할 때 true인 경우에 음수로 변환하여 노드 삽입
→ 계수가 1인 특수 케이스 고려 : goto문 이용하여 바로 차수 구하는 코드로 이동 

 

<Processing> 숫자인 경우
→ 2자리 숫자이상인 케이스 고려
→ 차수가 0/1 이상인 케이스 두 가지로 나누어 고려 

→ 이때, 차수가 0인 경우(인덱스가 string의 길이인지로 판단)엔 양/음 판단하여 노드 삽입

→ 항의 차수가 1인 경우 양/음 판단하여 노드 삽입

→ 항의 차수가 2인 경우(= 다음 인덱스의 값이 '^'인 경우) 차수 구한 후 양/음 판단하여 노드 삽입

 

2. 연결리스트

2-1. 구성

: 첫번째 노드와 마지막 노드를 가리키는 Node 포인터 head, tail를 private member로 세팅

 

2-2. 연산자 오버로딩

: 연산하고자 하는 연결리스트로 구성한 다항식 2개를 연산자 오버로딩 이용

→ 이때, 연산결과를 새로운 연결리스트를 생성하여 마지막에 반환

• LinkedList* operator+( LinkedList* another);
• LinkedList* operator-(LinkedList* another);
• LinkedList* operator*(LinkedList* another);

(1) 공통 작업 ( 덧셈, 뺄셈 )

: 투 포인터 이용

: 다항식1 연결리스트의 head가리키는 포인터 a + 다항식2 연결리스트의 head가리키는 포인터

: a와 b 둘 다 특정 노드를 가리키고 있는 동안만 작업 (while문)

: while문을 빠져나오면 다항식1 연결리스트와 다항식2 연결리스트에 남은 노드들 새로운 연결리스트에 마저 모두 삽입

• a→degree == b→degree
  : 계수 연산하여 새로운 연결리스트에 노드 삽입
• a→degree < b→degree
  : b가 가리키는 노드를 새로운 연결리스트에 노드 삽입 후 b만 다음 노드로 이동
• a→degree > b→degree
  : a가 가리키는 노드를 새로운 연결리스트에 노드 삽입 후 a만 다음 노드로 이동

2-2-1. 특수 케이스 처리 ( 곱셈연산 )

: #include <unordered_map>

: unordered_map<int, Node*> map; 선언하여 key에는 degree, value에는 node의 주소값을 저장하도록 함

: unordered_map<int, Node*>:: iterator it; 선언

• 연결리스트 순회하며 각 다항식의 항의 차수와 계수 곱셈연산을 하여 새로운 연결리스트에 노드 삽입
• 이때, 새로운 연결리스트에는 차수가 뒤죽박죽으로 삽입되어있음
  : 또다른 새로운 연결리스트를 생성하여 노드들을 삽입하며 정렬하는 SortInsert함수 만듦
  → 순회하는 노드의 차수가 이미 해시맵에 존재하면 it->second함수를 이용하여 이미 해당 차수가 존재하는 노드를 가져와 계수끼리 연산하고 그 결과를 update
  → 순회하는 노드의 차수가 해시맵에 존재하지않으면 map.emplace 내장함수를 이용하여 해당 노드의 차수와 위치를 저장하고 SortInsert함수 통해 정렬하며 노드 삽입 

 

 LinkedList.h

#pragma once
#include <iostream>
#include <unordered_map>
using namespace std;
class Node {
private:
	int coef; //계수
	int degree; //차수
	Node* link;
public:
	Node(int coef,int degree, Node* next) : coef(coef), degree(degree), link(next) {}
	Node(int coef, int degree): coef(coef),degree(degree), link(NULL){}
	int getCoef() {
		return coef;
	}
	int getDegree() {
		return degree;
	}
	Node* getLink() {
		return link;
	}
	void setLink(Node* next) {
		link = next;
	}
	friend class LinkedList;
};

class LinkedList
{
private:
	Node* head;
	Node* tail;
	int count;

public:
	friend LinkedList* insertSort(LinkedList& list);
	LinkedList():head(NULL),tail(NULL){}

	void changeHead(Node* item) {
		head = item;
	}
	void changeTail(Node* item) {
		tail = item;
	}

	void SortInsert(Node *item) {
		if (isEmpty()) {
			head = item;
			tail = item;
		}
		else {
			//가장 큰 차수
			if ( item->degree >head->degree) {
				item->setLink(head);
				head = item;
				if (head->link ==NULL) {
					tail = head;
				}

			//일반적인 경우
			}
			else {
				Node* curNode = head->link;
				Node* preNode = head;
				while (curNode != NULL) {
					if (item->degree > curNode->degree) {
						break;
					}
					else {
						preNode = curNode;
						curNode = curNode->link;
					}
				}

				//가장 작은 값인 경우
				if (curNode == NULL) {
					preNode->setLink(item);
					tail = item;
				}
				else {
					item->setLink(curNode);
					preNode->setLink(item);
				}
			}
		}
		count++;
	}
	void insertNode(Node * item){
		if (isEmpty()) {
			head = item;
			tail = item;
			count++;
		}
		else {
			tail->link = item;
			tail = item;
			count++;
		}
	}
	int isEmpty() {
		return head == NULL;
	}
	Node* getHead() {
		return head;
	}
	Node* getTail() {
		return tail;
	}
	int getCount(){
		return count;
	}
	void traverse() {
		Node* curNode = head;
		cout << endl;
		while (curNode != NULL) {
			

			if (curNode->degree != 0 && curNode->degree != 1) {

				cout << curNode->coef << "x^" << curNode->degree;
			}
			else if (curNode->degree == 0) {
				cout << curNode->coef;
				break;
			}
			else if (curNode->degree == 1) {
				cout << curNode->coef << "x";
			}
			
			if (curNode->link != NULL) {
				if (curNode->getLink()->coef > 0) {
					cout << "+";
				}
				
			}
			curNode = curNode->link;
		}
		cout << endl;
	}
	
	LinkedList* operator+( LinkedList* another) {
		LinkedList* newList = new LinkedList;
		Node* a = head;
		Node* b = another->getHead();
		while (a && b) {
			if (a->degree == b->degree) {
				int sum = a->coef + b->coef;
				newList->insertNode(new Node(sum, a->degree));
				a = a->getLink();
				b = b->getLink();
			}
			else if (a->degree < b->degree) {
				newList->insertNode(new Node(b->coef, b->degree));
				b = b->getLink();
			}
			else {
				newList->insertNode(new Node(a->coef, a->degree));
				a = a->getLink();
			}
		}
		while (a != NULL) {
			newList->insertNode(new Node(a->coef, a->degree));
			a = a->getLink();
		}
		while (b != NULL) {
			newList->insertNode(new Node(b->coef, b->degree));
			b = b->getLink();
		}
		return newList;
	}
	LinkedList* operator-(LinkedList* another) {
		LinkedList* newList = new LinkedList;
		Node* a = head;
		Node* b = another->getHead();
		while (a && b) {
			if (a->degree == b->degree) {
				int minus = a->coef - b->coef;
				newList->insertNode(new Node(minus, a->degree));
				a = a->getLink();
				b = b->getLink();
			}
			else if (a->degree < b->degree) {
				newList->insertNode(new Node(~(b->coef)+1, b->degree));
				b = b->getLink();
			}
			else {
				newList->insertNode(new Node(a->coef, a->degree));
				a = a->getLink();
			}
		}
		while (a != NULL) {
			newList->insertNode(new Node(a->coef, a->degree));
			a = a->getLink();
		}
		while (b != NULL) {
			newList->insertNode(new Node(b->coef, b->degree));
			b = b->getLink();
		}
		return newList;
	}
	/*LinkedList* operator/(LinkedList* another) {

	}*/
	LinkedList* operator*(LinkedList* another) {
		Node* a= head;
		unordered_map<int, Node*> map; //key : degree, value : position of node
		unordered_map<int, Node*>::iterator it;

		LinkedList* newList = new LinkedList;
		while (a != NULL) {
			Node* b = another->getHead();
			while (b != NULL) {
				int coef = a->getCoef() * b->getCoef();
				int degree = a->getDegree()+b->getDegree();
				newList->insertNode(new Node(coef, degree));
				b = b->link;
			}
			a = a->link;
		}
		
		//같은 차수의 항 통합시키기
		Node* curNode = newList->getHead();
		LinkedList* res = new LinkedList;
		while (curNode != NULL) {
			
			
			it = map.find(curNode->degree);
			if (it == map.end()) { 
				Node* newNode = new Node(curNode->coef, curNode->degree);
				map.emplace(curNode->degree, newNode);
				res->SortInsert(newNode);
			}
			else {
				int newCoef=(it->second->coef)+curNode->coef;
				it->second->coef = newCoef;
			}
			curNode = curNode->link;
		}

		return res;
	}

};​

main.cpp

#include <iostream>
#include <string>
#include "LinkedList.h"
using namespace std;



void setNode(LinkedList& list, int len, const string& exp) {
	//식을 입력하면 계수 차수 구성하는 노드 생성하여 연결리스트에 삽입
	int j = 0;
	for (int i = 0; i < len; i++) {
		int coef = 0;
		int degree = 0;
		bool negative = false;
		if (exp[i] == '-') {
			negative = true;
			i++;
		}
		else if (exp[i] == '+') {
			i++;
		}
		if (exp[i] == 'x') {
			coef = 1;
			goto mygoto;
		}

		if (exp[i] >= '0' && exp[i] <= '9') {
			j = i;

			while (exp[j] >= '0' && exp[j] <= '9') {
				coef *= 10;
				coef += exp[j] - '0';
				j++;
			}
			if (j == len) {
				if (negative) {
					list.insertNode(new Node(-coef, 0));
				}
				else {
					list.insertNode(new Node(coef, 0));
				}
				return;
			}
			i = j;


			mygoto:
			if (exp[i] == 'x') {
				int k = i + 1;
                
				//차수가 2이상인 경우
				if (exp[k] == '^') {
					k++;
					while (exp[k] != '+' && exp[k] != '-') {
						while (exp[k] >= '0' && exp[k] <= '9') {
							degree *= 10;
							degree += exp[k] - '0';
							k++;
						}
					}
					if (negative) {
						list.insertNode(new Node(-coef, degree));
					}
					else {
						list.insertNode(new Node(coef, degree));
					}
					i = k - 1;
				}
				//차수가 1인 경우
				else {
					degree = 1;
					if (negative) {
						list.insertNode(new Node(-coef, 1));
					}
					else {
						list.insertNode(new Node(coef, 1));
					}
					i = k - 1;
				}
			}
		}
	}
}



int main() {


	int ans;
	string exp1;
	string exp2;



	while (1) {
		LinkedList list1;
		LinkedList list2;
		cout << "\n\n*************다항식 연산**************" << endl;
		cout << "1. 덧셈\n2. 뺄셈\n3. 곱셈\n4. exit\n";
		cout << ">> ";
		cin >> ans;
		if (ans == 4) {
			cout << "quit" << endl;
			break;
		}
		cin.ignore();
		cout << "\n";
		cout << "연산을 수행할 두 개의 식을 공백없이 입력하시오\n";

		//5x^3-8x
		//-2x^3-x^2-2x

		//6x^2-2x-1
		//-4x^2+7x+5

		//3x^2+2x+3
		//17x^13+4x^2+6

		cout << "\n첫번째 식 : ";
		getline(cin, exp1);
		setNode(list1, exp1.length(), exp1);
	

		cout << "두번째 식 : ";
		getline(cin, exp2);
		setNode(list2, exp2.length(), exp2);

		

		cout << "\n[연산 결과]\n";
		LinkedList* newList;
		switch (ans) {
		case 1:
			newList = list1 + &list2;
			newList->traverse();
			break;
		case 2:
			newList = list1 - &list2;
			newList->traverse();
			break;
		case 3:
			newList = list1 * &list2;
			newList->traverse();
			break;
		default:
			cout << "다시 입력하시오" << endl;
			break;
		}
		cout << endl;

		newList = NULL;
	}






	return 0;
}​