[백준1918번] (C) 후위표기식

백준 1918번

착안점

1. 각 연산자(operator)의 우선순위값을 return해주는 isOperator 함수를 만들어줬다.
   (, ) : 우선순위 0
   +, - : 우선순위 1
   *, / : 우선순위 2
   피연산자 : 우선순위 -1 (즉, A, B, C)
   
   
2. postfix함수가 가장 중요한 함수라고 할 수 있다. for문을 이용해 글자 하나하나씩 읽어나간다.
   • 우선순위 -1 : 피연산자는 그대로 출력
   • 열린괄호 ( : 스택에 push
   • 닫힌괄호 ) : 스택에 있는 (를 만날 때까지 pop
   • 우선순위 1 이상
     • 스택이 비어있지 않고 && 스택에 있는 연산자의 우선순위가 더 높다면 pop
     • 그외의 경우라면 스택에 push
   • 맨 마지막에서는 스택에 남아있는 것이 없도록 모두 pop

#include <stdio.h>
#include <string.h>
#define MAX_SIZE    100

typedef struct Stack{
    int top;
    char s[MAX_SIZE];
}Stack;

void push(Stack *s, char elem){
    s->top++;
    s->s[s->top] = elem;
}

char pop(Stack *s){
    char temp = s->s[s->top];
    s->top--;
    return temp;
}
int is_empty(Stack *s){
    if (s->top != -1)
        return 0;
    return 1;
}

char peek(Stack *s){
    return s->s[s->top];
}

int isOperator(char op){
    switch(op){
        case '(': case ')':
            return 0;
        case '+': case '-':
            return 1;
        case '*': case '/':
            return 2;
        default:
            return -1;
    }
}

void postfix(char *str){
    int i=0;
    Stack s;
    s.top = -1;
    for(i=0; i<strlen(str); i++){
        if(isOperator(str[i]) == -1){
            printf("%c", str[i]);
        }
        else if(str[i]=='('){
            push(&s, str[i]);
        }
        else if(str[i]==')'){
            while(peek(&s) != '('){
                printf("%c", pop(&s));
            }
            pop(&s);
        }
        else if (isOperator(str[i]) >=1 ){
            // 스택이 비어있지 않고 && 스택 top의 우선순위가 더 높다면 pop
            while(!is_empty(&s) && isOperator(str[i]) <= isOperator(peek(&s))){
                printf("%c", pop(&s));
            }
            push(&s, str[i]);
        }
    }
    while(!is_empty(&s)){
        printf("%c", pop(&s));
    }
}

int main(void){
    char str[100];
    int i=0;
    scanf("%s", str);
    postfix(str);
}