[C언어 포인터 기반 스택 알고리즘] 후위 표기법 계산기 만들기

💡 이번에는 포인터 기반 스택을 사용하여 후위 표기법 계산기를 만들어보았다.

문제

💡 스택 기반 계산기를 만들어보시오.

당연히 없는 문제기에 대충 내가 만들었다.

해답

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

typedef struct Node {
    char data[100];
    struct Node *next;
} Node;

typedef struct Stack {
    Node *top;
} Stack;

void push(Stack *stack, char *data) {
    Node *node = (Node*)malloc(sizeof(Node));
    strcpy(node->data, data);
    node->next = stack->top;
    stack->top = node;
}

char* getTop(Stack *stack) {
    Node *top = stack->top;
    return top->data;
}

char* pop(Stack *stack) {
    if (stack->top == NULL) {
        printf("스택 언더플로우가 발생했습니다.\\n");
        return NULL;
    }
    Node *node = stack->top;
    char *data = (char*)malloc(sizeof(char) * 100);
    strcpy(data, node->data);
    stack->top = node->next;
    free(node);
    return data;
}

int getPriority(char *i) {
    if (!strcmp(i, "(")) return 0;
    if (!strcmp(i, "+") || !strcmp(i, "-")) return 1;
    if (!strcmp(i, "*") || !strcmp(i, "/")) return 2;
    return 3;
}

char* transition(Stack *stack, char **s, int size) {
    char res[1000] = "";
    for (int i = 0 ; i < size ; i++) {
        if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
            while (stack->top != NULL && getPriority(getTop(stack)) >= getPriority(s[i])) {
                strcat(res, pop(stack));
                strcat(res, " ");
            }
            push(stack, s[i]);
        } else if (!strcmp(s[i], "(")) {
            push(stack, s[i]);
        } else if (!strcmp(s[i], ")")) {
            while (strcmp(getTop(stack), "(")) {
                strcat(res, pop(stack));
                strcat(res, " ");
            }
            pop(stack);
        } else {
            strcat(res, s[i]);
            strcat(res, " ");
        }
    }
    while (stack->top != NULL) {
        strcat(res, pop(stack));
        strcat(res, " ");
    }
    return res;
}

void calculate(Stack *stack, char **s, int size) {
    int x, y, z;
    for (int i = 0 ; i < size ; i++) {
        if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
            x = atoi(pop(stack));
            y = atoi(pop(stack));
            if (!strcmp(s[i], "+")) {
                z = y + x;
            }
            if (!strcmp(s[i], "-")) {
                z = y - x;
            }
            if (!strcmp(s[i], "*")) {
                z = y * x;
            }
            if (!strcmp(s[i], "/")) {
                z = y / x;
            }
            char buffer[100];
            sprintf(buffer, "%d", z);
            push(stack, buffer);
        } else {
            push(stack, s[i]);
        }
    }
    printf("%s\\n", pop(stack));
}

int main(void) {
    Stack stack;
    stack.top = NULL;
    char a[100] = "( ( 3 + 4 ) * 5 ) - 5 * 7 * 5 - 5 * 10";
    int size = 1;
    for (int i = 0 ; i < strlen(a) ; i++) {
        if (a[i] == ' ') {
            size++;
        }
    }
    char *ptr = strtok(a, " ");
    char **input = (char**)malloc(sizeof(char*) * size);
    for (int i = 0 ; i < size ; i++) {
        input[i] = (char*)malloc(sizeof(char) * 100);
    }
    for (int i = 0 ; i < size ; i++) {
        strcpy(input[i], ptr);
        ptr = strtok(NULL, " ");
    }
    char b[1000] = "";
    strcpy(b, transition(&stack, input, size));
    printf("후위 표기법 : %s\\n", b);
    size = 1;
    for (int i = 0 ; i < strlen(b) - 1 ; i++) {
        if (b[i] == ' ') {
            size++;
        }
    }
    char *ptr2 = strtok(b, " ");
    for (int i = 0 ; i < size ; i++) {
        strcpy(input[i], ptr2);
        ptr2 = strtok(NULL, " ");
    }
    calculate(&stack, input, size);

    return 0;
}

설명

코드가 정말 길다.

이번에는 사용해보지 않은 함수도 써보고, 복잡하기 때문에 라이브러리 내장 함수에대해서도 함께 설명해보겠다.

중위 표기법을 후위 표기법으로 변경

• 중위 표기법은 평소 우리가 잘 아는 표기법이다.
  • 예) 7 * 5 + 3
• 후위 표기법으로 변경하는 이유는 컴퓨터가 계산하기에 편한 수식의 형태이기 때문이다.
  • 예) 7 5 * 3 +

라이브러리와 typedef으로 구조체 선언

