[자료구조 - C언어] 자료구조 제12강: 연결 리스트 - 다항식(3)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

0. Use Case

• $ 프롬프트로 입력
• 공백 입력 가능 ~ 무시
• 계수는 정수, 지수는 양수
• calc f 1 = f(1)을 의미 ~ 다음 줄에 결괏값 출력
• g= f + g ~ 두 개의 다항식을 정해, 새로운 다항식을 만들 수 있다
• 기존에 존재하던 다항식을 덮어쓸 수 있다
• 입력 - 차수에 대한 내림차순 X, 동일 차수의 항이 여럿
• 출력 - 차수에 대한 내림차순 O
• 동일 이름의 함수를 새로 정의 O
• 연결 리스트를 이용하여 하나의 다항식을 표현하는 구조체 Polynomial을 정의
  • 각각의 항을 연결 리스트로 연결 & 차수에 대한 내림차순
  • 동일 차수의 항을 2개 이상 X, 계수가 0인 항 존재 X
  • 하나의 항은 계수와 지수로 정의, 하나의 항은 구조체 Term으로 정의
  • 변수 x의 값이 주어질 때 값 계산하는 함수 제공

 

 

1. Polynomial *create_by_parse_polynomial(char name, char *body)

• 하나의 다항식을 각각의 항으로 잘라서 계수와 차수를 분석하는 함수

• f(x) = 5x^3 -4x^2 + 12를
  • 5x^3, -4x^2, +12로 구분한 후
  • [begin_term, i): begin_term부터 i까지 parse_and_add_term함수로 처리
    • parse_and_add_term함수에서 0을 리턴 받으면 제대로 된 다항식 정의가 아니라는 뜻이기 때문에
      • 가비지가 된 ptr_poly를 destory한다.
  • 문장이 끝날 때까지 begin_term=i; 갱신하며 다음 항으로 이동

Polynomial *create_by_parse_polynomial(char name, char* body){
    Polynomial *ptr_poly = create_polynomial_instance(name);
    
    //i는 body를 순회, begin_term은 하나의 항의 시작 위치
    int i =0, begin_term=0;
    //body가 끝날 때 까지
    while(i<strlen(body)){
        //body를 순회하면서 + 또는 - 를 읽으면
        if(body[0]=="+" || body[0]=="-")
            i++;
        //하나의 항이 끝날 때 까지 전진
        //그 다음 항의 + 또는 -를 만나면 종료
        //i<strlen(body)는 마지막 항의 끝에는 +, -가 없기 때문에 종료 조건
        while(i<strlen(body) && body[i]!="+" && body[i]!="-")
            i++;
        //잘라진 하나의 항에서 계수와 차수를 인식한 후 ptr_poly에 add하는 함수
        //잘라진 하나의 항 = [begin_term, i) = begin_term 부터 (i-1) 까지
        int result = parse_and_add_term(body, begin_term, i, ptr_poly);
        //제대로 된 다항식의 정의가 아니라면 0을 리턴
        if(result==0){
            //가비지가된 ptr_poly를 free처리
            destory_polynomial(ptr_poly);
            return NULL;
        }
        //다음 항의 시작 위치는 i
        begin_term=i;
    }
    return ptr_poly;
}

1-1. int parse_and_add_term(char *expr, int begi, int end, Polynomial *p_poly)

• 하나의 항을 분석하고 polys에 삽입
• 부호(+ 또는 -)를 파악해서
  • +: sign_coef = 1
  • -: sign_coef = -1
  • 첫 번째 항일 경우 부호가 없을 수도 있다
• 계수의 절댓값 파악하기
  • coef = coef * 10 + (int)(expr[i]-'0');
  • 아스키코드 → 정수 변환
• 실제 계수 값 계산하기
  • coef == 0
    • 계수가 0이 아니라 -1 또는 +1
    • coef = sign_coef
  • 이외는 coef *= sign_coef(부호만 곱해주면 된다)
