[C] 백준 9012번: 괄호

 문제 조건은 참 간단하다. 괄호 짝이 알맞게 지어져 있는지를 판별하는 것이다. 

 여는 괄호가 계속 누적 됐다가 나올 수도 있고 열렸다가 닫혔다가 반복할 수 있기 때문에 스택을 이용해 푸는 것이 가장 편하게 먹힌다고 생각한다. 시간이 나면 한 번 스택이 아닌 다른 방법으로도 풀어봐야겠다.

입출력 예시

정답 코드

#include <stdio.h>

char stack[50];
int top = 0;

int isVPS(char *);

void push(char);
char pop();
int isEmpty();

int main() {

	int t;
	char str[51];

	int i;

	scanf("%d", &t);

	for (i = 0; i < t; i++) {
		scanf("%s", str);

		if (isVPS(str)) printf("YES\n");
		else printf("NO\n");
	}

	return 0;

}

int isVPS(char *str) {

	int result = 1;

	int i;

	for (i = 0; str[i]; i++) {

		if (str[i] == '(') {
			push(str[i]);
		}
		else {

			if (isEmpty()) {
				result = 0;
				break;
			}
			else {
				pop();
			}

		}

	}

	if (!isEmpty()) result = 0;

	while (!isEmpty()) {
		pop();
	}

	return result;

}

void push(char c) {
	stack[top++] = c;
}

char pop() {
	return stack[--top];
}

int isEmpty() {
	return top == 0;
}

코드 설명

1. 문자열의 갯수 T를 입력받는다.

2. T만큼의 문자열을 입력받는다. 입력 받으면 이 문자열이 VPS인지 검사하는 함수 isVPS를 통해 YES와 NO를 출력한다.

3. 함수 isVPS는 다음과 같이 작동한다. 

 1) result(VPS면 1, 아니면 0)를 1로 초기화하고 문자열 처음부터 탐색한다. 문자가 여는 괄호면 문자를 스택에 push한다. 

 2) 문자가 닫는 괄호면 pop을 하는데, 만약 스택이 비어있으면 닫는 괄호에 앞서 나온 여는 괄호가 없기 때문에 VPS가 아닌 문자열이 된다. 그렇다면 result를 0으로 바꿔주고 for문을 탈출한다. 

 3) for문 중간에서 break 없이 정상적으로 종료되어도, 스택이 비어있지 않으면 여는 괄호는 남았지만 그에 대응하는 닫는 괄호가 나오지 않은 것이 된다. 만약 for문 종료 후 스택이 비어있지 않으면 result를 0으로 바꿔준다.

 4) 다음 VPS 탐색을 위해 스택을 전부 비워준다.

 5) result를 return 한다.