연결리스트_다항식_구현목표 및 전체코드 [1/3]

[ 구현 목표 ]

1. 다항식 차수별로 내림차순으로 저장
2. 'printf 변수' 출력 시 해당 형식에 맞게 출력 (존재하지 않는 변수의 경우 경고메세지 출력)
3. '='이 두 개 이상 포함 시 경고 메세지 출력
4. 기존 존재하는 변수에 식을 넣으면 덮어쓰기
5. 기존 변수를 활용한 더하기 기능
6. 명령어 입력 시 띄워쓰기 무시
7. 'calc (변수) (x값) 입력 시 계산결과 출력 및 해당하는 변수가 없을 경우 경고 메세지 출력
8. 'exit' 입력 시 프로그램 종료

 

---

 

[ 전체 코드 ]

* 다음 글 코드 상세 참조

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define INPUT 50
#define LIST 10

/* 다항식 각 요소 저장 연결리스트 */
typedef struct Inside {
	int coef;  // 지수
	int expo;  // 계수
	struct Inside* next;
}Inside;

/* 변수 이름 및 다항식 head 위치 */
typedef struct {
	char* name;  // 변수 이름
	Inside* head;  // 다항식(연결리스트)의 head
}Data;

int read_line(FILE* fp, char* str, int len);
char* remove_space(char* str);
void my_printf(char* str);
int plus(char* str);
int plus_validity(char* str, int* c);
char* my_strtok(char* str);
int exch_data(char* str);
int save_data(char* str, char* equal_p);
int extract_and_add(int c, Inside* head, char* str, int start, int end);
int add_inside(int c, Inside* head, int coef, int expo);
void inside_free(int c);
void calc(char* str);
int validity(char* arg);
int my_realloc(Data** p);

Data** data_set;  // Data의 포인터 저장 배열
int n = 0;  // Data_set에 실제 저장된 갯수

int main()
{
	data_set = (Data**)malloc(sizeof(Data*) * LIST);
	char input[INPUT];

	printf("\n");
	while (1)
	{
		printf(">> ");
		if (read_line(stdin, input, INPUT) == 0) continue;

		else if (strncmp(input, "printf", 6) == 0)
			my_printf(input);

		else if (strncmp(input, "calc", 4) == 0)
			calc(input);

		else if (strncmp(input, "exit", 4) == 0)
			break;
	}
	puts("종료되었습니다.");
	return 0;
}

/*한줄 읽기*/
/* parameter : 읽어올 장소, 저장할 장소, 입력 길이 */
/* return : 입력된 글자 수*/
int read_line(FILE* fp, char* str, int len)
{
	char c;
	int i = 0, equal_count = 0;
	char* equal_p = NULL;
	while ((c = getc(fp)) != '\n' && c != EOF)
	{
		if (i == len - 1) continue;
		// 최대 길이에 도달하면 아무것도 하지 않는다. (마지막은 '\0'자리이므로 그 전까지 허용)
		// break를 시켜버리면 stdin 버퍼에 값이 남아 문제를 야기할 수 있으므로 끝까지 돌린다.

		// 첫글자는 무조건 공백이 아니어야 하며, 이후부터는 연속된 공백은 제거
		if ((i == 0 && isspace(abs(c))) ||
			(i > 0 && i < isspace(abs(c)) && isspace(abs(str[i - 1]))))
			continue;
		if ((str[i++] = c) == '=')
			equal_count++;
	}
	if (isspace(abs(str[i]))) i--;  // 마지막칸이 공백이라면 i를 한칸 줄여준다.
	str[i] = '\0';

	/* 한줄 안에 '='이 하나 있으면 변수 저장을 동시에 수행 */
	if (equal_count > 1)
	{
		puts("변수 입력을 위해 '='기호를 한번만 입력해 주세요.");
		return 0;
	}
	else if (equal_count == 1)
	{
		equal_p = remove_space(str);  // 문자열의 공백을 모두 없애고 '='위치 입력

		/* 문자열(전체 식)의 유효성 검증 및 식의 형태가 아니라면 식의 합 형식 확인 */
		if (validity(equal_p + 1) == 0)
		{
			if (plus(str) == 1)
				return i;
			else
			{
				puts("유효한 형태의 식이 아닙니다. 또는 계산할 변수가 존재하지 않습니다.");
				return 0;
			}
		}
		else if (save_data(str, equal_p) == 0)
		{
			puts("저장에 실패했습니다.");
			return 0;
		}
	}
	return i;
}