• 계산한 계수가 상수항인지 파악
  • → 상수항이라면 add_term(coef, 0, p_poly);
  • → 상수항이 아니라면 그다음 문자는 반드시 x
    • → 1차 항인지 확인
      • → 1차 항이라면 add_term(coef, 1, p_poly);
      • → 1차항이 아니라면 그다음 문자는 반드시 ^
• 지수 파악하기
• add_term(coef, expo, p_poly);

int parse_and_add_term(char *expr, int begin, int end, Polynomial *p_poly){
    
    int i=begin;
    //sign_coef: 부호, coef: 계수의 절대값, expo: 지수
    int sign_coef=1, coef=0, expo=1;
    
    //부호
    //+ 또는 - 기호로 계수의 부호를 결정
    //하지만 첫 번째 항은 + 또는 -기호가 없을 수도 있다.
    if(expr[i]=='+')
        i++;
    else if(expr[i]=='-'){
        sign_coef = -1;
        i++;
    }
    //digit들을 읽어 계수의 절대값(coef)를 계산
    //계수가 1 또는 -1인 경우는 digit들이 하나도 없을 수도 있다.
    //  ->coef가 0인 경우 계수는 0이 아니라 1 또는 -1
    while(i<end&&expr[i]>='0' && expr[i]<='9'){
        //아스키코드에서 정수로 변환
        //'123' -> 123
        coef = coef * 10 + (int)(expr[i]-'0');
        i++;
    }
    
    //실제 계수
    if(coef==0)    //계수가 +/- 1: -x^2 or x^4
       coef=sign_coef;
    else
        coef*=sign_coef;
    
    //항이 끝났다 = 계수부분만 있다 = 차수가 0 = 상수항
    if(i>=end){
        add_term(coef, 0, p_poly);
        return 1;
    }
    
    //상수항이 아니라면 그 다음 문자는 반드시 x
    if(expr[i]!='x')
        return 0;
    i++;
    
    //계수 다음에 x가 나오고 문자열이 끝나면 -> 1차항
    if(i>=end){
        add_term(coef, 1, p_poly);
        return 1;
    }
    
    //x다음에 ^가 아닌 다른 문자가 등장해서는 안된다.
    if(expr[i] !='^')
        return 0;
    i++;
    
    //지수
    expo=0;
    while(i<end&&expr[i]>='0' && expr[i]<='9'){
        expo = expo * 10 + (int)(expr[i]-'0');
        i++;
    }
    
    add_term(coef, expo, p_poly);
    
    return 1;
}

1-2. void insert_polynomial(Polynomial *ptr_poly)

• 새로운 다항식을 정의해서 polys배열에 삽입하는 함수
• 이미 정의된 이름의 다항식이 배열에 존재하는 경우에 유의
  • 기존의 다항식에 덮어쓰기

//새로운 다항식을 정의해서 polys배열에 삽입
//case 1. 이미 정의된 이름의 다항식이 배열에 존재 ~ 기존의 다항식 삭제
//case 2. 아예 새로운 다항식
void insert_polynomial(Polynomial *ptr_poly){
    for(int i=0; i<n; i++){
        //case1. 이름이 같은 다항식이 존재한다면
        if(polys[i]->name == ptr_poly->name){
            //다항식을 덮어쓸 경우 기존의 다항식 객체를 free
            destory_polynomial(polys[i]);
            //빈 자리에 채워 넣기
            polys[i]=ptr_poly;
            return;
        }
    }
    //case2. 같은게 없다면
    polys[n++] = ptr_poly;
}

1-3. void destory_polynomial(Polynomial *ptr_poly)

• ptr_poly에 달려 있는 각각의 노드들은 따로따로 malloc 해서 생성한 것이기 때문에
  • Polynomial 객체 하나를 free 한다고 해서 Terms 객체들이 자동으로 free 되지 않음

