두 자리 이상인 수의 연산이 가능한 계산기 구현 - 1 (infix to postfix 변환))

복잡한 연산이 가능한 계산기

지난 학기 과제로 했던 내용입니다. 도움이 되길 바랍니다.

1.

.

만들고 싶은 계산기는 45+9 또는 7*3과 같은 간단한 계산이 아니라 다음과 같은 식을 입력했을 때 답을 얻어낼 수 있는 계산기입니다.

수식을 입력하세요 : 5*(15+(2*5-3)*(54/2))*123-30*50/1500
결과값 : 125459

위의 계산을 자료구조의 한 종류인 stack을 응용하여 만들어보도록 하겠습니다.

2.

두 가지의 큰 틀로 나뉩니다.

1. stack을 이용하여 사용자에게 입력받은 infix를 postfix로 변환한다.
2. stack을 이용하여 postfix로 변환된 수식을 계산한다.

infix를 postfix로 바꾸는 과정이 postfix를 계산하는 과정보다 비교적 더 어렵습니다. postfix로 변환된 수식을 계산하는 코드를 먼저 이해하셔도 무방합니다.

infix를 postfix로 바꾸는 이유는 postfix가 우리가 코드를 짜는 입장에서 stack을 이용하여 계산하기에 좋은 표기식이기 때문입니다.

3. infix를 postfix로 바꾸는 함수