/* 공백 제거해주기 */
/* parameter : 공백 제거할 문자열 */
/* return : '=' 기호의 위치 */
char* remove_space(char* str)
{
	char temp[INPUT];
	strcpy(temp, str);
	int i = 0, j = 0;
	char* e = NULL;
	while (temp[i] != '\0')
	{
		if (!isspace(abs(temp[i])))
			if ((str[j++] = temp[i]) == '=')
				e = &str[j - 1];
		i++;
	}
	str[j] = '\0';
	return e;
}

/* 검색된 변수의 값 출력하기 */
/* parameter : 명령어(input) */
void my_printf(char* str)
{
	int i, j = 0;
	for (i = 0; i < n; ++i)
	{
		if (strcmp(data_set[i]->name, &str[7]) == 0)
		{
			j++;
			break;
		}
	}
	if (j == 0)
	{
		puts("해당하는 값이 없습니다.");
		return;
	}
	Inside* p = data_set[i]->head;
	int a = 0;	// 가장 첫 출력을 구분하기 위한 카운트
	printf("   %s = ", data_set[i]->name);
	while (p != NULL)
	{
		if (a != 0 && p->coef > 0)  // 첫번째가 아닐 때 양수면 '+'붙여준다.
			printf("+");
		if (p->coef != 1 && p->coef != -1)  // 1이나 -1이 아니라면 coef를 출력한다.
			printf("%d", p->coef);
		if (p->coef == -1)  // coef가 -1이라면 -만 출력한다.
			printf("-");
		if (p->next == NULL && (p->coef == 1 || p->coef == -1) && p->expo == 0)
			printf("%d", abs(p->coef));
		// 마지막에 -1, 1 숫자만 나온다면 절대값을 출력해준다.
		if (p->expo == 1)  // expo가 1이라면 x만 출력하고 끝내고
			printf("x");
		else if (p->expo > 1)  // else, expo가 1보다 크면 x^expo를 출력한다.
			printf("x^%d", p->expo);

		printf(" ");  // 다 하면 한칸 띄워준다.
		p = p->next;
		a++;
	}
	printf("\n");  // 식이 끝나면 한줄 띄워준다.
}

/* 변수끼리 합치기 */
/* parameter : 전체 입력값 (f = a + b + c)  */
/* return : 정상 1, 비정상 0 */
int plus(char* str)
{
	int c;  // 저장시킬 변수의 위치 (신규 / 기존)
	char* arg;  // 변수이름 저장
	char* l_value;  // l-value 값 저장

	/* 유효성 검증(모든 변수가 있는 값이 맞는지 확인 및 기존 변수 위치 반환) */
	if (plus_validity(str, &c) == 0)  // 변수가 존재하지 않을 경우
		return 0;

	l_value = my_strtok(str);  // 첫 번째 l_value 변수를 잘라서 보관

	/* 신규 임시 공간 생성 */
	if (n != 0 && (n % 10) == 0)
		if (my_realloc(data_set) == 0)
		{
			puts("%d개 이상의 변수 저장 공간이 없습니다.");
			return 0;
		}
	if ((data_set[n] = (Data*)malloc(sizeof(Data))) == NULL)
	{
		puts("변수 저장 실패, 메모리할당에 실패했습니다.");
		return 0;
	}
	data_set[n]->name = "Temp";
	data_set[n]->head = NULL;

	/* r_value 값 붙여넣기 */
	while ((arg = my_strtok(NULL)) != NULL)
	{
		int i = 0;
		while (i < n)
		{
			if ((strcmp(data_set[i]->name, arg)) == 0)
				break;
			i++;
		}

		Inside* p = data_set[i]->head;
		while (p != NULL)  // 해당 변수의 연결리스트를 신규 생성된 Temp 변수에 하나씩 추가
		{
			add_inside(n, data_set[n]->head, p->coef, p->expo);
			p = p->next;
		}
	}

	/* n번째에 임시로 저장된 최종 Data를 실제 위치에 놓고 변수 이름 지정 */
	if (c == n)  // n 번째에 들어가는게 맞다면 해당변수 이름을 l_value로 바꿔주고 n++;
		data_set[n++]->name = _strdup(l_value);
	else  // 기존 변수 값에 넣어줘야 한다면
	{
		inside_free(c);  // 기존 변수의 연결리스트를 모두 Free 시켜주고
		data_set[c]->head = data_set[n]->head;  // 신규 생성된 연결리스트의 head 부여
		free(data_set[n]); // 임시 생성된 Temp 변수 Free
	}

	return 1;
}