void destory_polynomial(Polynomial *ptr_poly){
    if(ptr_poly == NULL)
        return;
    Term *t = ptr_poly->first, *tmp;
    while(t!=NULL){
        tmp = t;        //t를 먼저 삭제하면 t다음 노드의 주소를 알 수 없기 때문에 복사
        t = t->next;    //t가 한 칸 먼저 전진
        free(tmp);      //t가 가리키고 있던 노드를 free
    }
    free(ptr_poly);     //ptr_poly가 가리키는 다항식 객체를 free
}

 

 

2. 전체 코드

//  polynomial.c
//  연결리스트

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


#define MAX_POLYS 100
#define BUFFER_LENGTH 100

struct term{
    int coef;                    //계수
    int expo;                   //차수
    struct term *next; //다음 노드
};
typedef struct term Term;

typedef struct polynomial{
    char name;    //다항식의 이름
    Term *first;     //다항식을 구성하는 첫 번째 항의 주소
    int size;         //항의 개수
} Polynomial;

Polynomial *polys[MAX_POLYS];    //다항식들에 대한 포인터의 배열
int n = 0;                       //저장된 다항식의 개수

void handle_print(char name);
void handle_calc(char name, char *x_str);
void handle_definition(char *expression);
char *erase_blanks(char *expression);
Polynomial *create_by_add_two_polynomias(char name, char former, char later);
void insert_polynomial(Polynomial *pol);
Polynomial *create_by_parse_polynomial(char name, char*exp_body);
int parse_and_add_term(char *expr, int begin, int end, Polynomial *p_poly);
void destory_polynomial(Polynomial *ptr_poly);

//create instance
Term *create_term_instance(){
    Term *t = (Term *)malloc(sizeof(Term));
    t -> coef = 0;
    t -> expo = 0;
    t -> next = NULL;
    
    return t;    //생성된 주소를 리턴
}

Polynomial *create_polynomial_instance(char name){
    Polynomial *ptr_poly = (Polynomial *)malloc(sizeof(Polynomial));
    ptr_poly -> name = name;
    ptr_poly -> size = 0;
    ptr_poly -> first = NULL;
    return ptr_poly;
}


void add_term(int c, int e, Polynomial *poly){
    //계수가 0이라면 실제로 존재하지 않음
    if(c==0)
        return;
    
    Term *p = poly -> first;
    Term *q = NULL;
    while(p!=NULL && p->expo > e){
        q = p;
        p = p->next;
    }
    
    //1. 동일 차수의 항이 존재하는 경우
    if(p!=NULL && p->expo == e){
        p->coef += c;
        //원래는 계수가 0이 아니었는데, 계산 후 0이 된 경우
        //그 노드를 제거해야 한다
        //제거시 이전 노드의 주소가 필요
        //즉, q의 다음 노드를 제거
        if(p->coef == 0){
            //q가 NULL이면 첫 번째 노드 삭제
            if(q==NULL){
                poly->first = p->next;
            }else{
                q->next = p->next;
            }
            poly->size--;
            free(p);      //불필요해진 노드 p는 free
        }
        return;
    }
        
    //2. 동일 차수의 항이 존재하지 않는 경우
    // - 새로운 노드를 만들어 다항식에 노드를 추가
    Term *term = create_term_instance();
    term->coef = c;
    term->expo = e;
    
    //q 바로 뒤에 삽입
    if(q==NULL){  //맨 앞에 삽입하는 경우
        term->next = poly->first;
        poly->first = term;
    }
    else{              //그렇지 않은 경우
        term->next = p;
        q->next = term;
    }
    poly->size++;
}

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;
}

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;
}

//하나의 항을 출력하는 함수
//개선된 print_term
void print_term(Term *pTerm){
    if (pTerm->coef>0)
        printf("+");
    
    if (pTerm->expo == 0)
        printf("%d", pTerm->coef);
    else{
        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->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);
            else 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");
}

