C로 스택을 활용한 계산기 구현해보기 (중위 표기법, 후위 표기법 뜻)

 

1. 중위 표기법과 후위 표기법 뜻

 

중위 표기법이란, 일반적으로 사람이 수식을 표기할 때 사용하는 표기 방법이다. 흔히 우리는 두 개의 피연산자가 있고 한 개의 연산자가 있을 때, 피연산자 사이에 연산자가 들어갈 수 있도록 표기를 한다. 그러나 컴퓨터가 좋아하는 방식은 후위 표기법이다. 후위 표기법은 연산자가 뒤쪽에 위치한다. 

 

중위 표기법: 7 * 9 + 2
후위 표기법: 7 9 * 2 +

 

2. 기본적인 구조체와 push, pop 함수 만들기

 

#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 안에 담아줌
    node -> next = stack -> top; // 현재 스택의 top을 node의 next로
    stack -> top = node; // top을 지금 노드로 바꿔줌
}

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

char pop(Stack *stack) {
    if (stack -> top == NULL)
    {
        printf("스택 언더플로우");
    }
    Node *node = stack -> top;
    char *data = (Node*) malloc(sizeof(Node));
    strcpy(data, node -> data); // 현재 스택에 있던 데이터를 반환하도록 만들고, 

    stack -> top = node -> next; // 기존 스택의 top에서 하나를 뽑도록 한다.
    free(node);
    return data;
}

 

Node 구조체에는 숫자와 문자열 등이 들어가기 때문에 하나의 문자열을 담을 수 있도록 하고, 다음 노드를 가리킬 수 있도록 한다. push() 함수에는 매개변수로 들어온 문자열을 node에 담아준 수, 현재 스택의 top을 node의 next로 바꾼 후 top을 지금 노드로 바꿔준다.  pop() 함수에서는 현재 스택에 있던 데이터를 반환하도록 만들고, 기존 스택의 top을 메모리에서 지워준다. 마지막으로 getTop() 함수에서는 스택의 top 데이터를 반환하도록 한다.

 

3. 우선순위 함수 만들기

 

중위 표기법을 후위 표기법으로 바꾸는 방법:

(1) 피연산자가 들어오면 바로 출력한다.

(2) 연산자가 들어오면 자기보다 우선순위가 높거나 같은 것들을 빼고 자신을 스택에 담는다. 

(3) 여는 괄호 '('가 나오면 무조건 스택에 담는다.

(4) 닫는 괄호 ')'가 나오면 '('를 만날 때까지 스택에서 출력한다.

 

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

 

strcmp 함수는 string compare에서 따 온 이름이고, 각 문자를 아스키코드 값으로 비교해서 음수, 양수, 0으로 반환하는 함수다. 특정한 문자가 들어왔을 때 해당 문자의 우선순위를 숫자로 반환하는 함수 getPriority() 함수를 만들어준다. 

 

strcmp(str1, str2)
str1 < str2 : 음수 반환
str1 < str2 : 양수 반환
str1 == str2 : 0 반환

 

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 && getPrioity(getTop(stack)) >= getPriority(s[i])) {
                strcat(res, pop(stack));
                strcat(res, " ");
            }
        }
        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, " ");
    }
}

 

그리고 후위 표기법으로 만들어주는 변환 함수를 만들어준다. 매개변수로 3가지가 char **s 는 입력된 문자열을 의미한다. 예를 들어 3 + 5라는 문자열이 들어온다면, "3", "+", "5" 이렇게 3개의 문자열로 구성된 배열로 나누어 받겠다는 의미다. size는 각 문자열의 개수다.

 

for문에서는 들어온 문자열의 배열을 한 개씩 살펴보면서, 먼저 해당 문자열이 +, -, *, / 연산자라면 이것보다 연산자 우선순위가 높은 것들을 다 stack에서 뽑은 뒤에 자신을 스택에 넣는다. res는 후위 표기법으로 바꾼 문자열을 담을 변수다. 스택에서 뽑은 데이터를 넣고, 그 뒤에 한 칸 띄워 준다. 3+5가 들어오면, 3 5 + 이렇게 res에 들어간다. strcat 함수는 문자열을 이어붙이는 함수다.

 