/* (변수 + 변수) 형태의 유효성 검증*/
/* parameter : 전체 입력값 */
/* return : 기존 변수 저장이면 2, 새로 만들어 저장이면 1, 변수가 없으면 0 */
int plus_validity(char* str, int* c)
{
	*c = n; // 기본값 부여
	char temp[INPUT];
	strcpy(temp, str);  // 원본 훼손을 막기 위해 임시 복사

	/* l-value 검사 및 존재하는 변수의 위치값 입력 */
	char* arg = my_strtok(temp);
	for (int i = 0; i < n; ++i)
	{
		if (strcmp(data_set[i]->name, arg) == 0)
		{
			*c = i;  // i번째 변수에 합쳐야 하는 상황 (없으면 c == n번째(기본값))
			break;
		}
	}

	/* 나머지 변수들이 실제로 존재하는지 확인, 존재하지 않는 변수가 있으면 0을 리턴 */
	while ((arg = my_strtok(NULL)) != NULL)
	{
		int j = 0;
		for (int i = 0; i < n; ++i)
		{
			if (strcmp(data_set[i]->name, arg) == 0)
			{
				j++;
				break;
			}
		}
		if (j == 0)
			return 0;
	}
	return 1;
}

/* 문자열을 =, +, -으로 순차적으로 나눠서 반환 (strtok 변형) */
/* parameter : 문자열 */
/* return : 구분자 이전 단어의 시작 지점 */
char* my_strtok(char* str)
{
	int i = 0;
	static char* start = NULL;
	static char* end = NULL;
	static int status = 0;
	if (str != NULL)
	{
		start = str;
		status = 0;
	}
	/* NULL값이 들어왔을 때 status가 0이라면 계속 진행*/
	else if (str == NULL && status == 0)
		start = end;
	/* 그 외 경우라면, 마지막에 도달한 이후의 경우밖에 없으므로 NULL값 반환*/
	else return NULL;

	while (1)
	{
		if (start[i] == '+' || start[i] == '-' || start[i] == '=')
		{
			start[i] = '\0';
			end = &start[i + 1];
			return start;
		}
		else if (start[i] == '\0')
		{
			status = 1;
			return start;
		}
		i++;
	}
}

/* 기존 동일 변수 존재 시 해당 식 삭제 */
/* parameter : 변수명 */
/* return : 없으면 -1, 있으면 해당 순서값(i)*/
int exch_data(char* str)
{
	int i = 0, j = 0;
	while (i < n)
	{
		if (strcmp(data_set[i]->name, str) == 0)
		{
			j++;
			break;
		}
		i++;
	}
	if (j == 0)
		return -1;
	else
		inside_free(i);
	return i;
}

