[자료구조] 자료구조 수업 과제 2

자료구조 수업때 과제를 하며 공부한 기록을 남긴다.

[과제 2]

1.1원 다항식을 정의할 수 있다. 다항식의 이름은 x를 제외한 영문 소문자이다(예: f, g등)

2.변수는 항상 x이다.

3.각 항의 지수는 음이 아닌 정수이고, 계수는 정수이다.

4.=,+,-등의 앞뒤로 하나 이상의 공백이 있을 수도 있고 없을 수도 있다.

5. 항들이 반드시 차수에 대한 내림차순으로 입력되는 것은 아니며, 동일 차수의 항이 여럿 있을 수도 있다.

6. 함수는 항상 차수에 대한 내림차순으로 정렬되어 저장되고 출력되어야 한다.

7. 동일 이름의 함수를 새로 정의할 수도 있다. 이 경우 기존의 함수는 지워진다.

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

-다항식의 표현

• 연결리스트를 이용하여 하나의 다항식을 표현하는 구조체 Polynominal을 정의한다.
• 다항식을 항들의 연결리스트로 표현한다.
• 항들을 차수에 대해서 내림차순으로 정렬하여 저장하며, 동일 차수의 항을 2개 이상 가지지 않게 한다. 또한 계수가 0인 항이 존재하지 않게 한다.
• 하나의 항은 계수와 지수에 의해 정의된다. 하나의 항을 표현하기 위해 구조체 Term을 정의 한다.
• 변수 x의 값이 주어질 때 다항식의 값을 계산하는 함수를 제공한다.

*출력결과

$ f= 2x^5 +  3x  -4x^2- 8 // f(x)=2x^5 + 3x -4x^2 - 8

$ calc f 1 // f(1)

-7

$ g= f + g

g = 2x^5+x^3-2x^2+3x-7

$ f = x^2-x + 1

$ print f

f = x^2-x+1

$ exit

 

언어는 자신이 원하는 언어로 작성해도 좋습니다.

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

나는 c++ 언어를 이용해서 과제를 해결해보았다. 조금 많이 고통스러웠지만 공부는 확실히 된 기분이다.

#include <iostream>
#include <string>
#include <vector>
#include <Cmath>

/*
* 입력 형식 : 함수이름(알파벳 한글자) = 다항식(차수 순서 무작위, 변수 x 고정, +나 -사이에 공백 있을수도 있음)
*/

using namespace std;

string PolynominalAdd(string polynames, char op);

class Term {
public:
	Term(int coef, int expo, Term* next = nullptr) { this->coef = coef, this->expo = expo, this->next = next; };

	int getcoef() { return this->coef; }
	int getexpo() { return this->expo; }
	Term* getnext() { return this->next; }

	void setcoef(int coef) { this->coef = coef; }
	void setexpo(int expo) { this->expo = expo; }
	void setnext(Term* next) { this->next = next; }

private:
	int coef;
	unsigned int expo;
	Term* next;
};

class Polynominal {
public:
	Polynominal() { this->first = nullptr, this->name = "", this->size = 0; } //기본 생성자 함수
	Polynominal(std::string poly) { //생성자 함수
		poly = SpaceEliminate(poly);
		this->name = PolyNameExtraction(poly);
		if (poly.find("x") != std::string::npos || poly.find_first_not_of("0123456789")) { //일반 함수일 경우
			PolyTermExtraction(poly);
			this->size = PolySizeExtraction(poly);
		}
		else { //함수와 함수의 연산일 경우
			string polynames = "";
			string operaters = "";

			for (auto e : poly) {
				if ((e >= 'a' && e <= 'z') && e != 'x') {
					polynames += e;
				}
				else if (e == '+' || e == '-') {
					operaters += e;
				}
				else if (e == '*' || e == '/') {
					cout << "지원되지 않는 연산자입니다." << endl;
				}
			}

			if (polynames.length() >= 2 && operaters.length() >= 1) {
				PolyTermExtraction(PolynominalAdd(poly,operaters[0]));
			}
			this->size = PolySizeExtraction(poly);

		}
	}

