[자료구조 - C언어] 자료구조 제12강: 연결 리스트 - 다항식(2)
2022. 10. 21. 16:13ㆍCS/자료구조
728x90
//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎
2022. 10. 25
- void handle_definition(char *expression) 함수 수정
expression = erase_blanks(expression); -> expression = erase_blanks(expression);- void print_poly(Polynomial *p) 함수 조건 추가
if(t->expo==0)
printf("%d",t->coef);0. Use Case
- $ 프롬프트로 입력
- 공백 입력 가능 ~ 무시
- 계수는 정수, 지수는 양수
- calc f 1 = f(1)을 의미 ~ 다음 줄에 결괏값 출력
- g= f + g ~ 두 개의 다항식을 정해, 새로운 다항식을 만들 수 있다
- 기존에 존재하던 다항식을 덮어쓸 수 있다
- 입력 - 차수에 대한 내림차순 X, 동일 차수의 항이 여럿
- 출력 - 차수에 대한 내림차순 O
- 동일 이름의 함수를 새로 정의 O
연결리스트를 이용하여 하나의 다항식을 표현하는 구조체 Polynomial을 정의- 각각의 항을 연결 리스트로 연결 & 차수에 대한 내림차순
- 동일 차수의 항을 2개 이상 X, 계수가 0인 항 존재 X
하나의 항은 계수와 지수로 정의, 하나의 항은 구조체 Term으로 정의- 변수 x의 값이 주어질 때 값 계산하는 함수 제공
1. 다항식의 값을 계산하는 함수
- 다항식의 값을 계산하는 함수: 각각의 항을 계산
int evalPoly(Polynomial *poly, int x){
int result = 0;
Term *t = poly -> first;
while (t != NULL){
//각각의 항의 값을 계산하여 더한다
result += evalTerm(t, x);
t = t->next;
}
return result;
}
- 하나의 항을 계산하는 함수
int evalTerm(Term *term, int x){
int result = term -> coef;
for(int i=0; i<term->expo; i++){
//cx^e: c에 x를 e번 곱한다
result *= x;
}
return result;
}
2. 다항식 출력하기
- 개선된 print_term
- +- 중복
- x^1과 x^0 표현
- (+/-) 1x^e 표현에서 (+/-) 1 제외
//하나의 항을 출력하는 함수
//개선된 print_term
void print_term(Term *pTerm){
if (pTerm->coef>0)
printf("+");
if (pTerm->expo == 1){
if(pTerm->coef==1)
printf("x");
else if(pTerm->coef==-1)
printf("-x");
else
printf("%dx", pTerm->coef);
}
else if (pTerm->expo == 0)
printf("%d", pTerm->coef);
else{
if(pTerm->coef==1)
printf("x^%d", pTerm->expo);
else
printf("%dx^%d", pTerm->coef, pTerm->expo);
}
}
//다항식 전체를 출력하는 함수
void print_poly(Polynomial *p){
printf("%c=", p->name);
Term *t = p->first;
//첫 항 부호 없이 출력
if(t!=NULL)
if(t->expo!=1){
if(t->expo==0)
printf("%d",t->coef);
if(t->coef==1)
printf("x^%d", t->expo);
else if(t->coef==-1)
printf("-x^%d", t->expo);
else
printf("%dx^%d", t->coef, t->expo);
}else{
if(t->coef==1)
printf("x");
else if(t->coef==-1)
printf("-x");
else
printf("%dx", t->coef);
}
t = t->next;
//두 번째항 부터 출력
while(t!=NULL){
print_term(t);
t = t->next;
}
printf("\\n");
}- 이전 print_term
void print_term(Term *pTerm){
printf("%dx^%d", pTerm->coef, pTerm->expo);
}
void print_poly(Polynomial *p){
printf("%c=", p->name);
Term *t = p->first;
while(t!=NULL){
print_term(t);
printf("+");
t = t->next;
}
printf("\\n");
}3. process_command()
- 메인함수에서 호출되어 사용자의 명령어를 받아 처리하는 함수
void process_command(){
char command_line[BUFFER_LENGTH];
char copied[BUFFER_LENGTH];
char *command, *arg1, *arg2;
while(1){
printf("$ ");
//라인 단위로 입력을 읽은 다음
if(read_line(stdin, command_line, BUFFER_LENGTH) <= 0)
continue;
strcpy(copied, command_line);
command = strtok(command_line, " ");
//함수 출력
if(strcmp(command, "print") == 0){
arg1 = strtok(NULL, " ");
//예외처리
if(arg1 == NULL){
printf("Invalid arguments.\\n");
continue;
}
handle_print(arg1[0]); //함수 이름은 한 글자 char형
}
//함수 계산
else if(strcmp(command, "calc") == 0){
//함수 이름
arg1 = strtok(NULL, " ");
if(arg1 == NULL){
printf("Invalid arguments.\\n");
continue;
}
//x 값
arg2 = strtok(NULL, " ");
if(arg2 == NULL){
printf("Invalid arguments.\\n");
continue;
}
handle_calc(arg1[0], arg2);
}
//함수 종료
else if (strcmp(command, "exit")==0)
break;
//나머지는 새로운 함수를 정의하거나 기존 함수를 재정의
else{
//tokenizing 이전의 입력 필요
handle_definition(copied);
}
}
}3-1. void handle_print(char name)
- polys 배열에서 다항식의 이름을 비교해서 출력
void handle_print(char name){
for(int i =0;i<n;i++){
if (polys[i]->name == name){
print_poly(polys[i]);
return;
}
}
printf("일치하는 함수가 존재하지 않습니다.");
}
3-2. void handle_calc(char name, char *x_str)
- polys 배열에서 다항식의 이름을 찾은 후
- 변수 x_str을 다항식에 대입한 후 결괏값 출력
void handle_calc(char name, char *x_str){
for(int i =0;i<n;i++){
if (polys[i]->name == name){
printf("%d\\n", evalPoly(polys[i], atoi(x_str)));
return;
}
}
printf("일치하는 함수가 존재하지 않습니다.");
}
3-3. void handle_definition(char *expression)
- 새로운 함수를 정의하거나 기존 함수를 재정의하는 함수
- tokenizing 이전의 입력값 필요
void handle_definition(char *expression){
//문자열 expression에서 모든 공백 문자들을 제거하여 압축
expression = erase_blanks(expression);
//1. 기존 함수를 더해서 새로운 함수 정의
//2. 완전 새로운 함수 정의
//1, 2 모두 '='을 delimiter로 tokenizing
char *f_name = strtok(expression, "=");
//함수 이름이 없거나 한 글자가 아니라면
if(f_name==NULL || strlen(f_name)!=1){
printf("Unsupported Command");
return;
}
char *exp_body = strtok(NULL, "=");
//몸통이 없거나 길이가 0이하라면
if(exp_body==NULL || strlen(exp_body)<=0){
printf("Invalid expression format. --");
return;
}
//case1. 기존 함수를 더해서 새로운 함수를 정의
//g=f+h
if(exp_body[0]>='a' && exp_body[0]<='z' && exp_body[0]!='x'){
//f
char *former = strtok(exp_body, "+");
if(former==NULL || strlen(former)!=1){
printf("Invalid expression format.");
return;
}
//h
char *later = strtok(NULL, "+");
if(later==NULL || strlen(later)!=1){
printf("Invalid expression format.");
return;
}
Polynomial *pol = create_by_add_two_polynomias(f_name[0], former[0], later[0]);
//없는 함수를 더하고자 한다면 null리턴
if(pol==NULL){
printf("Invalid expresion format.");
return;
}
//polys 배열에 삽입하는 함수, 동일한 이름이 존재시 교체
insert_polynomial(pol);
}
//case2. 완전 새로운 함수를 정의
else{
Polynomial *pol = create_by_parse_polynomial(f_name[0], exp_body);
if(pol==NULL){
printf("Invalid expression format.");
return;
}
insert_polynomial(pol);
}
}3-4. char *erase_blanks(char *expression)
- 문자열 expresion에서 모든 공백 문자들을 제거하여 압축
- 문자열의 끝에 '\0' 추가
char *erase_blanks(char *expression){
char *str = (char*)malloc(sizeof(expression));
int i, k = 0;
for (i=0;i<strlen(expression);i++)
if(expression[i]!=' ')
str[k++] = expression[i];
str[k]='\\0';
return str;
}
부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.
https://www.youtube.com/watch?v=kvZdKW6t1O8&feature=emb_imp_woyt
728x90
'CS > 자료구조' 카테고리의 다른 글
| [자료구조 - C언어] 자료구조 제13강: 이중 연결 리스트 (0) | 2022.10.26 |
|---|---|
| [자료구조 - C언어] 자료구조 제12강: 연결 리스트 - 다항식(3) (0) | 2022.10.25 |
| [자료구조 - C언어] 자료구조 제12강: 연결 리스트 - 다항식(1) (0) | 2022.10.20 |
| [자료구조 - C언어] 자료구조 제11강: 연결 리스트 - 개념과 기본 동작들(5) (0) | 2022.10.19 |
| [자료구조 - C언어] 자료구조 제11강: 연결 리스트 - 개념과 기본 동작들(4) (1) | 2022.10.19 |