#include <stdio.h>
#include <stdlib.h>
#include <string.h>  // 문자열을 처리할 것이기 때문에 string.h파일을 include 해준다.

typedef struct Node {
    char data[100]; // 숫자가 길수도 있기 때문에 문자열로 초기화 한다.
    struct Node *next;
} Node;

typedef struct Stack {
    Node *top;
} Stack;

typedef 는 예전부터 사용했던 것인데 무엇인지는 제대로 모르고 지나갔다.

typedef 키워드는 C언어에서 자료형을 새롭게 이름을 붙일 때 쓰는 키워드다.

typedef를 이용하면 main함수에서 구조체를 선언할 때 매번 struct 키워드를 써줄 필요가 없다.

구조체의 별칭은 구조체를 정의할 때 중괄호 뒤에 써주면 된다.

typedef를 이용한 구조체 선언 - 한 눈에 끝내는 C언어 기초

push 함수

void push(Stack *stack, char *data) {
    Node *node = (Node*)malloc(sizeof(Node));
    strcpy(node->data, data);   // 각 노드는 데이터를 포함하고 있기 때문에 매개변수로 들어온 데이터 즉 문자열을 노드 안에 담을수있게 한다.
    node->next = stack->top;    // 현재 스택의 탑을 노드의 다음이 가르키게 한다.
    stack->top = node;  // 스택의 탑을 노드가 될 수 있게 한다.
}

strcpy() 은 str(=string), cpy(=copy)로 문자열을 복사하는 함수이다.

함수 원형은 char* strcpy(char* dest, const char* origin); 이다.

origin에 있는 문자열 전체를 dest로 복사를 하는 함수이다.

아래의 예제를 보자

char origin[] = "BlockDMask";  //"BlockDMask\\0" 이므로 size = 11;
char dest3[] = "STRCPY_EXAMPLE";  // size = 15;
strcpy(dest3, origin);
 
printf(" case3 before : %s\\n", dest3);
    
dest3[10] = 'y';    //'\\0' -> 'y'
printf(" case3 after  : %s\\n", dest3);

// case3 before : BlockMask
// case3 after : BlockMaskyPLE

복사를 할 때 메모리 상에서 ‘\0’까지 복사가 되기 때문에 dest3[10] 에서 '\\0' -> 'y' 로 변경해주지 않으면 ‘\0’ 까지밖에 인식하지 못하여 BlockMask 로 출력이 된다.

또는