	//==========set()===========
	void setname(string name) {
		this->name = name;
	}

	void setfirst(Term* term) {
		this->first = term;
	}

	void setsize(int size) {
		this->size = size;
	}
	//==========get()===========
	string getname() {
		return this->name;
	}

	Term* getfirst() {
		return this->first;
	}

	int getsize() {
		return this->size;
	}

	void printtest() { //다항식 출력 함수
		if (this->first != nullptr) {
			Term* tmpPtr = this->first;
			cout << this->name << "(x) = ";
			cout << tmpPtr->getcoef() << "x^" << tmpPtr->getexpo();
			tmpPtr = tmpPtr->getnext();
			while (tmpPtr != nullptr) {
				if (tmpPtr->getcoef() > 0) {
					cout << "+" << tmpPtr->getcoef() << "x^" << tmpPtr->getexpo();
				}
				else {
					cout << tmpPtr->getcoef() << "x^" << tmpPtr->getexpo();
				}
				tmpPtr = tmpPtr->getnext();
			}
		}
	}

	/*
	* 다항식 출력 함수
	*/
	void print() {
		if (this->first != nullptr) {
			Term* tmpPtr = this->first;
			cout << this->name << "(x) = ";
			while (tmpPtr != nullptr) {
				if (tmpPtr->getexpo() == 0) { //상수 출력
					if (tmpPtr->getcoef() > 0) {
						if (this->first != tmpPtr) {
							cout << "+" << tmpPtr->getcoef();
						}
						else {
							cout << tmpPtr->getcoef();
						}
					}
					else {
						cout << tmpPtr->getcoef();
					}
				}
				else if (tmpPtr->getexpo() == 1) { //일차항 출력
					if (tmpPtr->getcoef() == 1) {
						if (this->first != tmpPtr) {
							cout << "+x";
						}
						else {
							cout << "x";
						}
					}
					else if (tmpPtr->getcoef() == -1) {
						if (this->first != tmpPtr) {
							cout << "-x";
						}
						else {
							cout << "x";
						}
					}
					else {
						if (this->first != tmpPtr) {
							cout << "+" << tmpPtr->getcoef() << "x";
						}
						else {
							cout << tmpPtr->getcoef() << "x";
						}
					}
				}
				else { //고차항 출력
					if (tmpPtr->getcoef() == 1) {
						if (this->first != tmpPtr) {
							cout << "+x^" << tmpPtr->getexpo();
						}
						else {
							cout << "x^" << tmpPtr->getexpo();
						}
					}
					else if (tmpPtr->getcoef() == -1) {
						if (this->first != tmpPtr) {
							cout << "-x^" << tmpPtr->getexpo();
						}
						else {
							cout << "x^" << tmpPtr->getexpo();
						}
					}
					else {
						if (this->first != tmpPtr) {
							if (tmpPtr->getcoef() > 0) {
								cout << "+" << tmpPtr->getcoef() << "x^" << tmpPtr->getexpo();
							}
							else {
								cout << tmpPtr->getcoef() << "x^" << tmpPtr->getexpo();
							}
						}
						else {
							cout << tmpPtr->getcoef() << "x^" << tmpPtr->getexpo();
						}
					}
					
				}
				tmpPtr = tmpPtr->getnext();
			}
		}
		cout << endl;
	}
	
	/*
	* 다항식에 값 대입
	*/
	double calc(double x) {
		Term* tmpPtr = this->getfirst();
		double result = 0;

		while (tmpPtr != nullptr) {
			result += tmpPtr->getcoef() * pow(x, (double)tmpPtr->getexpo());
			tmpPtr = tmpPtr->getnext();
		}
		return result;
	}

private:
	string name;
	Term* first = nullptr;
	int size;

	string SpaceEliminate(string poly) { //다항식 공백 제거
		string polynominal;
		for (auto e : poly) {
			if (e != ' ') {
				polynominal += e;
			}
		}
		return polynominal;
	}

	string PolyNameExtraction(string poly) { //다항식 이름 추출 함수
		if (poly.length() != 0) {
			string polyname = "";
			polyname += poly[0];
			return polyname;
		}
		else {
			return "no Polynominal";
		}
	}