void infix_to_postfix(char *infix, char *postfix){
    StackType s;
    init(&s);
    while(*infix!='\0'){
        if(*infix=='('){
            push(&s, *infix);
            infix++;
        }
        else if(*infix == ')'){
            while(peek(&s)!='('{
                *postfix++ = pop(&s);
                *postfix++ = ' ';
            }
            pop(&s);
            infix++;
        }
        else if(*infix=='+'||*infix=='-'||*infix=='*'||*infix=='/'){
            while(!is_empty(&s)&&(prec(*infix)<=prec(peek(&s)))){
                *postfix++ = pop(&s);
                *postfix++ = ' ';
            }
            push(&s, *infix);
            infix++;
        }
        else if(*infix>='0'&&*infix<='9'){
            do{
                *postfix++ = *infix++;
            }while((*infix>='0' && *infix<='9'));
            *postfix++ = ' ';
        }
        else
            isfix++;
    }
    while(!is_empty(&s)){
        *postfix++ = pop(&s);
        *postfix++ = ' ';
    }
    postfix--;
    *postfix = '\0';
}

함수를 설명해보겠습니다. 먼저 Stack을 선언하고 초기화시킵니다.
StackType 코드는 다음과 같습니다.

typedef int element
typedef struct{
    element stack[MAX_STACK_SIZE];
    int top;
}StackType;

init함수는 다음과 같습니다.

void init(StackType *s){
    s->top=-1;
}

4.

그리고 반복문을 시작합니다. 이 반복문은 infix 수식이 끝날 때까지 반복하므로 조건은 null을 만날 때까지입니다.
반복문 안에서 if문이 시작됩니다. 먼저 왼쪽 괄호를 만난 경우, 괄호를 push함수를 이용하여 stack에 넣습니다. 그리고 다음 문자로 이동합니다. push함수는 다음과 같습니다.

void push(StackType *s, element item){
    if(is_full(s)){
        fprintf(stderr, "스택 포화 에러\n");
        return;
    }
    else s->stack[++(s->top)]=item;
}

---

다음 조건입니다. 왼쪽 괄호가 아닌 오른쪽 괄호를 만난 경우입니다. 수식이 잘못된 것이 아니라면 오른쪽 괄호를 만났다는 이야기는 그 전에 왼쪽 괄호를 만났겠죠? 그러면 stack에 왼쪽 괄호가 들어가있고, 오른쪽 괄호를 만날 때까지의 숫자와 연산자가 들어가 있을겁니다.
오른쪽 괄호를 만났으므로 먼저 처리해야할 식 하나가 생겼습니다. 따라서 stack에서 왼쪽 괄호를 만날 때까지 숫자와 연산자를 꺼내어 postfix배열에 넣습니다. 그 과정에서 peek함수와 pop함수가 사용되었는데요. 각 함수는 다음과 같습니다.

element peek(StackType *s){
    if(is_empty(s)){
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->stack[s->top];
}

element pop(StackType *s){
    if(is_empty(s)){
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
    }
    else return s->stack[(s->top)--];
}

---

다음 조건입니다. 왼쪽 괄호, 오른쪽 괄호가 아닌 연산자를 만난 경우입니다. 먼저 prec함수를 살펴보겠습니다.

int prec(char op){
    switch(op){
        case '(': case ')': return 0;
        case '+': case '-': return 1;
        case '*': case '/': return 2;
    }
    return -1;
}

prec함수는 보시다시피 각 연산자와 괄호에 따라 return되는 값이 다릅니다. return되는 값은 우선순위를 의미합니다. 우선순위를 알아야 하는 이유는 infix는 * , / 같은 연산자가 뒤에 있어도 먼저 계산하지만 postfix는 순서대로 계산할 뿐이죠. 그래서 원래의 식에 맞게 계산할 수 있도록 해야하기 때문입니다.

조건에서 나타나 있는 것처럼, 조건안의 반복문에서 stack의 상태와, stack 최상위층의 문자, infix배열의 문자의 우선순위를 계속 비교합니다. stack이 비어있지않고, stack 최상위층의 문자가 infix배열에서 만난 문자보다 우선순위가 크거나 같으면 최상위층에 있는 문자가 먼저 와야겠죠? stack에 있는 문자를 pop시켜 postfix 배열에 넣습니다.

---

그 다음 코드를 보시면 아주 중요한 개념이 있습니다.

*postfix++ = ' ';

바로 postfix배열에 공백을 넣는 것입니다. 공백의 역할은 아주 중요합니다. 예를 들어 설명해보면, 우리는 두 자리 이상의 연산이 가능한 계산기를 만드는 건데 다음의 수식을 보면

infix -> 189 + 3 * 5
postfix -> 35189*+

infix를 postfix로 어찌어찌 바꿔서 35100*+라는 식을 얻었다고 합시다. 그러면 이 식을 어떻게 계산해야 할까요? 3*5+189을 하면 참 좋겠지만, 35*1+89을 해야할 지 351*8+9를 하라는 건지 사람이든 컴퓨터든 35100*+라는 식을 봤을때 햇갈릴 수 밖에 없습니다. 물론 조건이 한 자리의 수들의 계산이 가능한 계산기를 만드는 거라면 문제없지만 우리는 두 자리 이상의 수들을 계산하는 계산기를 만들고 싶은거니까요.

이 문제를 해결하는 방법은 여러 방법이 있을 수 있습니다. 저에게 가장 와닿고 이해하기 쉬웠던 것은 저렇게 공백을 넣어서 구분하는 방법이었습니다. postfix의 각 숫자 사이에 공백을 넣으면 몇 자리 수가 와도 구분할 수 있습니다.

postfix -> 3 5 189 * +

이런식으로 구분할 수 있습니다. 누가 봐도 3*5+189를 하라는 것을 알 수 있고 코드를 짤 때는 공백을 기준으로 구분하면 되겠죠. 자세한 설명은 postfix로 변환된 식을 계산하는 과정에서 설명하겠습니다.

---

다시 조건으로 돌아와서, 우선 순위가 높은 문자를 postfix에 모두 넣고 반복문이 끝나면 우선순위가 낮은 문자를 넣어주면 됩니다. 그리고 infix배열의 다음 문자로 이동하면 되죠.

다음 조건은 0부터 9까지의 숫자를 만났을 때입니다. 두 자리 이상일 수 있으므로 반복문으로 구현하여 각 인덱스의 수를 차례대로 옮깁니다. 이 때 역시 반복문이 끝나면, 즉, 두 자리든 한 자리든 몇 자리든 하나의 수가 끝나면 공백을 넣어줍니다.

---

마지막 조건입니다. 위의 조건을 모두 만족하지 않는 경우에는 그냥 다음칸으로 이동합니다.

5.

하나의 커다란 반복문이 끝났습니다. 다음 과정은 stack에 남아있는 것들을 모두 꺼내는 것입니다. is_empty함수는 다음과 같습니다.

is_empty(StackType *s){
    return (s->top==-1);
}

stack에 남아있는 것들은 연산자들일 겁니다. 그래서 각 연산자 하나를 postfix에 넣을 때마다 공백도 넣어줍니다. 그러면 마지막에 공백이 남아있기 때문에 주소를 한 칸 앞으로 이동시키고 공백을 null값으로 바꾸어 배열을 끝내는 겁니다.

---

이렇게 infix를 postfix로 바꾸는 함수를 모두 살펴보았습니다. 글이 너무 길어져 다음 중요한 과정인 postfix로 변환된 수식을 계산하는 과정은 따로 작성하도록 하겠습니다. 감사합니다.