char origin[] = "BlockDMask";
char dest2_1[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
char dest2_2[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    
strncpy(dest2_1, origin, sizeof(origin));
strncpy(dest2_2, origin, sizeof(origin) - 1);
 
printf(" case2_1 : %s\\n", dest2_1);
printf(" case2_2 : %s\\n", dest2_2);

// case2_1 : BlockMask
// case2_2 : BlockMaskaaaaaaaaaaaaaaaaaaa

이렇게 sizeof(origin) -1) 을 사용하면 된다.

[C언어/C++] strcpy, strncpy 함수(문자열 복사)에 대해서

내가 사용한 예제를 보면 typedef에서 data[100]으로 초기화하여 긴 문자열도 처리할 수 있게끔 해놓았기 때문에 문자 잘림 없이 잘 복사가 되는 것 같다.(추측)

getTop 함수

char* getTop(Stack *stack) {
    Node *top = stack->top; // 최상단 노드를 반환할 수 있게 한다.
    return top->data;  // top의 data를 반환한다.
}

pop 함수

char* pop(Stack *stack) {
    if (stack->top == NULL) {
        printf("스택 언더플로우가 발생했습니다.\\n");
        return NULL;
    }
    Node *node = stack->top;
    char *data = (char*)malloc(sizeof(char) * 100);
    strcpy(data, node->data);
    stack->top = node->next;
    free(node);
    return data;
}

pop 함수는 [C언어 포인터 기반 스택 알고리즘] 스택 삽입 및 삭제하기 를 참고하면 좋을 것 같다.

getPriority 함수

int getPriority(char *i) {
    if (!strcmp(i, "(")) return 0;  // 우선순위가 가장 낮음
    if (!strcmp(i, "+") || !strcmp(i, "-")) return 1;
    if (!strcmp(i, "*") || !strcmp(i, "/")) return 2;
    return 3;
}

0이면 우선순위가 가장 낮고, 수가 커질 수록 우선순위가 커진다.

transition 함수

// 후위표기법으로 변경하는 함수

/* s는 37 * 5라고 들어왔을 때 
 * "37", "*", "5" 라고 각 문자열로 본다는 뜻이다.
 * size는 각 들어오는 문자열의 사이즈이다. */
char* transition(Stack *stack, char **s, int size) {
    char res[1000] = "";
    for (int i = 0 ; i < size ; i++) {

        // 문자열이 연산자인지 체크한다.
        if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {

            // 자기보다 우선순위가 높은 것을 뽑는다.
            while (stack->top != NULL && getPriority(getTop(stack)) >= getPriority(s[i])) {
                // 자신보다 우선순위가 높은 것들 먼저 스택에서 뽑은 뒤에 뽑은 데이터를 res에 넣어준다.
                strcat(res, pop(stack));
                // 3 + 5가 들어오면 3 5 + 이렇게 띄어쓰기를 해준다.
                strcat(res, " ");
            }

						// stack에 넣어준다.
            push(stack, s[i]);

				// 문자열이 "("인지 체크한다.
        } else if (!strcmp(s[i], "(")) {
            push(stack, s[i]);

				// 문자열이 ")"인지 체크한다.
        } else if (!strcmp(s[i], ")")) {

						// ")"이 나왔다면 "("가 나올때까지 스택에서 뽑아서 결과 배열(res)에 넣어준다.
            while (strcmp(getTop(stack), "(")) {
                strcat(res, pop(stack));
                strcat(res, " ");
            }
						
						// "("도 stack에서 나올 수 있게 한다.
            pop(stack);

        } else {
            // 일반 숫자인 경우 바로 출력한다.
            strcat(res, s[i]);
            strcat(res, " ");
        }
    }

    // 스택에 남아있는 문자가 있다면 다 꺼내준다.
    while (stack->top != NULL) {
        strcat(res, pop(stack));
        strcat(res, " ");
    }

    return res;
}

이번에는 모르는 함수가 두 개가 나왔다.

• strcmp(string1, string2)
  • 원형은 int strcmp( const char *string1, const char *string2); 이다.
  • string1과 string2 두 문자열을 비교한다.
    • 리턴값이 -1 일 때 : 두 문자열을 비교하여, 틀린 첫번째 문자가 string1이 더 작을 때 -1을 리턴한다.
    • 리턴값이 0일 때 : 두 문자열이 같다.
    • 리턴값이 1일 때 : 두 문자열을 비교하여, 틀린 첫번째 문자가 string1이 더 클 때 1을 리턴한다.
  • 위의 코드 transition에서 왜 !strcmp(string1, string2) 를 썼을까에 대한 의문이 들었다.
    • 이것에 대한 해답은 아스키 코드 값에 있다.
    • C언어에서 0은 false값이므로 string1와 string2가 같아서 리턴 0을 해준다면 false 값으로 if문 안으로 들어갈 수 있는 것이다.

    } else if (!strcmp(s[i], ")")) {
    		// ")"이 나왔다면 "("가 나올때까지 스택에서 뽑아서 결과 배열(res)에 넣어준다.
        while (strcmp(getTop(stack), "(")) {
            strcat(res, pop(stack));
            strcat(res, " ");
        }
    		
    		// "("도 stack에서 나올 수 있게 한다.
        pop(stack);
    }
    

    • 그럼 이 코드에서는 strcmp 를 썼으므로 0이 아닌 값은 모두 true로 인식하기 때문에 괄호를 빼는 작업을 했다는 것을 알 수 있다.

[C언어&C++] strcmp, strncmp 함수(문자열 비교 함수)

• strcat(dest, origin)
  • 원형은 char* strcat(char* dest, const char* origin); 이다.
  • origin에 있는 문자열을 dest 뒤쪽에 이어 붙이는 함수 이다.
  • dest 문자열 끝에 있는 ‘\0’은 사라지고 그 위치에 바로 붙는 것이 특징이다.

[C언어/C++] strcat, strncat 문자열 연결 함수에 대해서

calculate 함수

void calculate(Stack *stack, char **s, int size) {
    int x, y, z;
    for (int i = 0 ; i < size ; i++) {
        if (!strcmp(s[i], "+") || !strcmp(s[i], "-") || !strcmp(s[i], "*") || !strcmp(s[i], "/")) {
            x = atoi(pop(stack));
            y = atoi(pop(stack));

            // y가 더 먼저 들어간 문자이기 때문에 y가 먼저 들어가야 한다.
            if (!strcmp(s[i], "+")) {
                z = y + x;
            }
            if (!strcmp(s[i], "-")) {
                z = y - x;
            }
            if (!strcmp(s[i], "*")) {
                z = y * x;
            }
            if (!strcmp(s[i], "/")) {
                z = y / x;
            }
            char buffer[100];
            // 계산된 숫자의형태를 문자로 넣겠다는 것 이다.
            sprintf(buffer, "%d", z);
            // 그것을 다시 스택에 넣겠다는 것 이다.
            push(stack, buffer);
        } else {
            push(stack, s[i]);
        }
    }
    printf("%s\\n", pop(stack));
}

이번에도 모르는 함수가 두 개 나왔다.

