9012. Parenthesis

9012번 문제는 괄호의 유효성 검사를 하는 문제이다.

 

자료구조인 스택을 활용하여 문제를 해결한다.

 

입력으로 '('가 들어오면, 스택에 넣는다.

반대로 ')'가 들어오면, 스택에서 '('가 있는지 꺼내어 본다.

만약 짝이 맞지 않다면, 유효하지 않은 것으로 판단한다.

 

#include <stdio.h>
#include <string.h>
 
#define MAX_STACK_SIZE 50
 
char stack[MAX_STACK_SIZE];
int top_index;
 
void init(void) {
    int i;
 
    for (i = 0; i < MAX_STACK_SIZE; i++) {
        stack[i] = 0x00;
    }
    top_index = -1;
}
 
void push(char c) {
    top_index++;
    stack[top_index] = c;
}
 
char pop(void) {
    int ret;
 
    if (top_index < 0) {
        return -1;
    }
 
    ret = stack[top_index];
    stack[top_index] = 0x00;
    top_index--;
 
    return ret;
}
 
void func(void) {
    char c, r;
    char str[MAX_STACK_SIZE + 1];
    int l;
 
    scanf("%s", str);
    l = strlen(str);
 
    for(int i = 0 ; i < l ; i++){
        c = str[i];
 
        if (c == '(') {
            push(c);
        }
        else { // c == ')'
            r = pop();
            if (r != '(') {
                do { r = getchar(); } while (r != '\n' && r != -1);
                printf("NO\n");
                return;
            }
        }
    }
 
    if (top_index == -1) {
        printf("YES\n");
    }
    else {
        printf("NO\n");
    }
 
    return;
}
 
int main(void) {
    int tc;
 
    // freopen("input.txt", "r", stdin);
    scanf("%d%*c", &tc);
 
    for (int i = 0; i < tc; i++) {
        init();
        func();
    }
 
    return 0;
}