[C] 1874 - 스택 수열

문제 링크

백준 - 스택 수열

---

문제 내용

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

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

아마 예시 입출력이 없었다면 아직도 문제를 이해하지 못했을 것이다.

쉽게 설명하자면 1부터 오름차순으로 스택에 push 할 수 있고 pop을 통해 입력된 수열을 만들 수 있는지 체크하고 만들 수 있다면 push와 pop의 과정들을 출력하는 문제이다.

세가지 조건을 나누어서 해결했다.

우선 peek라고도 불리는 stack[top] 값과 temp(입력값)을 비교했다.

1. stack[top]값이 더 큰 경우
"NO" 출력 후 프로그램 종료

2. temp값이 더 큰 경우
stack[top]과 temp가 같아질때까지 push 후 같아지면 pop 진행

3. 두 값이 같은 경우
pop 진행

이 세 가지 경우로 나누어 코드를 짰다.

---

코드

#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));
  }
}