[아무문제] 다항식 더하기 프로그램

말 그대로 x에 관한 다항식 더하기 결과를 출력하는 프로그램입니다. 

입력:  9x^2+6x^1-3x^0

        10x^2+3x^0

출력: 19x^2 + 6x^1 + 0x^0

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>


typedef struct _Node {
	int coef;
	int expon;
	int item;
	struct _Node* next;
}Node;

typedef struct {
	Node* tail;
	int len;
}Polynominal;

typedef struct {
	Node* top;
}Stack;

void InitItem(Polynominal* plist) {
	plist->tail = NULL;
	plist->len = 0;
}

void InsertLast(Polynominal* plist, int front, int back) {
	
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->coef = front;
	newNode->expon = back;
	if (plist->tail == NULL) {
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else {
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
		plist->tail = newNode;
	}
	plist->len++;
	
}

void InitStack(Stack* pstack) {
	pstack->top = NULL;
}

bool IsEmpty(Stack* pstack) {
	return pstack->top == NULL;
}

int Peek(Stack* pstack) {
	if (IsEmpty(pstack))
		exit(1);
	return pstack->top->item;
}

void Push(Stack* pstack, int item) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->item = item;
	newNode->next = pstack->top;
	pstack->top = newNode;
}

int Pop(Stack* pstack) {
	Node* temp;
	int data;
	if (IsEmpty(pstack))
		exit(1);

	data = pstack->top->item;
	temp = pstack->top;
	pstack->top = pstack->top->next;
	free(temp);

	return data;
}

int pow(int num) {
	int result = 1;

	for (int i = 0; i < num; i++) {
		result = result * 10;
	}

	return result;

}

int comp(int num1, int num2) {
	if (num1 == num2)
		return 1;
	else if (num1 > num2)
		return 2;
	else if (num1 < num2)
		return 3;
}

