[자료구조][C언어]스택이란?(5)_후위표기식 만들기

저번 자료구조 시간에서 스택을 이용해서 후위 표기식을 계산하는 알고리즘을 C언어로 구현해보는 시간을 가졌었다. 이번 시간에는 스택을 이용해서 중위  표기식을 후위 표기식으로 만드는 알고리즘에 대해서 다루어 보도록 할 예정이다.

 

스택의 활용_3 후위표기식 만들기

 

배경지식

 

저번 시간에 다루었던 중위 표기식, 후위 표기식에 관한 지식을 간단하게 정리하자면

 

중위 표기식은 두 피연산자 사이에 연산자를 표기하는 방식이며,

후위 표기식은 피연산자를 먼저 표기한 뒤, 피연산자를 표기하는 방식이다.

 

기억이 잘 안 나거나 더 자세히 알아보고 싶으면 아래의 글의 배경지식 부분을 참고하길 바란다.

 

https://all4null.tistory.com/7

[자료구조][C언어]스택이란?(4)_후위 표기식의 계산

 

후위 표기식을 만드는 알고리즘에 대해 알아보도록 하겠다.

 

일단, 입력으로는 괄호로 우선순위가 잘 정리된 중위 표기 식이 온다고 가정하자.

 

숫자(피연산자)일 경우:

    출력

 

연산자가 올 경우:

    우선순위가 높은 연산자가 입력으로 있는 경우:

        스택에 삽입한다.

 

    스택이 비어있는 경우:

        스택에 삽입한다.

 

    스택에 입력보다 우선순위가 높거나 같은 연산자가 있는 경우:

    (입력의 우선순위가 높고 스택의 우선순위가 낮을 때)

    (ex. +는 *보다 우선순위가 높다)

        스택에 들어있는 연산자를 출력하고 연산자를 삽입한다.

        (이 과정은 스택에 입력보다 우선순위가 낮거나 같은 연산자가 존재하지 않을 때까지 반복해준다.)

        (즉, 입력 연산자의 우선순위가 가장 낮아야한다. )

 

여는 괄호 ' ( ' 가 올 경우:

    스택에 삽입

 

닫는 괄호 ' ) '가 올 경우:

    스택에서 ' ( ' 가 나올 때까지 pop 하면서 출력

 

입력이 끝났을 때 스택이 비어있지 않은 경우:

    스택이 빌 때까지 pop 하면서 동시에 나온 값 출력

 

우선순위 

( , ) : 0

+ , - : 1

*, /  : 2

 

만약 이해가 잘 되지 않는다면 아래 그림을 통해 이해해보도록 하자.

 

 

입력으로 2+3*4-5 가 주어졌을 때, 

 

2는 피연산자이므로 출력, +는 연산자이며 스택이 비어있으므로 삽입(push), 3은 피연산자이므로 출력한다.

 

*는 연산자이며, 스택이 비어있지 않고 연산자 + 가 존재하지만 *가 우선순위가 낮으므로 무시하고 *를 스택에 삽입한다.

4는 피연산자이므로 출력한다.

 

-는 연산자이며, 스택이 비어있지 않고 - 는 * 보다 우선순위가 높으므로  *를 pop을 하고 출력을 해준다. 그런데 + 또한 -랑 우선순위가 같으므로 + 또한 pop을 하고 출력을 해준다. 그리고 -를 스택에 삽입해준다.

 

5는 피연산자이므로 출력한다.

 

입력이 끝났으나 스택에 - 가 남아있으므로 -를 출력해준다.

 

234*+5- 로 변환이 완료되었다.

 

 

 

후위 표기식 만들기 구현

 

위의 과정들을 C언어로 구현하면 다음과 같은 코드가 나온다.

 

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define SIZE 100

typedef struct StackType{
    int top;
    int elem[SIZE];
}StackType;

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

int isFull(StackType *S){
    return S->top == SIZE - 1;
}

int isEmpty(StackType *S){
    return S->top == -1;
}
void push(StackType *S,int e){
    S->elem[++S->top] = e;
}

int peek(StackType *S){
    if(isEmpty(S)){
        return -1;
    }
    int top = S->elem[S->top];
    return top;
}

int size(StackType *S){
    int size = S->top+1;
    return size;
}

int pop(StackType *S){
    if(isEmpty(S))
        return -1;
    else{
        int e = S->elem[S->top--];
        return e;
    }
}

void printStack(StackType *S){
    if(isEmpty(S)){
        return;
    }
    else{
        printf("Stack:");
        for(int i = 0; i <= S->top; i++){
            printf(" %d",S->elem[i]);
        }
    printf("\n");
    }
    
}

int isoperator(char ch){
    if(ch == '+' || ch == '-' || ch == '*' || ch == '/' )
        return 1;
    else 
        return 0;
}

//우선순위 반환 함수
int priority(char ch){
    if(ch == '+' || ch == '-')
        return 1;
    else if(ch == '*' || ch == '/')
        return 2;
    else if(ch == '(' || ch == ')')
        return 0;
    return -1;
}

//중위표기식->후위표기식 변환 함수
void infix2postfix(char str[]){
    int len = strlen(str);
    //printf("%d\n",len);
    StackType S;
    init(&S);

    for(int i = 0; i < len; i++){
        //여는 괄호가 올 경우
        if(str[i] == '(')  
            push(&S,str[i]);
        // 닫는 괄호가 올 경우
        else if(str[i]==')'){
            char i = pop(&S);
            while(i !='('){
                printf("%c",i);
                i = pop(&S);
            }
        }
        //피연산자가 올 경우
        else if(isoperator(str[i]) == 0){ 
            printf("%c",str[i]);
        }
        //연산자가 올 경우
        else if(isoperator(str[i]) == 1){ 
            //스택이 비어있는 경우
            if(isEmpty(&S)){
                push(&S,str[i]);
            }
            // 스택보다 우선순위가 높은 연산자가 입력으로 있는 경우
            else if(priority(str[i]) > priority(peek(&S))){
                push(&S,str[i]);
            }
            //스택에 입력보다 우선순위가 낮거나 같은 연산자가 있는 경우
            else if(priority(str[i]) <= priority(peek(&S))){
                while(priority(str[i]) <= priority(peek(&S)) && isEmpty(&S) == 0){
                    printf("%c",pop(&S));
                }
                push(&S,str[i]);
            }
        }
    }
    //입력이 끝났을 때 스택이 비어있지 않은 경우
    while(isEmpty(&S)!=1){
        printf("%c",pop(&S));
    }
}

int main()
{   
    char str[] = "(2+3)*4+9";
    infix2postfix(str);

    return 0;
}

 

만약에 짠 코드가 모든 경우에 대해서 잘 동작하는지 확인하고 싶다면, 백준의 1918번 문제에다 코드를 한번 제출하는 것도 도움이 될 것이다.

 

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

 

이번 시간에는 중위 표기식을 후위 표기식으로 바꾸는 방법에 대해서 알아보았다. 

혹시 궁금하거나 헷갈리거나 잘못된 부분이 있다면 언제든지 댓글로 알려주시면 좋겠습니다!! 

 

다음 시간에는 다른 자료구조를 한번 다뤄볼 생각이다.

 

참조

 

천인국 외 2인 , C언어로 쉽게 풀어쓴 자료구조, 생능출판, 2019

 

https://sirzzang.github.io/programming/Programming-Postfix/

[알고리즘] 후위표기법 연산