[C Language] 후위표기법(reverse polish notation)을 이용한 계산기 만들기

계산기를 작성하는 프로그램을 만들어보자. reverse polish notation(후위 표기법이라고도 한다.)을 사용할 것이다.

 

---

reverse polish notation이란,
(1-2)*(4+5)
를
12-45+*
로 표기하는 것을 의미한다.

 

reverse polish notation을 사용하면 괄호에 영향을 받지 않고 정확하게 연산과정을 지켜가며 컴퓨터 내부연산을 통해 계산할 수 있다.

 

이 표기법과 스택 자료구조를 통해 일관되게 계산하는 프로그램을 만들 것이다.

---

프로그램의 구조를 다음과 같이 설계하자.

while(next operator or operand is not end-of-file indicator)
    if(number)
        push it
    else if(operator)
        pop operands
        do operation
        push result
    else if(newline)
        pop and print top of stack
    else
        error

external로 스택과 push, pop함수를 선언하여 main 함수 내에서 다루면 깔끔하게 프로그램을 만들 수 있을 것이다!

이대로 main 파일을 작성하면 아래와 같다.

#include <stdio.h>
#include <stdlib.h> // atof()사용

#define MAXOP 100 // operand, operator의 최대 사이즈
#define NUMBER '0' // 숫자가 발견됐다는 신호로

int getop(char []);
void push(double);
double pop(void);

int main(){
    int type;
    double op2;
    char s[MAXOP];

    while((type = getop(s)) != EOF){
        switch (type){
            case NUMBER:
                push(atof(s));
                break;
            case '+':
                push(pop() + pop());
                break;
            case '*':
                push(pop() * pop());
                break;
            case '-':
                op2 = pop();
                push(pop() - op2);
                break;
            case '/':
                op2 = pop();
                if(op2 != 0.0)
                    push(pop() / op2);
                else
                    printf("error : zero division\n");
                break;
            case '\n':
                printf("\t%.8g\n", pop());
                break;
            default:
                printf("error: unknown command %s\n", s);
                break;
        }
    }
    return 0;
}

+ *는 교환법칙이 성립하므로, 두가지 연산 모두 pop()으로 처리한다.
- /는 교환법칙이 성립하지 않으므로 op2로 먼저 하나를 꺼내서 연산한다.

 

이렇게 하는 이유는 push() 내부에 시퀀스 포인트가 없어서 pop() - pop()혹은 pop() / pop()에서 연산의 순서가 거꾸로 될 수도 있기 때문이다.

 

여기서 stack과 pop, push함수를 아래와 같이 정의할 수 있다.

#define MAXVAL 100

int sp = 0;
double val[MAXVAL];

void push(double f){
    if(sp < MAXVAL)
        val[sp++] = f;
    else
        printf("error : stack full\n");
}

double pop(void){
    if(sp > 0)
        return val[--sp];
    else{
        printf("error : stack empty\n");
        return 0.0;
    }
}

스택(sp)을 external하게 정의함으로써 pop과 push함수가 서로 공유할 수 있다.

 

main 파일에서 정의한 getop()함수를 정의하자.

#include <ctype.h>

int getch(void);
void ungetch(void);

// 다음 operator 혹은 operand를 받는다.
int getop(char s[]){
    int i, c;

    while((s[0] = c = getch()) == ' ' || c == '\t') ;

    s[1] = '\0';
    if(!isdigit(c) && c != '.') // 숫자가 아님
        return c;
    i = 0;
    if(isdigit(c)) // integer part
        while(isdigit(s[++i] = c = getch())) ;
    if(c == '.')
        while(isdigit(s[++i] = c = getch())) ;

    s[i] = '\0';
    if(c != EOF)
        ungetch(c);
    return NUMBER;    
}

아래는 getop에서 나온 getch()와 ungetch()를 정의한다.

getch()는 character하나를 받아오는 함수고, ungetch() 받아왔던 character를 다시 스택에 반환하는 함수이다.
스택에서 읽어온 데이터가 기대한 값이 아닐 때, 다시 반환하는 과정을 만들기 위해 존재하는 함수다.

#define BUFSIZE 100

char buf[BUFSIZE];
int bufp = 0;

// character 하나를 버퍼에서 받는다.
int getch(void){
    return (bufp > 0) ? buf[--bufp] : getchar();
}

// 버퍼에 character를 반납.
void ungetch(int c){
    if(bufp >= BUFSIZE)
        printf("ungetch : too many characters\n");
    else
        buf[bufp++] = c;
}