워낙 간단한 수준이라 주요 포인트만 짚어보겠습니다.
해당 과제는 유투브 '권오흠'님의 자료구조 강의를 참조하였습니다.
[ 메인 함수 ]
- 각 다항식을 차수별로 정렬하기 위해 구조체의 연결리스트 방식을 사용
- read_line 함수에서 명령어를 읽어서 처리하며, 입력 글자가 없으면 continue
#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;
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;
}
[ read_line() - 명령어 읽어서 분석하기 ]
- 명령어 읽을 때 변수 저장 또는 일반 명령어를 구분하여 처리
- gets함수는 설정한 길이가 넘어가면 런타임 에러 발생
- fgets함수는 런타임 에러는 나지 않지만 버퍼에서 '\n'까지 가져와서 저장
- 둘 다 공백제거 기능이 없기 때문에 대부분 입력 함수는 직접 만들어서 쓰는게 편리함
- 쓸데없는 중복 공백을 제거하고 글자 사이에는 한칸만 공백을 남겨둠
- 파일로 한번에 추가하는 경우를 상정하여, 입력은 File* 타입으로 받음 (argument를 stdin으로 넘겨주면 사용하면 버퍼에서 가져옴)
- 파일로 읽을 때는 파일의 끝(EOF)에 도달했을 때도 멈추도록 조건을 꼭 넣어줘야 함
※ Point
isspace() 함수 사용 시, 적용 가능한 범위가 아스키코드 상 -1 ~ 255 범위 안이기 때문에 한글 입력시 에러 발생, 이를 피하기 위해 절대값을 반환하는 abs() 함수를 함께 써줌
(Expression: c>=-1 && <=255와 같은 에러 발생)
/*한줄 읽기*/
/* 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;
}
[ remove_space() - 입력된 문자열에서 모든 공백 제거 및 '=' 위치 반환 ]
- 일반 명령어와는 달리 변수 입력의 경우 공백이 있으면 처리가 불편해서 미리 공백을 제거해줌
- 저장 함수에서 '='을 기준으로 변수와 식을 분리하므로 해당 위치의 포인터를 반환
/* 공백 제거해주기 */
/* 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;
}
[ validity() - 식의 유효성 검증 ]
- 한개의 항 씩 계산하거나 나눌 때 유효성 검증을 해볼까 했지만 오히려 그게 더 귀찮고 복잡한 코드가 돼버려 그냥 따로 함수로 추가
- 각각의 경우의 수를 모두 검사하는 방식으로 하드코딩
/* 식의 유효성 검증 */
/* 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;
}
[ my_strtock() - 여러 구분자로 문장을 잘라서 시작 위치값을 리턴 ]
- 기본적으로 strtok와 같은 결과 ('+', '-', '=' 기호를 기준으로 잘라줌)
- 문장의 마지막 단어에 도달할 때까지 계속 잘라나가야 하기 때문에 변수들은 static으로 지정함 (함수가 종료되더라도 변수의 값이 저장되어 있음)
※ Point
strtok는 제공된 문자열에 직접 접근하여 구분자를 '\0'값으로 바꿔버리기 때문에 다시 써야하는 문자열이라면 미리 복사해두고 진행해두는 것이 좋음
/* 문자열을 =, +, -으로 순차적으로 나눠서 반환 (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++;
}
}
[ save_data() - 새로운 변수 입력 시 저장 ]
- 먼저 l_value가 기존에 존재하는 변수인지 exch_data() 함수를 통해 확인 후, 존재한다면 기존 데이터를 모두 지워두고 시작 (해당 변수의 Inside* head에 할당 된 연결리스트의 메모리 free)
- data_set 배열의 갯수가 초기에 LIST(10)이었으므로, n이 10에 도달해 있으면 공간을 늘려줌
- my_realloc()함수, 기본함수 realloc을 사용해도 되지만 그냥 한번 만들어봤음
- 어느 순서에 저장할지를 미리 판단 후, extract_and_add() 함수로 연결리스트를 만들어줌
- 이 때 전체 식을 '+', '-' 기호로 잘라서 필요한 정보를 arguments로 함수에 넘겨줘야 함
- my_strtok으로는 '+', '-' 기호에 대한 정보를 넘겨주기 까다롭기 때문에 함수 내에서 처리함
/* 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;
}
[ exch_data() - 기존 l_value가 있으면 기존 head 값을 free하고 해당 위치를 반환 ]
- 해당 변수를 찾은 후, inside_free 함수로 연결리스트 전체를 free하고 위치정보를 반환
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;
}
[ inside_free() - 연결리스트 전체 free ]
- 코딩보다 함수/변수 작명이 더 어려운 듯.. 그러나 코드가 복잡해질 수록 이름은 매우 중요해짐
/* 연결리스트 전체 초기화 시키기 */
/* 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;
}
[ extract_and_add - 주어진 하나의 식을 지수(coef)와 계수(expo)로 분리 ]
- 식마다 형식이 다르기 때문에 (2x^2, -3x^3, 2x, 2 등등) 하나씩 읽어가며 판단
- 지수와 계수를 분리하여 add_inside 함수에 전달
- 첫 숫자 추출은 atoi를 써도 되지만 오히려 한글자씩 읽어서 변환하는게 코드가 깔끔하여 그렇게 함
/* 하나의 다항식에서 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;
}
[ add_inside - 주어진 arguments 값을 가지고 연결리스트를 순서에 맞게 추가 ]
- 기준 순서에 맞게, coef 값과 expo 값으로 연결리스트를 만든 후 해당 순서에 삽입
- 사실 int c를 통해 몇번 째 변수에 연결리스트를 추가할지 알려줬으므로, Inside* head는 argument 로 받을 필요가 없지만.. 계속 소스를 수정하다보니 중복으로 들어가게 됨 (c값만 주거나 또는 Inside** 더블 포인터 타입으로 하나만 주면 됨)
/* 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;
}
[ plus() - 변수끼리 더하기 ]
- validity() 함수에서 유효성 검증에 실패하면 변수끼리 더하는 함수로 이동
- 변수 = 변수+변수' 형태에서 만약 모든 변수가 식과 동일한 형태 (f=2x^2+3x)라면 식의 저장이 우선됨
- 먼저 plus_validity() 함수에서 입력받은 모든 변수가 실제 존재하는지 확인
- 이후 임시 변수를 하나 생성하여 add_inside를 통해 모든 변수의 연결리스트를 모두 더해줌
- 저장해야하는 '='의 왼쪽(l_value) 변수가 존재하면 해당 변수에 걸려있는 연결리스트를 모두 Free해주고 새로 생성한 연결리스트의 head값을 입력해줌
- l_value가 기존에 없는 변수라면 임시 저장된 변수의 이름만 입력값으로 바꿔줌
※ Point
- malloc(동적할당)을 할 시에는 메모리가 부족해 할당받지 못했을 경우에 대해 return 값을 줄 것
- 동적할당 받은 내용을 지울 때는 포인터로 연결된 모든 부분들을 모두 Free 해줄 것
/* 변수끼리 합치기 */
/* 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 번째에 들어가는게 맞다면
data_set[n++]->name = _strdup(l_value); // 해당변수 이름을 l_value로 바꿔주고 n++;
else // 기존 변수 값에 넣어줘야 한다면
{
inside_free(c); // 기존 변수의 연결리스트를 모두 Free 시켜주고
data_set[c]->head = data_set[n]->head; // 신규 생성된 연결리스트의 head 부여
free(data_set[n]); // 임시 생성된 Temp 변수 Free
}
return 1;
}
[ plus_validity() - '변수 = 변수 + 변수' 형태에 실제 변수 값이 모두 존재하는지 확인 ]
- l_value 값이 존재한다면 해당 값을 c에 넣어줌
- 그냥 c값을 리턴해도 되지만 그냥 포인터로 바깥 함수에 직접 넣어줌, 포인터가 젤 편한듯..
/* (변수 + 변수) 형태의 유효성 검증*/
/* 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;
}
[ my_printf() - 변수에 저장된 연결리스트들을 형식에 맞게 출력 ]
- 형식이 경우마다 제각각이므로, 경우의 수를 많이 나눠야 함
- 뭔가 더 깔끔하고 간결하게 할 수 있는 방법을 고민해봤지만 생각이 나지 않음..
/* 검색된 변수의 값 출력하기 */
/* 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"); // 식이 끝나면 한줄 띄워준다.
}
[ calc() - 변수명과 x값 입력하면 계산 결과 출력 ]
- 사실 read_line() 함수에서 처음부터 공백을 모두 없애고 시작했으나, calc() 함수를 만들면서 글자사이 공백을 남기는 걸로 바꿈 (변수명과 x값을 구분할 수 있는 방법이 없기 때문에..)
/* 계산 결과 출력 */
/* 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);
}
'▸C언어 > 알고리즘 및 자료구조' 카테고리의 다른 글
스택구조_후위표기식_수식 계산하기(괄호 포함 수식) [2/3] (0) | 2019.12.09 |
---|---|
스택구조_후위표기식_수식 계산하기(괄호 없는 수식) [1/3] (1) | 2019.12.09 |
스택구조_괄호 수식 검증 [1/1] (0) | 2019.12.09 |
연결리스트_일반 배열 vs 연결리스트 [3/3] (0) | 2019.12.09 |
연결리스트_다항식_구현목표 및 전체코드 [1/3] (0) | 2019.12.05 |
댓글