[C] 스택과 후위 표기식(1918 - 후위 표기식)

문제 링크

백준 - 후위 표기식

---

문제 내용

C에는 스택 라이브러리가 없기 때문에 구현하여 사용해야한다.

그래서 스택을 구현한 김에 더 깊게 이해하고자 스택 문제를 여러 개 풀고 있다.

---

후위 표기식(Postfix Notation)이란?

우리는 1+2+3 처럼 숫자(피연산자)와 숫자 사이에 연산자(+)를 넣어서 식을 표현하는데

이를 중위 표기식(Infix Notation)이라고 한다.

후위 표기식(Postfix Notation)은 연산자가 피연산자의 뒤에 온다.

1 + 2 + 3 (Infix)

1 2 + 3 + (Postfix)

컴퓨터가 후위 표기식을 사용하는 이유

후위 표기식은 앞에서부터 뒤로 가면서 연산자가 보이면 앞의 두 숫자를 피연산자로 계산하면 된다.

중위 표기식 1+2×3의 경우 후위 표기식으론 123×+이다.

앞에서부터 차례로 읽다가 연산자인 ×가 발견되었을 때 앞에 있는 2개의 피연산자 2 3를 대상으로 2×3=6을 실행한다.

그 뒤의 연산자인 +가 발견되었을 때 앞에 있는 2개의 피연산자 1 6을 대상으로 1+6=7을 실행한다.

컴퓨터는 후위 표기식을 사용하는데, 이런 후위 표기식을 컴퓨터가 사용하는 근본적인 이유는

괄호도 필요없고 연산자 우선 순위를 고려할 필요도 없기 때문이다.

후위 표기식과 스택

이러한 방식의 후위 표기식을 만들거나 후위 표기식을 중위 표기식으로 만들때 스택(Stack) 구조가 사용된다.

간단한 예를 들면 아까처럼 123x+을 중위 표기식으로 사용할때 1/2/3을 스택에 담고 x를 만나면

pop() x pop() 후 연산한 값을 push()한다면 스택에는 1/6이 들어가 있을 것이다.

이 예시는 후위 표기식을 중위 표기식으로 만드는 과정이었고, 이 문제는 반대로 중위 표기식을 후위 표기식으로 만드는 문제이다.

---

중위 표기식 -> 후위 표기식

먼저 코드를 작성하기 전 4가지 규칙을 찾았다.

1. 피연산자는 출력한다.

2. '('를 만난다면 push한다.

3. ')'를 만난다면 '('가 나올때까지 pop을 진행하고 그 사이의 연산자들을 출력한다.

4. 연산자를 만난다면 push하지만 이때 peek의 우선순위가 연산자의 우선순위보다 크거나 같다면 우선순위가 더 작아질때까지 pop 후 출력하고 연산자를 push한다.

이 조건을 잘 신경쓴다면 문제없이 코드를 구현할 수 있다.

---

코드

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

typedef char element;

typedef struct{
  element data[MAX_STACK_SIZE];
  int top; 
}StackType;

void init_stack(StackType *s){
  s->top = -1;
}

int is_empty(StackType *s){
  return(s->top == -1);
}

int is_full(StackType *s){
  return(s->top == MAX_STACK_SIZE-1);
}

void push(StackType *s, element item){
  if(is_full(s)){
    return;
  }
  s->data[++(s->top)] = item;
}

element pop(StackType *s){
  if(is_empty(s)){
    return 0;
  }
  return s->data[(s->top)--];
}

int priority(char c){
  if(c == '(' || c==')')
    return 0; //'()'은 연산에 참가 안하고 따로 처리하므로 후순위로 둠
  else if(c == '+' || c == '-') 
    return 1;
  else if(c == '*' || c == '/')
    return 2;
}

int main(void){
  char input[100] = {0,};
  scanf("%s", input);
  StackType s;
  char temp;
  init_stack(&s);
  for(int i=0; i<strlen(input); i++){
    int ch = input[i];
    switch(ch){
      case '+': case '-' : case '*' : case '/':
        while(!is_empty(&s) && priority(s.data[s.top])>=priority(ch)){ 
        //스택에 있는 연산자의 우선순위가 더 크거나 같으면 출력
          printf("%c", pop(&s));
        }
        push(&s, ch);
        break;

      case '(': 
        push(&s, ch);
        break;

      case ')':
        temp = pop(&s);
        while(temp !='('){
          printf("%c", temp);
          temp = pop(&s);
        }
        break;

      default : //피연산자인 경우
        printf("%c", ch);
        break;
    }
  }
  while(!is_empty(&s)){ //남은 연산자 출력
    printf("%c", pop(&s));
  }
}