[C/C++] 백준 #1918 후위 표기식(스택)

후위 연산식, 후위 표기식은 모두 스택을 이용해서 문제를 풀 수 있습니다.

 

여기서는 중위 연산식을 후위 연산식으로 바꾸는 것인데요.  사칙연산자와 괄호만 사용하고 있어서 구현 자체가 어렵지는 않습니다.  단지 주의할 것은 연산자 우선순위입니다.  연산자 우선순위는 테이블을 이용하기도 하지만, 저는 그냥 조건문으로 해결하였습니다.  연산자가 많은 경우에는 테이블을 이용하는 것이 더 유리하겠죠.

 

infix to postfix

 

중위식에서 후위식으로 바꾸기 위해서는 토큰을 다음과 같이 나누어야 합니다.  +, -, *, /, (, ), 숫자로 나눌 수 있습니다.

1) 연산자를 저장할 스택을 마련합니다.

2) + - 연산자의 경우 스택이 비거나 ( 기호가 나올 때까지 연산자를 끄집어내어 출력합니다.  해당 연산자는 스택에 넣습니다.

3) * / 연산자의 경우 스택이 비거나 ( 기호가 나오거나 +, - 기호가 나올 때까지 연산자를 끄집어내어 출력합니다.  해당 연산자는 스택에 넣습니다.

4) ( 기호의 경우 스택에 넣습니다.

5) ) 기호의 경우 스택에 (가 나올 때까지 연산자를 끄집어내어 출력 후에 ( 기호를 스택에서 빼냅니다.

6) 숫자의 경우 출력합니다.

7) 끝나면 스택이 빌때까지 연산자를 끄집어 내어 출력합니다.

 

예를 들어서 (3 + 2) * (4 - 3) 이라는 중위식이 있다고 해보죠.

1) ( 은 스택에 넣습니다.

2) 3 은 출력합니다.

3) +은 스택에 넣습니다.

4) 2 는 출력합니다.

5) )이 나오면 (이 나올 때까지 연산자를 출력합니다.  출력 내용은 +

6) *은 스택에 넣습니다.

7) (은 스택에 넣습니다.

8) 4 는 출력합니다.

9) -는 스택에 넣습니다.

10) 3은 출력합니다.

11) )가 나오면 (이 나올때까지 연산자를 출력합니다.  출력 내용은 -

12) 식이 끝나면, 스택에 남아있는 연산자들을 출력합니다.  출력 내용은 *

이렇게 하면 (3 + 2) * (4 - 3)의 식은 3 2 + 4 3 - * 가 됩니다.

 

제가 작성한 소스입니다.  사실 바로 출력해도 되지만, post라는 배열을 사용했습니다.  소스는 참고용으로 봐주세요.

//-------------------------------------------
//    baekjoon #1918 - Postfix expression
//        - by Aubrey Choi
//        - created at 2019-11-27
//-------------------------------------------
#include <stdio.h>

int main()
{
    char exp[104], post[100], n=0, stack[100], sp=0;
    scanf("%s",exp);
    for(int i=0;exp[i];i++)
    {
        if(exp[i]=='+'||exp[i]=='-')
        {
            while(sp>0&&stack[sp-1]!='(') post[n++]=stack[--sp];
            stack[sp++]=exp[i];
        }
        else if(exp[i]=='*'||exp[i]=='/')
        {
            while(sp>0&&(stack[sp-1]!='('&&stack[sp-1]!='+'&&stack[sp-1]!='-')) 
                post[n++]=stack[--sp];
            stack[sp++]=exp[i];
        }
        else if(exp[i]=='(') stack[sp++]=exp[i];
        else if(exp[i]==')')
        {
            while(stack[sp-1]!='(') post[n++]=stack[--sp];
            sp--;
        }
        else post[n++]=exp[i];
    }
    while(sp>0) post[n++]=stack[--sp];
    printf("%.*s\n", n, post);
}