	int PolySizeExtraction(string poly) { //다항식 크기 확인 함수
		Term* tmpPtr = this->first;
		int size = 0;
		while (tmpPtr != nullptr) {
			size++;
			tmpPtr = tmpPtr->getnext();
		}
		return size;
	}

	void PolyTermExtraction(string poly) { //다항식 항 추출 함수
		vector<string> terms;
		string term = "";
		poly.erase(0, this->name.size() + 1);

		for (auto e : poly) {
			if (e == '+' || e == '-') {
				if (term.length() != 0) terms.push_back(term);
				term = "";
				term += e;
			}
			else {
				term += e;
			}
		}

		if (term.length() != 0) terms.push_back(term);

		//terms 차수에 따라 정렬
		vector<double> degrees;
		string degree = "";

		for (auto e : terms) {
			if (e.find("^") != std::string::npos) {
				while (e.back() != '^') {
					degree += e.back();
					e.pop_back();
				}
				reverse(degree.begin(), degree.end());
				degrees.push_back(stoi(degree));
				degree = "";
			}
			else if (e.find("x") != std::string::npos) {
				degrees.push_back(1);
			}
			else {
				degrees.push_back(0);
			}
		}

		string strtmp = "";
		double inttmp = 0;
		for (int i = 0; i < degrees.size(); i++) { //버블 정렬
			for (int j = 0; j < degrees.size() - 1 - i; j++) {
				if (degrees[j] < degrees[j + 1]) {
					strtmp = terms[j];
					terms[j] = terms[j + 1];
					terms[j + 1] = strtmp;

					inttmp = degrees[j];
					degrees[j] = degrees[j + 1];
					degrees[j + 1] = inttmp;
				}
			}
		}

		for (auto e : terms) { //terms에 저장된 다항식문자열에 따라 항 객체 생성
			string temp = "";
			int coef = 0;
			int expo = 0;
			if (e.length() != 0) {
				if (e.find("x") != std::string::npos && e.find("^") != std::string::npos) { //x의 제곱 이상인 항
					if (e[0] == 'x') {
						coef = 1;
					}
					else {
						for (int i = 0; i <= e.length() - 1; i++) {
							if (e[i] != 'x') {
								temp += e[i];
							}
							else {
								if (temp == "-") {
									temp += "1";
								}
								else if (temp == "+") {
									temp += "1";
								}
								coef = stoi(temp);
								temp = "";
								break;
							}
						}
					}
					for (int i = e.length() - 1; i >= 0; i--) {
						if (e[i] != '^') {
							temp += e[i];
						}
						else {
							reverse(temp.begin(), temp.end());
							expo = stoi(temp);
							temp = "";
							break;
						}
					}
					
					

					if (this->first == nullptr) {
						this->first = new Term(coef, expo);
					}
					else {
						Term* tmpPtr = this->first;
						while (tmpPtr->getnext() != nullptr) {
							tmpPtr = tmpPtr->getnext();
						}
						tmpPtr->setnext(new Term(coef, expo));
					}
				}
				else if (e.find("x") != std::string::npos && e.find("^") == std::string::npos) { //x의 1제곱인 항
					if (e[0] == 'x') {
						coef = 1;
					}
					else {
						for (int i = 0; i <= e.length() - 1; i++) {
							if (e[i] != 'x') {
								temp += e[i];
							}
							else {
								if (temp == "-") {
									temp += "1";
								}
								else if (temp == "+") {
									temp += "1";
								}
								coef = stoi(temp);
								temp = "";
								break;
							}
						}
					}
					if (this->first == nullptr) {
						this->first = new Term(coef, expo = 1);
					}
					else {
						Term* tmpPtr = this->first;
						while (tmpPtr->getnext() != nullptr) {
							tmpPtr = tmpPtr->getnext();
						}
						tmpPtr->setnext(new Term(coef, expo = 1));
					}

				}
				else { //상수
					coef = 0;
					coef = stoi(e);
					if (this->first == nullptr) {
						this->first = new Term(coef, expo = 0);
					}
					else {
						Term* tmpPtr = this->first;
						while (tmpPtr->getnext() != nullptr) {
							tmpPtr = tmpPtr->getnext();
						}
						tmpPtr->setnext(new Term(coef, expo = 0));
					}
				}
			}
		}

		Term* tmpPtr = this->first; //동일 차수 합치기
		while (tmpPtr->getnext() != nullptr) {
			if (tmpPtr->getexpo() == tmpPtr->getnext()->getexpo()) {
				tmpPtr->setcoef(tmpPtr->getcoef() + tmpPtr->getnext()->getcoef());
				tmpPtr->setnext(tmpPtr->getnext()->getnext());
			}
			else {
				tmpPtr = tmpPtr->getnext();
			}
		}
	}
};