/* Data 변수 저장 */
/* parameter : 전체 입력값, '='위치 포인터 */
/* return : 정상 1, 비정상 0 */
int save_data(char* str, char* equal_p)
{
	*equal_p = '\0';
	int status = 0;	// 기존 변수에 추가하면 0, 새로 만들어서 추가하면 1

	/* 이미 있는 변수라면 exch_data에서 찾아서 기존 값을 없앤 후,
	c값을 리턴받은 값으로 바꿔준다.*/
	int c = n, j = 0;
	if ((j = exch_data(str)) != -1)
		c = j;

	/* 기존에 없는 변수라면 새로운 공간을 할당해준다. */
	else
	{
		if (n != 0 && (n % 10) == 0)
			if (my_realloc(data_set) == 0)
			{
				puts("%d개 이상의 변수 저장 공간이 없습니다.");
				return 0;
			}
		if ((data_set[c] = (Data*)malloc(sizeof(Data))) == NULL)
		{
			puts("변수 저장에 실패했습니다. 메모리 부족.");
			return 0;
		}
		data_set[c]->name = _strdup(str);
		data_set[c]->head = NULL;
		status = 1;
	}


	/* 식을 연결리스트에 분리하여 저장 */
	int i = 0, start = 0, end = 0;
	equal_p += 1; // '='다음의 시작점으로 위치를 옮겨준다. (식의 시작점)
	// 첫 문자에서 기호가 있을 경우 상정
	if (equal_p[0] == '+' || equal_p[0] == '-')
		i++;
	while (1)
	{
		if (equal_p[i] != '+' && equal_p[i] != '-' && equal_p[i] != '\0')
			i++;
		else if (equal_p[i] == '+' || equal_p[i] == '-')
		{
			end = i;
			if (extract_and_add(c, data_set[c]->head, equal_p, start, end) == 0)
				return 0;
			start = i++;
		}
		else if (equal_p[i] == '\0')
		{
			end = i;
			if (extract_and_add(c, data_set[c]->head, equal_p, start, end) == 0)
				return 0;
			break;
		}
	}
	if (status == 1) n++;  // 새로 추가된 경우에만 n을 늘려준다. 
	return 1;
}

/* 하나의 다항식에서 coef, expo 추출해서 inside에 추가 */
/* parameter : c번째 변수, 가르키는 연결리스트, 전체 문자열, 부분 문자열의 시작과 끝 */
int extract_and_add(int c, Inside* head, char* str, int start, int end)
{
	int coef = 0, expo = 0, operator = 1;
	int  i;

	for (i = start; i < end; ++i)
	{
		/* 첫 글자가 부호일 때 */
		if (str[i] == '+');
		else if (str[i] == '-')
			operator = -1;

		/* 숫자가 나올 경우 */
		else if (str[i] > 47 && str[i] < 58)
			coef = (coef * 10) + (str[i] - '0');

		/* x가 나올 경우 */
		else if (str[i] == 'x')
		{
			if (coef == 0) coef = 1;  // coef가 초기값인데 x가 나오면 1값 부여
			expo = 1;
		}
		/* ^가 있을 경우 */
		else if (str[i] == '^')
		{
			expo = atoi(&str[i + 1]);
			break;
		}
	}
	coef *= operator;
	if (add_inside(c, head, coef, expo) == 0)
		return 0;

	return 1;
}

/* Inside 하나 추가 */
/* parameter : (c번째 변수)의 (연결리스트), 추가할 (coef), (expo) 값 */
int add_inside(int c, Inside* head, int coef, int expo)
{
	/* 가장 처음 head 생성 */
	if (head == NULL)
	{
		Inside* first;
		if ((first = (Inside*)malloc(sizeof(Inside))) == NULL)
		{
			puts("메모리 할당에 실패했습니다.");
			return 0;
		}
		first->coef = coef;
		first->expo = expo;
		first->next = NULL;
		data_set[c]->head = first;
		return 1;
	}

	/* 이후에 추가될 때 */
	Inside* p = head;
	Inside* q = NULL;
	while (p != NULL)
	{
		if (p->expo > expo)
		{
			q = p;
			p = p->next;
		}
		else break;
	}
	if (p != NULL && p->expo == expo)  // 차수가 같은 변수가 있을 때
	{
		if ((p->coef += coef) == 0)  // 더해서 0이 되어 제거돼야할 경우
		{
			if (q == NULL)  // 첫 번째 일 때 
				data_set[c]->head = p->next;
			else  // 두 번째 이상일 때
				q->next = p->next;
			free(p);
		}
		return 1;
	}

	else	// 같은 차수가 없어 새로 생성해서 연결해줘야 할 때 
	{
		Inside* temp;
		if ((temp = (Inside*)malloc(sizeof(Inside))) == NULL)
		{
			puts("메모리 할당에 실패했습니다.");
			return 0;
		}
		temp->coef = coef;
		temp->expo = expo;
		if (q == NULL)  // 가장 처음 순서일 때
		{
			temp->next = head;
			data_set[c]->head = temp;
		}
		else  // q 다음번에 들어가야할 때
		{
			temp->next = q->next;
			q->next = temp;
		}
	}
	return 1;
}