int main() {
	char Exp1[100];
	char Exp2[100];
	
	scanf("%s",Exp1);
	scanf("%s",Exp2);
	
	int len1 = strlen(Exp1);
	int len2 = strlen(Exp2);

	Polynominal poly1;
	Polynominal poly2;

	InitItem(&poly1);
	InitItem(&poly2);

	Stack stack;
	InitStack(&stack);

	int i = 0;
	int numdigit = 0;
	int tempsave1 = 0, tempsave2 = 0;
	int coefsaved = 0, itsnegative = 0;
	int expnum = 0;
	//문자열 순환 연결 리스트에 저장  
	while (1) {

		if (i == len1)
			break;

		if (isdigit(Exp1[i])) {
			if (Exp1[i - 1] == '-') {
				itsnegative++;
			}
			Push(&stack, Exp1[i]-48);
			numdigit++;
			if (i + 1 == len1) {
				if (itsnegative != 0) {
					int ten;
					for (int j = 0; j < numdigit; j++) {
						ten = pow(j);
						tempsave2 = -(Pop(&stack) * ten + tempsave2);
					}
				}
				else {
					int ten;
					for (int j = 0; j < numdigit; j++) {
						ten = pow(j);
						tempsave2 = Pop(&stack) * ten + tempsave2;
					}
				}

				numdigit = 0;

				InsertLast(&poly1, tempsave1, tempsave2);
				expnum++;
				tempsave1 = 0; tempsave2 = 0; itsnegative = 0;
			}
		}
		else if (Exp1[i] == 'x') {
			if (itsnegative != 0) {
				int ten;
				for (int j = 0; j < numdigit; j++) {
					ten = pow(j);
					tempsave1 = -(Pop(&stack) * ten + tempsave1);
				}
			}
			else {
				int ten;
				for (int j = 0; j < numdigit; j++) {
					ten = pow(j);
					tempsave1 = Pop(&stack) * ten + tempsave1;
				}
			}

			numdigit = 0;
			itsnegative = 0;

		}
		else if (Exp1[i] == '+' || Exp1[i] == '-' || (i+1) == len1) {
			if (itsnegative != 0) {
				int ten;
				for (int j = 0; j < numdigit; j++) {
					ten = pow(j);
					tempsave2 = -(Pop(&stack) * ten + tempsave2);
				}
			}
			else {
				int ten;
				for (int j = 0; j < numdigit; j++) {
					ten = pow(j);
					tempsave2 = Pop(&stack) * ten + tempsave2;
				}
			}

			numdigit = 0;

			InsertLast(&poly1, tempsave1, tempsave2);
			expnum++;
			tempsave1 = 0; tempsave2 = 0; itsnegative = 0;
		}
		i++;
	}

	//////////////////////////////////////두번째 식 저장 시작////////////////////////////////////////
	i = 0;
	while (1) {

		if (i == len2)
			break;

		if (isdigit(Exp2[i])) {
			if (Exp2[i - 1] == '-') {
				itsnegative++;
			}
			Push(&stack, Exp2[i] - 48);
			numdigit++;
			if (i + 1 == len2) {
				if (itsnegative != 0) {
					int ten;
					for (int j = 0; j < numdigit; j++) {
						ten = pow(j);
						tempsave2 = -(Pop(&stack) * ten + tempsave2);
					}
				}
				else {
					int ten;
					for (int j = 0; j < numdigit; j++) {
						ten = pow(j);
						tempsave2 = Pop(&stack) * ten + tempsave2;
					}
				}

				numdigit = 0;

				InsertLast(&poly2, tempsave1, tempsave2);
				expnum++;
				tempsave1 = 0; tempsave2 = 0; itsnegative = 0;
			}
		}
		else if (Exp2[i] == 'x') {
			if (itsnegative != 0) {
				int ten;
				for (int j = 0; j < numdigit; j++) {
					ten = pow(j);
					tempsave1 = -(Pop(&stack) * ten + tempsave1);
				}
			}
			else {
				int ten;
				for (int j = 0; j < numdigit; j++) {
					ten = pow(j);
					tempsave1 = Pop(&stack) * ten + tempsave1;
				}
			}

			numdigit = 0;
			itsnegative = 0;

		}
		else if (Exp2[i] == '+' || Exp2[i] == '-' || (i + 1) == len2) {
			if (itsnegative != 0) {
				int ten;
				for (int j = 0; j < numdigit; j++) {
					ten = pow(j);
					tempsave2 = -(Pop(&stack) * ten + tempsave2);
				}
			}
			else {
				int ten;
				for (int j = 0; j < numdigit; j++) {
					ten = pow(j);
					tempsave2 = Pop(&stack) * ten + tempsave2;
				}
			}

			numdigit = 0;

			InsertLast(&poly2, tempsave1, tempsave2);
			expnum++;
			tempsave1 = 0; tempsave2 = 0; itsnegative = 0;
		}
		i++;
	}
	//각 연결 리스트 exponent비교해서 계산 
	Polynominal poly3;
	InitItem(&poly3);

	int compresult;
	int compexpnum=0;

	Node* fix1 = poly1.tail;
	Node* fix2 = poly2.tail;

	poly1.tail = poly1.tail->next;
	poly2.tail = poly2.tail->next;
	while (1) {

		compresult = comp(poly1.tail->expon, poly2.tail->expon);

		if (compresult == 1) {	//두 지수가 같으면 1 
			InsertLast(&poly3, poly1.tail->coef + poly2.tail->coef, poly1.tail->expon);
			compexpnum += 2;

			if (compexpnum == expnum)
				break;
			if (poly1.tail != fix1) {
				poly1.tail = poly1.tail->next;
			}
			if (poly2.tail != fix2) {
				poly2.tail = poly2.tail->next;
			}
		}
		else if (compresult == 2) {		//poly1의 지수가 크면 
			InsertLast(&poly3, poly1.tail->coef, poly1.tail->expon);//tempcoef1, tempexp1);
			compexpnum++;
			
			if (compexpnum == expnum)
				break;
			if (poly1.tail != fix1) {
				poly1.tail = poly1.tail->next;
			}
		}
		else if (compresult == 3) {		//poly2의 지수가 크면 
			InsertLast(&poly3, poly2.tail->coef, poly2.tail->expon); //tempcoef2, tempexp2);
			compexpnum++;

			if (compexpnum == expnum)
				break;
			if (poly2.tail != fix2) {
				poly2.tail = poly2.tail->next;
			}
		}

	}

	//마지막으로 출력 ㅎ;;;;;
	Node* fix3 = poly3.tail;
	poly3.tail = poly3.tail->next;
	printf("%dx^%d", poly3.tail->coef, poly3.tail->expon);

	while (1) {
		poly3.tail = poly3.tail->next;
		if (poly3.tail->coef < 0) {
			printf("%dx^%d", poly3.tail->coef, poly3.tail->expon);
			if (poly3.tail == fix3)
				break;
		}
		else {
			printf("+%dx^%d", poly3.tail->coef, poly3.tail->expon);
			if (poly3.tail == fix3)
				break;
		}
	}

	return 0;
	
}

스택과 연결리스트를 활용한 연습문제입니다. 

 

사실 알고리즘 자체는 그다지 어려운 편은 아니지만 워낙 코드가 길다보니 군데군데 실수가 꽤 많았네요.