[Data Structure] #2-6 중위 표기법을 후위 표기법으로 변환하기

중위 표기법(Infix)를 후위 표기법(Postfix)로 변환하기 (스택 응용)

 이전 포스트에서 사람들은 중위 표기법을 쓰고 컴퓨터 컴파일러는 후위 표기법을 쓴다고 이야기 한 바 있다. 물론 컴파일러가 후위 표기법을 쓸 때의 이익도 함께 이야기했다. 그렇다면 우리 프로그래머는 사람들이 입력하는 중위 표기법을 후위 표기법으로 변환해야 할 필요가 있다. 

 이 변환작업에도 스택이 사용된다. 왜 그럴까? 바로 연산자가 피연산자보다 나중에 계산되기 때문이다. 예를 들어 a+b 라는 중위 표기식이 입력값으로 들어왔을 때 피연산자인 a는 곧바로 출력하면 된다. 그러나 연산자 +는 후위 표기법에 따라 피연산자 b보다 뒤에 나와야 한다. 그럼 이 +를 어디에 두어야 할까? 바로 스택이다. 

 스택에 두는 이유에 대해서 조금 더 자세히 들어가보자. a-b*c 라는 입력값이 들어온 경우 a는 출력하면 되고, -는 저장한다. 다시 b는 출력시키고 *는 어떻게 해야할까. 다시 그 위에 저장해야 한다. 그리고 c는 출력한다. 그럼 이제 저장된 - 와 * 중 무엇을 먼저 출력해야 할까. 기본적으로 가장 나중에 들어온 연산자가 가장 먼저 출력되어야 한다.(LIFO) 그러므로 스택을 사용하는 것이다.

 그런데 여기에도 문제가 좀 있다. a*b-c의 경우에는 위의 예처럼 했다가는 b-c가 먼저 계산되는 것처럼 출력된다. 그래서 이 문제를 해결하기 위해서 연산자에 우선순위를 두게 된다. 밑의 코드에서 prec()라는 메서드로 정의해두었다.

 연산자 우선순위는 괄호 (, ) 가 제일 낮고 덧셈과 뺄셈 그리고 곱셈과 나눗셈 순서로 우선순위가 높아진다. 우선 순위가 높을 수록 빨리 스택을 빠져나오게 되는 것이다. 이때 괄호는 특이한 경우다. 왼쪽 괄호 ( 가 나올 경우 무조건 스택에 집어넣는다. 그 후에 오른쪽 괄호 )가 나오면 스택에서 왼쪽 괄호를 찾을 때까지 스택을 파내야 한다. 왜냐하면 괄호는 무조건 먼저 계산이기 때문이다.

 코드를 보자.

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

#define MAX_SIZE_STACK 100
#define FALSE 0
#define TRUE 0

// 중위 표기법을 후위 표기법으로 변환한다
// 피연산자는 무조건 출력한다
// 연산자의 경우에는 우선순위에 따라 결정한다

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

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

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

int is_full(StackType *s){
    return s->top == MAX_SIZE_STACK-1;
}

void push(StackType *s, element item){
    if (is_full(s))
        exit(1);
    s->stack[++(s->top)] = item;
}

element pop(StackType *s){
    if (is_empty(s))
        exit(1) ;
    return s->stack[(s->top)--];
}

element peek(StackType *s){
    if (is_empty(s))
        exit(1);
    return s->stack[s->top];
}

// 우선순위 반환 메서드
int prec(char op){
    switch (op) {
        case '(': case ')': return 0;
        case '+': case '-': return 1;
        case '*': case '/': return 2;
    }
    return -1;
}

void infix_to_postfix(char exp[]){
    int i;
    char ch, top_op;
    int len = (int) strlen(exp);
    
    StackType s;
    init(&s);
    
    for (i=0; i<len; i++) {
        ch = (int) exp[i];
        
        switch (ch) {
            // 연산자일 경우
            case '+': case '-': case '*': case '/':
                // 자신보다 우선 순위가 높은 것이
                // Stack에 계실 경우 어서 빼드린다
                while (!is_empty(&s) && prec(peek(&s)) >= prec(ch)) {
                    top_op = pop(&s);
                    printf("%c ", top_op);
                }
                push(&s, ch);
                break;
                
            // 괄호의 경우
            case '(':
                push(&s, ch);
                break;
            case ')':
                top_op = pop(&s);
                while (top_op != '(') {
                    printf("%c ", top_op);
                    top_op = pop(&s);
                }
                break;
                
            // 피연산자일 경우
            default:
                printf("%c ",ch);
                break;
        }
    }
    
    while (!is_empty(&s)) {
        printf("%c ",pop(&s));
    }
}

int main(){
    // a*b+c -> ab*c+
    infix_to_postfix("a*b+c");
    printf("\n");
    return 0;
}

 이때 핵심은 우선 순위가 높은 연산자가 스택에 '계실' 경우에는 어서 어서 빼드려야 한다는 점이다. 또한 우선순위가 같더라도 먼저 스택에 와 있었으니 먼저 빼준다는 것만 기억하면 그리 어렵지 않다.