[자료구조] 스택을 활용해서 두 자리 수 이상의 연산이 가능한 계산기 만들기(C언어)

스택으로 계산기를 구현하려면 아래와 같은 과정을 거쳐야 한다.

1. 중위 표기법을 모두 후위 표기법으로 바꾼다.
2. 후위 표기법으로 바뀐 식을 스택에 넣어준다.
3. 스택에 있는 값들을 특정 규칙에 따라 연산한다.

중위 표기법과 후위 표기법에 대한 내용은 위키 문서를 참조하기를 바란다. 이해를 돕기 위해서 후위 표기법을 가장 잘 설명한 블로그 주소도 남긴다.

 

주로 스택은 구제체 안에 배열을 선언한 상태로 사용한다. 아래는 스택을 구성하는 여러 기능들을 구현해 보았다. 이들 모두 계산기 구현에 중요한 역할을 하기 때문에 반드시 알고 넘어가야 한다.  

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100
typedef struct Stack { // 스택 구조체
    int data[MAX_LEN];
    int top;
} Stack;
void initStack(Stack* stack) { // 스택을 초기화 해주는 함수
    stack->top = -1;
}
int isempty(Stack* stack) {
    return (stack->top == -1);
}
void push(Stack* stack, int data) { // 스택에 새로운 데이터를 삽입하는 함수
    stack->data[++(stack->top)] = data;
}
int pop(Stack* stack) { // 스택의 맨 꼭대기 값을 스택에서 지우면서 반환하는 함수
    if (stack->top == -1) {
        puts("Stack is empty");
        exit(1);
    }
    return stack->data[(stack->top)--];
}
int peek(Stack* stack) { // 스택의 맨 꼭대기 값을 알려주는 함수
    return stack->data[stack->top];
}
void printStackContents(Stack* stack) { // 후위 표기법이 잘 저장되었는지 확인하게 해주는 함수
    for (int i = 0; i < stack->top; i++)
    {
        printf("%d", stack->data[i]);
    }
    puts("");
}

 

---

우리가 만들고자 하는 프로그램은 두 자리 이상의 연산도 가능한 계산기이다. 하지만 그냥 배열에 값들을 넣어주면 한 자리 연산만 가능하다. 따라서 후위 표기법으로 저장할 때 숫자와 연산자 사이에 공백을 넣어준다.  (예시 : 12 34 -)

 

이후에 중위 표기법을 후위 표기법으로 바꾸는 함수와 연산자들의 우선순위를 나타내주는 함수이다.

int priority(char c) { // 연산자를 만났을 때 우선순위 반환 함수
    switch (c) {
    case '(': case ')': return 0;
    case '+': case '-': return 1;
    case '*': case '/': return 2;
    }
}
char* infix_to_postfix(char string[]) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    initStack(stack);
    char* pf_str = (char*)malloc(sizeof(char) * MAX_LEN); // 후위 표기법으로 전환될 문자를 저장하는 배열
    int pf_idx = 0; // 후위 표기법 저장 배열의 인덱스 위치
    for (int str_idx = 0; str_idx < strlen(string); str_idx++)
    {
        char target = string[str_idx];
        if ('0' <= target && target <= '9') {
            while ('0' <= target && target <= '9') {
                pf_str[pf_idx++] = target;
                target = string[++str_idx];
            }
            str_idx--;
            pf_str[pf_idx++] = ' ';
        }
        else if (target == '+' || target == '-' || target == '*' || target == '/') {
            while (!isempty(stack) && (priority(target) <= priority(peek(stack)))) {
                pf_str[pf_idx++] = pop(stack);
                pf_str[pf_idx++] = ' ';
            }
            push(stack, target);
        }
        else if (target == '(') {
            push(stack, target);
        }
        else if (target == ')') {
            char buf = pop(stack);
            while (buf != '(') {
                pf_str[pf_idx++] = buf;
                pf_str[pf_idx++] = ' ';
                buf = pop(stack);
            }
        }
    }

    while (!isempty(stack)) {
        pf_str[pf_idx++] = pop(stack);
        pf_str[pf_idx++] = ' ';
    }

    pf_str[--pf_idx] = '\0';
    return pf_str;
}

 

---

 

그리고 변환된 후위 연산자 배열을 가지고 연산을 수행해 주는 함수와 이 함수에 이용되는 문자열 -> 자연수 변환 함수이다.

 

int change(char string[], int* _idx) {
    int idx = *_idx;
    int result;
    int i;
    char tmp[MAX_LEN];
    for (i = 0; string[i + idx] != ' '; i++) {
        tmp[i] = string[i + idx];
    }
    *_idx = i + idx;
    return atoi(tmp);
}
int calc_pf(char pf[]) {
    int num_first = 0, num_last = 0;
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    initStack(stack);
    int len = strlen(pf);
    for (int i = 0; pf[i]!='\0'; i++)
    {
        if (pf[i] == ' ') {
            i++;
        }
        char target = pf[i];   
        if (target != '+' && target != '-' && target != '*' && target != '/') {
            push(stack, change(pf, &i));
        }
        else {
            num_last = pop(stack);
            num_first = pop(stack);
            switch (target) {
            case '+': push(stack, num_first + num_last); break;
            case '-': push(stack, num_first - num_last); break;
            case '*': push(stack, num_first * num_last); break;
            case '/': push(stack, num_first / num_last); break;
            }
        }
    }
    return pop(stack);
}

 

---

 

마지막으로 나래와 같은 main 함수를 넣어줌으로써 결과물을 확인한다.

int main() {
    char arr[MAX_LEN];
    printf("Enter a equation : ");
    fgets(arr, sizeof(arr), stdin);
    arr[strlen(arr) - 1] = 0;
    char* pf = infix_to_postfix(arr);
    printf("postfix : %s\n", pf);
    printf("%d", calc_pf(pf));
    return 0;
}