int read_line(FILE *fp, char str[], int n){
    int ch, i = 0;
    while((ch = fgetc(fp)) != '\n' && ch != EOF){
        if (i<n)
            str[i++] = ch;
    }
    str[i] = '\0';

    //자신이 읽은 문자수를 리턴
    return i;
}


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);
        }
    }
}

void handle_print(char name){
    for(int i =0;i<n;i++){
        if (polys[i]->name == name){
            print_poly(polys[i]);
            return;
        }
    }
    printf("일치하는 함수가 존재하지 않습니다.\n");
}

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("일치하는 함수가 존재하지 않습니다.\n");
}
void handle_definition(char *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\n");
        return;
    }

    char *exp_body = strtok(NULL, "=");
    //몸통이 없거나 길이가 0이하라면
    if(exp_body==NULL || strlen(exp_body)<=0){
        printf("Invalid expression format.--\n ");
        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.\n");
            return;
        }
        //h
        char *later = strtok(NULL, "+");
        if(later==NULL || strlen(later)!=1){
            printf("Invalid expression format.\n");
            return;
        }
        
        Polynomial *pol = create_by_add_two_polynomias(f_name[0], former[0], later[0]);
        //없는 함수를 더하고자 한다면 null리턴
        if(pol==NULL){
            printf("Invalid expresion format.\n");
            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.\n");
            return;
        }
        insert_polynomial(pol);
    }
}

char* erase_blanks(char *expression){
    char *str = (char*)malloc(sizeof(char));
    int i, k = 0;
    for (i=0;i<strlen(expression);i++)
        if(expression[i]!=' ')
            str[k++] = expression[i];
    str[k]='\0';

    return str;
}

Polynomial *create_by_parse_polynomial(char name, char* body){
    Polynomial *ptr_poly = create_polynomial_instance(name);
    //i는 body를 순회, begin_term은 하나의 항의 시작 위치
    int i =0, begin_term=0;
    //body가 끝날 때 까지

    while(i<strlen(body)){
        //body를 순회하면서 + 또는 - 를 읽으면
        if(body[i] == '+'|| body[i] == '-')
            i++;

        //하나의 항이 끝날 때 까지 전진
        //그 다음 항의 + 또는 -를 만나면 종료
        //i<strlen(body)는 마지막 항의 끝에는 +, -가 없기 때문에 종료 조건
        while(i<strlen(body) && body[i] != '+' && body[i] != '-' )
            i++;
        

        //잘라진 하나의 항에서 계수와 차수를 인식한 후 ptr_poly에 add하는 함수
        //잘라진 하나의 항 = [begin_term, i) = begin_term 부터 (i-1) 까지

        int result = parse_and_add_term(body, begin_term, i, ptr_poly);
        //제대로 된 다항식의 정의가 아니라면 0을 리턴

        if(result==0){
            //가비지가된 ptr_poly를 free처리
            destory_polynomial(ptr_poly);
            return NULL;
        }
        //다음 항의 시작 위치는 i
        begin_term=i;
    }
    return ptr_poly;
}

Polynomial *create_by_add_two_polynomias(char name, char f, char g){
    Polynomial *h = create_polynomial_instance(name);
    Polynomial *fx, *gx;
    
    for(int i=0; i<n; i++){
        if(polys[i]->name == f)
            fx = polys[i];
        else if(polys[i]->name == g)
            gx = polys[i];
    }
    if(fx==NULL || gx==NULL){
        printf("No existing function name");
        return 0;
    }
    
    Term *p = fx->first;
    Term *q = gx->first;
    
    while(p!=NULL){
        add_term(p->coef, p->expo, h);
        p = p->next;
    }
    while(q!=NULL){
        add_term(q->coef, q->expo, h);
        q = q->next;
    }
    return h;
        
}