strcat(기존 문자열 dest, 붙일 문자열 origin)
dest 문자열 끝을 가리키는 '\0'는 사라지고, 그 위치에 바로 origin 문자열이 바로 붙는다.

 

두 번째 조건으로는 여는 문자열 '('이 나오면 스택에 바로 추가한다. 또 세 번째 조건으로는 닫는 문자열 ')'이 나오면 여는 괄호 '('가 나올 때까지 스택에서 뽑아서 결과 배열에 담아준다. 이후에 다시 pop을 해서 여는 괄호 또한 나오도록 해 준다. 마지막 조건으로 일반 숫자가 들어올 경우, 바로 res 배열에 추가해 준다. 

 

    while (stack -> top != NULL) {
        strcat(res, pop(stack));
        strcat(res, " ");
    }

 

마지막으로 스택에 남아 있는 문자열은 다 뽑아서 res에 추가해준다. 결과적으로 res를 반환해서, 후위 표기법을 반환해준다. 

 

4. 후위 표기법을 계산하는 방법

 

- 피연산자가 들어오면 스택에 담는다.

- 연산자를 만나면 스택에서 두 개의 연산자를 꺼내서 연산한 뒤에, 다시 그 결과를 스택에 담는다.

- 연산을 마친 뒤에 스택에 남아있는 하나의 피연산자가 연산 수행 결과다. 

 

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("%d\n", pop(stack));
}

 

후위 표기법을 계산할 때도 스택이 하나 필요하다. 그리고 입력될 문자열 배열이 들어온다. 예를 들어 3 5 + 라면 "3", "5", "+" 이렇게 배열의 형태로 들어온다. 함수 내에서 계산할 변수를 3개 만들어 주고, 들어온 문자 배열을 for문을 돌면서 조건에 따라 연산을 하고 스택에 넣어주는 연산을 반복한다. 연산자를 만날 때는 스택에서 2개를 뽑아서, 그것을 계산한 결과를 스택에 다시 넣는다. atoi 함수는 문자열을 숫자로, sprintf 함수는 숫자를 문자의 형태로 바꿔 주는 함수다. 

 

atoi(문자열)
ASCII to integer 라는 뜻. char[] 문자열을 integer로 타입 변경한다.

buffer
sprintf(buffer, "형식", 문자열)
단점은 buffer의 사이즈보다 큰 문자열을 받게 되면 오버플로우가 생길 수 있다.

 

x가 먼저 스택에 들어가고, y가 나중에 들어간 원소다. 스택 원리상 그러면 y가 먼저 나와서 x와 연산을 수행하는 결과로 z를 구한다. 다시 말해 y + x 이런 식으로 y가 먼저 나와야 한다. 모든 과정을 반복하면 최종 결과는 스택에 마지막으로 담긴 값이 된다. 

 

5. 계산기 실행하기

 

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

먼저 띄어쓰기로 분리된 계산식을 각각의 문자열 배열 형태로 만들어준다. 각각의 문자열의 수를 세어서 size를 구한다. 우리가 계산하고 싶은 계산식 문자열이 띄어쓰기로 분리되어 있는 형태이기 때문에 띄어쓰기의 숫자 + 1 만큼이 된다.

그리고 각각의 문자열을 strtok 함수를 이용해 " " 토큰으로 분리한다. input에다가 후위 표기법으로 변환한 입력값을 넣기 위해 메모리 할당을 해 주고, 다시 for문으로 각각의 문자열을 최대 100까지 크기만큼 할당해준다. for문으로 input에 토큰으로 분리된 각 문자열을 input에다가 넣는다. 동시에 띄어쓰기도 하나씩 포함해준다. 그러면 띄어쓰기로 분리된 각 문자열 배열이 input에 담기게 된다. 결과는 3 4 + 5 * 5 7 * 5 * - 5 10 * - 다.

 

후위표기법으로 바뀐 결과를 다시 개수를 구하는데 이유는 후위표기법으로 바꿀 때 마지막에 항상 공백이 들어가기 때문이다. for문으로 돌면서 사이즈를 구하고, 다시 토큰으로 분리해 input에다가 넣는다. 만들어진 input과 size를 이용하여 연산을 수행한다. 

 

이해 갈 듯 말 듯 돌아버리겠다;