• atoi(cStr)
  • 원형은 int atoi (const char* cStr); 이다.
  • 문자열을 정수 타입으로 바꿔주는 함수이다.
  • 이외에도
    • atof = char to double : 문자열을 실수 타입으로 바꿔준다.
    • atol = char to long int : 문자열을 long 정수 타입으로 바꿔준다.

[C언어/C++] atoi, atof, atol 함수 (char* to int)

• sprintf(str, "문자열");또는 sprintf(str, "%d", 10);
  • sprintf(str, "문자열"); 은 str 문자열에 “문자열”이 저장된다.
  • sprintf(str, "%d", 10); 은 str 문자열에 문자열 “10”이 저장된다.

[C/C++언어]sprintf 함수와 fprintf 함수 사용법, 원하는 출력을 다양한 서식으로 구성하고 문자열이나 파일로 저장하기. stdio.h 라이브러리

main 함수

int main(void) {
    Stack stack;
    stack.top = NULL;
    char a[100] = "( ( 3 + 4 ) * 5 ) - 5 * 7 * 5 - 5 * 10";  // 계산 수식
    int size = 1;   // 각 문자열의 개수

    for (int i = 0 ; i < strlen(a) ; i++) {
        if (a[i] == ' ') {
            size++;
        }
    }

    char *ptr = strtok(a, " "); // 띄어쓰기를 이용하여 토큰으로 만들어준다.
    char **input = (char**)malloc(sizeof(char*) * size);    // 후위표기법에 넣으려는 입력값

    for (int i = 0 ; i < size ; i++) {
        input[i] = (char*)malloc(sizeof(char) * 100);   // 각 문자열은 최대 100까지
    }

		// 띄어쓰기로 이루어진 각 문자열 배열 형태로 인풋에 담기게된다.
    for (int i = 0 ; i < size ; i++) {
        strcpy(input[i], ptr);  // 토큰으로 분리된 각 문자열 복사한다.
        ptr = strtok(NULL, " ");    // 그 다음 토큰을 확인한다.
    }

    char b[1000] = "";
    strcpy(b, transition(&stack, input, size));
    printf("후위 표기법 : %s\\n", b);

    size = 1;
    for (int i = 0 ; i < strlen(b) - 1 ; i++) {  // 마지막은 항상 공백이 들어가므로 1을 뺀다.
        if (b[i] == ' ') {
            size++;
        }
    }

    char *ptr2 = strtok(b, " ");

    for (int i = 0 ; i < size ; i++) {
        strcpy(input[i], ptr2);
        ptr2 = strtok(NULL, " ");
    }

    calculate(&stack, input, size);

    return 0;
}

이번에도 모르는 함수가 두 개 있었다.

• strlen(a)
  • 원형은 size_t strlen(const char* str); 이다.
  • C언어 문자열을 받아서 그것의 길이를 반환하는 함수인데 문자열의 끝을 알려주는 ‘\0’ 문자가 나올때까지의 문자들의 개수를 반환한다.
  • 그럼 strlen 과 sizeof 의 다른점은 무엇일까?
    • strlen 은 할당받은 메모리에 바인딩 된 문자열의 길이이며 NULL을 제외한다. NULL을 만나게 되면 strlen 은 NULL 전의 길이 값을 리턴한다.
    • sizeof 의 경우 데이터가 할당받은 메모리 바이트의 길이이다.
      • 기억을 더듬어보니 length를 구하는 함수를 몰라서 sizeof 로 값을 구한 뒤 int의 값을 또 구해서 length를 구했던 기억이 있다.

[C언어] strlen과 sizeof 차이

[C언어/C++] strlen 함수(문자열 길이)에 대해서

• strtok(str, delimiters)
  • 원형은 char* strtok(char* str, char* delimiters); 이다.
  • strtok의 함수의 이름은 string+tokenize라고 할 수 있으며 문자열을 토큰처럼 조각조각 내는 함수이다.
  • char* 타입의 문자열 str을 첫번째 매개변수로 받아서, 두번째 들어온 char* 타입의 구분자를 기준으로 문자열을 잘라서 포인터를 하나씩 반환한다.
  • 위의 main 함수에서는 띄어쓰기를 구분자로 토큰으로 만들어주었다.
  • strtok(NULL, " "); 함수를 써주면 다음 띄어쓰기만큼의 토큰을 만들어준다.
    • 문자열의 끝까지 탐색한다면 strtok 함수는 NULL을 반환하게 된다.

[C언어/C++] strtok 함수(문자열 자르기)에 대해서.

---

마치며..

코드가 길고 강사님이 치는 코드 스타일과 내가 치는 코드 스타일이 달라서 오타로 고생 많이 했던 강의였다.

함수를 찾아보면서 공부하는 것이 시간이 훨씬 많이 들기는 하지만 그래도 이해가 더 잘되는 것 같다.