BOJ9012 괄호

문제 요약
입력된 괄호가 올바른 순서를 따르고 있는지를 알아보는 프로그램을 작성하세요.

문제 풀이
스택을 이용합니다.
우선 올바른 괄호라면, 스택이 다음과 같이 처리됩니다.
1. '('를 만나면 반드시 여기에 맞는 ')'가 나와야 하므로, 스택에 push한다.
2. ')'를 만나면 반드시 여기에 맞는 '('가 스택에 들어있어야 하므로, 스택을 pop한다.
3. 입력된 문자열을 모두 처리하고 나면, 스택은 비어 있어야 한다.

잘못된 괄호라면, 다음과 같은 상황이 일어납니다.
1. '('가 나오지 않았는데 ')'가 먼저 나온다. -> 비어 있는 스택에서 pop을 시도한다.
2. '('에 맞는 ')'가 부족하다. -> 입력된 문자열을 모두 처리했는데, 스택이 비어 있지 않다.

주의할 점
스택의 위치를 표시하는 top이 연산 과정에서 -1 -> -2 -> -1로 가는 경우가 발생할 수 있으므로, 잘못된 상황이 벌어지면 루프문에서 바로 빠져나와 잘못되었다는 판단을 한다.


C 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n = -1;
void push(int* stack)
{
 stack[++n] = 1;
}
int pop(int* stack)
{
 if (n >= 0)
  return stack[n--];

}

int empty(int* stack)
{
 return n == -1 ? 1 : 0;
}

int main(void)
{
 int num;
 scanf("%d", &num);
 for (int i = 0; i < num; i++)
 {
  int stack[60];
  char input[60];
  scanf("%s", input);
  for (int j = 0; j < strlen(input); j++)
  {
   if (input[j] == '(')
   {
    push(stack);
   }
   else if(n != -1)
   {
    pop(stack);
   }
   else
   {
    n--;
    break;
   }
  }
  if (n == -1)
  {
   puts("YES");
  }
  else
  {
   puts("NO");
   n = -1;
  }
 }


 return 0;
}