[자료구조] 스택을 이용해 중위식을 후위식으로 변환하기

스택 응용 문제 중 가장 대표적인 문제가 중위식(Infix)를 후위식(Posfix)로 변환하는 것이다.

 

우선, 중위식과 후위식에 대해서 간단히 설명하겠다.

중위식(Infix)

• 우리가 일반적으로 사용하는 식의 형태
• 연산자가 두 피연산자의 가운데에 위치한다.
• ex) 2 + 3 * 5

 

후위식(Posfix) 

• 컴퓨터가 연산을 수행할 때 사용하는 식의 형태
• 연산자가 두 피연산자의 뒤에 위치한다.
• ex) 2 3 4 * +

 

 

우리는 중위식을 입력으로 받아 후위식으로 변환하는 코드를 작성해보겠다.

스택을 사용할 것이니 우선 스택 구조를 먼저 작성해준다.

#include<stdio.h>
#define MAX_SIZE 8
int top = -1;
int stack[MAX_SIZE];

int isEmpty(){
    if(top==-1)
        return 1;
    
    return 0;
}

int isFull(){
    if(top+1==MAX_SIZE)
        return 1;
    return 0;
}

void Push(int val){
    if(isFull()){
        printf("스택이 가득 차있습니다.\n");
        return;
    }
    stack[++top] = val;
}

int Pop(){
    if(isEmpty()){
        printf("스택이 비어있습니다.\n");
        return -1;
    }
    return stack[top--];
}

void showStack(){
    for (int i = 0; i <= top;i++)
        printf("%d ", stack[i]);
    printf("\n");
}


int main(void){
}

 

위 코드에서는 스택의 최대 사이즈를 8로 설정하였다.

그리고 배열 기반으로 스택을 구현한 모습이다.

 

 

중위식을 후위식으로 변경하기

중위식을 후위식으로 변경하기 위해서는 중위식의 값을 하나하나 토큰으로 나누어 각 토큰에 대해 상황에 맞게 처리를 진행한다.

• 토큰이 피연산자 :  바로 출력한다.
• 토큰이 연산자 : 스택에 이미 연산자가 존재한다면, 스택에 있는 연산자와 토큰의 연산자를 비교한다. 스택에 있는 연산자의 우선순위가 높을 경우 모두 Pop 연산 수행 , 그리고 해당 토큰을 Push하여 스택에 저장

토큰은 중위식을 처음부터 하나씩 순서대로 저장하게 된다.

토큰이 연산자인 경우에, 스택에 연산자가 없거나, 스택에 있는 연산자의 우선순위가 낮다면 바로 Push() 를 수행하면 된다.

 

 

위 사진을 보자. 

처음에 토큰에는 2 라는 값이 저장될 것이고, 2는 피연산자 이므로 바로 출력한다

두번째로, +는 연산자이다. 스택에 아무 값이 없으므로 스택에 Push() 한다.

세번째로, 3은 피연산자이므로 출력한다.

네번째로, x 는 연산자이다. 스택에 이미 존재하는 +와 비교했을 때 x 연산자가 우선순위가 더 높으므로 스택에 Push() 해주면 된다.

이와 같이 진행하면 된다.

6번째를 보면, 스택에 -와 x 가 존재하던 상황에서 - 연산자가 토큰으로 입력되었다.

이 경우에 스택에 있던 모든 값을 Pop() 하고 나서 - 연산자를 Push() 하는 것을 확인할 수 있다.

 

 

 

위 그림처럼 코드를 구현하기 위해 아래 두 개의 함수를 추가하겠다.

• InfixToPosfix (중위식을 후위식으로 변경하는 함수)
• priority (우선 순위를 나타내는 함수)

 

 

전체 코드

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 8
int top = -1;
int stack[MAX_SIZE];

int isEmpty(){
    if(top==-1)
        return 1;
    
    return 0;
}

int isFull(){
    if(top+1==MAX_SIZE)
        return 1;
    return 0;
}

void Push(int val){
    if(isFull()){
        printf("스택이 가득 차있습니다.\n");
        return;
    }
    stack[++top] = val;
}

int Pop(){
    if(isEmpty()){
        printf("스택이 비어있습니다.\n");
        return -1;
    }
    return stack[top--];
}

void showStack(){
    for (int i = 0; i <= top;i++)
        printf("%d ", stack[i]);
    printf("\n");
}

int priority(int token){
    if(token=='+' || token=='-'){
        return 1;
    }
    else if(token=='*' || token=='/'){
        return 2;
    }
    else{
        return 0;
    }
}

void InfixToPostfix(char arr[]){
    int len = strlen(arr);
    for (int i = 0; i < len; i++){
        int token = arr[i];
        switch(token){
            case '+':
            case '-':
            case '/':
            case '*':
                while(!isEmpty() && priority(token) <= priority(stack[top])){
                    printf("%c", Pop());
                }
                Push(token);
                break;
            case '(':
                Push(token);
                break;
            case ')':
                while (stack[top] != '('){
                    printf("%c", Pop());
                }
                Pop(); 
                break;
            default:
                printf("%c", token);
        }
    }

    while(!isEmpty())
        printf("%c", Pop());
}

int main(void){
    char arr[100]; 
    printf("변환할 중위식을 입력하세요 : ");
    scanf("%s", arr);
    InfixToPostfix(arr);
    return 0;
}

 

실행 결과

 

 

• priority 함수에서 '*' 연산자와 '/' 연산자의 우선순위가 제일 높으므로 2를 반환하도록 했다.
• 괄호는 왼쪽 괄호는 그대로 Push, 오른쪽 괄호가 나오면 왼쪽 괄호가 반환될때까지 Pop을 진행하면 된다.