/* 연결리스트 전체 초기화 시키기 */
/* parameter : 초기화시킬 연결리스트를 가지고 있는 Data_set의 변수 넘버 */
void inside_free(int c)
{
	Inside* p = data_set[c]->head;
	Inside* q = NULL;
	while (p != NULL)
	{
		q = p;
		p = p->next;
		free(q);
	}
	data_set[c]->head = NULL;
}

/* 계산 결과 출력 */
/* parameter : 문자열 */
/* return : void */
void calc(char* str)
{
	int result = 0;
	char* arg;
	arg = strtok(str, " ");
	arg = strtok(NULL, " ");
	/* 변수명 검색 */
	Inside* p = NULL;
	int j = 0;
	for (int i = 0; i < n; ++i)
	{
		if (strcmp(data_set[i]->name, arg) == 0)
		{
			p = data_set[i]->head;
			j++;
			break;
		}
	}
	if (j == 0)
	{
		puts("해당 변수가 없습니다.");
		return;
	}

	int x = atoi(strtok(NULL, " "));
	/* 식 계산 */
	while (p != NULL)
	{
		int x_result = 1;
		for (int i = 0; i < p->expo; i++)
			x_result *= x;
		result += p->coef * x_result;
		p = p->next;
	}
	printf("계산결과 : %d\n", result);
}


/* 식의 유효성 검증 */
/* parameter : 검증할 전체 문자열 */
/* return : 정상 1, 비정상 0 */
int validity(char* arg)
{
	int i = 0;
	while (arg[i] != '\0')
	{
		/* 숫자(1~9) 또는 허용된 기호가 아닐 경우 */
		if (arg[i] != 'x' && arg[i] != '+' && arg[i] != '-' && arg[i] != '^' &&
			(arg[i] < 48 || arg[i] > 57)) return 0;
		/* 가장 처음에 +나 ^가 나왔을 때 */
		else if (i == 0 && (arg[i] == '+' || arg[i] == '^')) return 0;
		/* x 다음에 바로 숫자가 나올 때 */
		else if (arg[i] == 'x' && arg[i + 1] < 58 && arg[i + 1] > 48) return 0;
		/* ^ 앞에 x가 아니거나 뒤에 숫자가 아닐 때 */
		else if (i > 0 && arg[i] == '^' && (arg[i - 1] != 'x' ||
			(arg[i + 1] < 48 || arg[i + 1] > 57)))
			return 0;
		/* 연산 기호 및 변수가 연속으로 나올 때 */
		else if ((arg[i] == '+' || arg[i] == '-') && (arg[i + 1] == '+' ||
			arg[i + 1] == '-'))
			return 0;
		/* x 변수가 연속으로 나올 때*/
		else if (arg[i] == 'x' && arg[i + 1] == 'x')
			return 0;
		i++;
	}
	return 1;
}


/* realloc 함수 구현 */
/* parameter : Data** 타입 포인터 */
/* return : 정상 1, 비정상 0*/
int my_realloc(Data** p)
{
	static size = LIST;
	size += LIST;  // 한번 실행시킬 때마다 LIST(10) 씩 늘어남
	Data** temp;
	if ((temp = (Data**)malloc(sizeof(Data) * size)) == NULL)
		return 0;

	for (int i = 0; i < n; ++i)
		temp[i] = data_set[i];
	free(data_set);
	data_set = temp;
	return 1;
}