int parse_and_add_term(char *expr, int begin, int end, Polynomial *p_poly){
    
    int i=begin;
    //sign_coef: 부호, coef: 계수의 절대값, expo: 지수
    int sign_coef=1, coef=0, expo=1;
    
    //부호
    //+ 또는 - 기호로 계수의 부호를 결정
    //하지만 첫 번째 항은 + 또는 -기호가 없을 수도 있다.
    if(expr[i]=='+')
        i++;
    else if(expr[i]=='-'){
        sign_coef = -1;
        i++;
    }
    //digit들을 읽어 계수의 절대값(coef)를 계산
    //계수가 1 또는 -1인 경우는 digit들이 하나도 없을 수도 있다.
    //  ->coef가 0인 경우 계수는 0이 아니라 1 또는 -1
    while(i<end&&expr[i]>='0' && expr[i]<='9'){
        //아스키코드에서 정수로 변환
        //'123' -> 123
        coef = coef * 10 + (int)(expr[i]-'0');
        i++;
    }
    
    //실제 계수
    if(coef==0)    //계수가 +/- 1: -x^2 or x^4
       coef=sign_coef;
    else
        coef*=sign_coef;
    
    //항이 끝났다 = 계수부분만 있다 = 차수가 0 = 상수항
    if(i>=end){
        add_term(coef, 0, p_poly);
        return 1;
    }
    
    //상수항이 아니라면 그 다음 문자는 반드시 x
    if(expr[i]!='x')
        return 0;
    i++;
    
    //계수 다음에 x가 나오고 문자열이 끝나면 -> 1차항
    if(i>=end){
        add_term(coef, 1, p_poly);
        return 1;
    }
    
    //x다음에 ^가 아닌 다른 문자가 등장해서는 안된다.
    if(expr[i] !='^')
        return 0;
    i++;
    
    //지수
    expo=0;
    while(i<end&&expr[i]>='0' && expr[i]<='9'){
        expo = expo * 10 + (int)(expr[i]-'0');
        i++;
    }
    
    add_term(coef, expo, p_poly);
    
    return 1;
}

//새로운 다항식을 정의해서 polys배열에 삽입
//case 1. 이미 정의된 이름의 다항식이 배열에 존재 ~ 기존의 다항식 삭제
//case 2. 아예 새로운 다항식
void insert_polynomial(Polynomial *ptr_poly){
    for(int i=0; i<n; i++){
        //case1. 이름이 같은 다항식이 존재한다면
        if(polys[i]->name == ptr_poly->name){
            //다항식을 덮어쓸 경우 기존의 다항식 객체를 free
            destory_polynomial(polys[i]);
            //빈 자리에 채워 넣기
            polys[i]=ptr_poly;
            return;
        }
    }
    //case2. 같은게 없다면
    polys[n++] = ptr_poly;
}

void destory_polynomial(Polynomial *ptr_poly){
    if(ptr_poly == NULL)
        return;
    Term *t = ptr_poly->first, *tmp;
    while(t!=NULL){
        tmp = t;            //t를 먼저 삭제하면 t다음 노드의 주소를 알 수 없기 때문에 복사
        t = t->next;    //t가 한 칸 먼저 전진
        free(tmp);      //t가 가리키고 있던 노드를 free
    }
    free(ptr_poly);    //ptr_poly가 가리키는 다항식 객체를 free
}


void main(){
    process_command();
}

 

 

 

3. 실행 결과

$ f=6x^3+2x-5
$ g=4x^2-2x+6
$ print f
f=6x^3+2x-5
$ calc f 2
47
$ pring g
Unsupported Command
$ print g
g=4x^2-2x+6
$ clac g 5
Unsupported Command
$ calc g 4
62
$ h = g + f
$ print h
h=6x^3+4x^2+1
$ print g
g=4x^2-2x+6
$ pirnt f
Unsupported Command
$ print f
f=6x^3+2x-5
$ calc h 1
11
$ s = h + g
$ print s
s=6x^3+8x^2-2x+7
$ print h
h=6x^3+4x^2+1
$ print g
g=4x^2-2x+6
$ exit
Program ended with exit code: 0

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?v=C04nUFYsG-s