20. 중위표기 후위표기 변환

중위 표기법으로 된 수식을 후위 표기법 수식으로 변환하는 과정은 Stack을 이용하여 변환한다.

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

#define MAX_STACK_SIZE 100
typedef struct Stack{
    char Items[MAX_STACK_SIZE];
    int top;
}Stack;

// Stack 함수
void push(Stack  *s, char item){
    if(s->top >= MAX_STACK_SIZE - 1){
        printf("Stack Overflow\n");
        exit(1);
    }
    s->Items[++(s->top)] = item;
}
char pop(Stack *s){
    if(s->top == -1){
        printf("Stack Underflow\n");
        exit(1);
    }
    return s->Items[(s->top)--];
}
char peek(Stack *s){
    if(s->top == -1){
        printf("Stack Underflow\n");
        exit(1);
    }
    return s->Items[(s->top)];
}
int is_Empty(Stack *s){
    return (s->top <= -1);
}

// 우선순위 반환 함수
int get_priority(char op){
    switch(op){
        case '(': return 0;
        case '+': case '-': return 1;
        case '*': case '/': case '%': return 2;
        case '^': return 3;
        default: return -1;
    }
}

void infix_to_postfix(char *infix, char *postfix){
    Stack s;
    s.top = -1;
    int i, j;
    char token, top_token;
    
    for(i=0,j=0; infix[i] != '\0'; i++){
        token = infix[i];
        switch (token){
            case '(': 
                push(&s, token); break;
            case ')':
                while(!is_Empty(&s) & peek(&s) != '(')
                    postfix[j++] = pop(&s);
                if(is_Empty(&s)){
                    printf("Invalid Expression1");
                    exit(1);
                }
                pop(&s);
                break;
            case '+': case '-': case '*': case '/': case '%': case '^': 
                while(!is_Empty(&s) && get_priority(token) <= get_priority(peek(&s))) 
                    postfix[j++] = pop(&s);
                push(&s, token);
                break;
            default :
                if(token >= '0' && token <= '9')
                    postfix[j++] = token;
                else {
                    printf("Invaild Expression2");
                    exit(1);
                }
        }
    }
    while(!is_Empty(&s)){
        top_token = pop(&s);
        if(top_token == '('){
            printf("Invaild Expression3");
            exit(1);
        }
        postfix[j++] = top_token;
    }
    postfix[j] = '\0';
}

int main()
{
    char infix[MAX_STACK_SIZE], postfix[MAX_STACK_SIZE];
    
    printf("수식 입력 : ");
    fgets(infix, MAX_STACK_SIZE, stdin);
    infix[strlen(infix) - 1] = '\0';
    infix_to_postfix(infix, postfix);
    printf("후위 수식 : %s\n", postfix);
    
    return 0;
}

Stack 함수는 Push, Pop 이외에도 가장 위의 값을 반환하는 peek 함수를 추가하였다.

get_priority() 함수는 우선순위를 설정, 반환하는 것으로 위 함수의 리턴값을 변경하여 우선순위를 바꿀 수 있다.

infix_to_postfix() 함수는 중위수식을 후위 수식으로 변환하는 함수이다. 수식을 보고 연산자라면 자신의 우선순위와 스택 제일 위의 우선순위를 비교하여 스택에 넣거나 스택 안에 있는 것을 꺼낸다. 여는 괄호라면 무조건 스택에 넣고, 닫는 괄호라면 여는 괄호가 나올 때까지 연산자를 스택에서 꺼낸다. 연산자가 아닌 피연산자라면 그냥 출력한다. 중위 수식의 끝에 도달하면 스택에 들어있는 모든 연산자를 꺼낸다. 그럼 후위 수식으로의 변환이 완료된다.