vector<Polynominal> polyList;

int main() {
	Polynominal f;

	f = Polynominal("f= 2x^5 +  3x  -4x^2- 8 ");
	polyList.push_back(f);
	f.print();
	cout << f.calc(1) << endl;

	f = Polynominal("g=x^3 + 2 -x^2");
	polyList.push_back(f);
	f.print();

	f = Polynominal("f=f+g");
	//cout << PolynominalAdd("fg", '-') << endl;
	f.print();
	
	f = Polynominal("f = x^2-x + 1");
	f.print();

	return 0;
}

string PolynominalAdd(string polynames, char op) { //두 다항식의 합
	
	if (polyList.size() >= 2) {
		Polynominal f = Polynominal();
		Polynominal g = Polynominal();

		for (auto e : polynames) {
			for (Polynominal p : polyList) {
				if (p.getname()[0] == e) {
					if (f.getfirst() == nullptr) {
						f = p;
					}
					else {
						g = p;
					}
				}
			}
		}

		if (f.getfirst() == nullptr || g.getfirst() == nullptr) {
			return "not found function name";
		}
		else {
			//함수 연결
			string fs = "";
			string gs = "";

			if (f.getfirst() != nullptr) {
				Term* tmpPtr = f.getfirst();
				fs += f.getname() + "=";
				fs += to_string(tmpPtr->getcoef()) + "x^" + to_string(tmpPtr->getexpo());
				tmpPtr = tmpPtr->getnext();
				while (tmpPtr != nullptr) {
					if (tmpPtr->getcoef() > 0) {
						fs += "+" + to_string(tmpPtr->getcoef()) + "x^" + to_string(tmpPtr->getexpo());
					}
					else {
						fs += to_string(tmpPtr->getcoef()) + "x^" + to_string(tmpPtr->getexpo());
					}
					tmpPtr = tmpPtr->getnext();
				}
			}
			else {
				return "function is null";
			}

			if (op == '-') {
				if (g.getfirst() != nullptr) {
					Term* tmpPtr = g.getfirst();
					
					while (tmpPtr != nullptr) {
						if (tmpPtr->getcoef() < 0) {
							gs += "+" + to_string(tmpPtr->getcoef() * -1) + "x^" + to_string(tmpPtr->getexpo());
						}
						else {
							gs += to_string(tmpPtr->getcoef() * -1) + "x^" + to_string(tmpPtr->getexpo());
						}
						tmpPtr = tmpPtr->getnext();
					}
				}
			}
			else if (op == '+') {
				if (g.getfirst() != nullptr) {
					Term* tmpPtr = g.getfirst();

					while (tmpPtr != nullptr) {
						if (tmpPtr->getcoef() > 0) {
							gs += "+" + to_string(tmpPtr->getcoef()) + "x^" + to_string(tmpPtr->getexpo());
						}
						else {
							gs += to_string(tmpPtr->getcoef()) + "x^" + to_string(tmpPtr->getexpo());
						}
						tmpPtr = tmpPtr->getnext();
					}
				}
			}
			else {
				return "function is null";
			}

			if (fs.empty() || gs.empty()) {
				return "fuction is empty";
			}
			else {
				return fs + gs;
			}
		}
	}
	else {
		return "polyList is not enough";
	}
}

[출력결과]