[Data Structure] #2-4 스택을 이용한 괄호 검사

스택을 이용한 괄호 검사

 스택을 응용해서 괄호 검사를 한다. 괄호에서 스택을 쓰는 이유는 단순하다. 가장 최근에 들어간 열린괄호와 지금 들어가는 닫힌 괄호와 같은 타입이어야 하기 때문이다. 즉, 가장 나중에 넣은 것이 가장 먼저 나와야 한다. 그래서 스택을 쓰는 것이다.  이전에 했던 배열 스택를 그대로 가져다 쓰고 있다. 추가된 점이라는 메서드 check_matching() 뿐이다. 코드 상단에 조건3개를 적어놨는데 이 조건들이 check_matching 메서드에서 어떻게 적용되는지를 봐두자. 이미 주석을 달아놨기 때문에 보고 이해만 해도 좋다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE_STACK 100
#define FALSE 0
#define TRUE 1


// 1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같다.
// 2. 같은 타입의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
// 3. 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안된다.

typedef int element;
typedef struct {
    element stack[MAX_SIZE_STACK];
    int top;
} StackType;

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

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

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

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

element pop(StackType *s){
    if (is_empty(s))
        exit(1);
    return s->stack[(s->top)--];
}

element peek(StackType *s){
    if (is_empty(s))
        exit(1);
    return s->stack[s->top];
}

int check_matching(char *in){
    StackType s;
    char ch; // character from in
    char open_ch; // character from stack
    int i;
    int n = (int) strlen(in);
    init(&s);
    
    for (i=0; i<n; i++) {
        ch = in[i];
        switch (ch) {
            case '(': case '{' : case '[':
                push(&s, ch);
                break;
            case ')': case '}' : case ']':
                if (is_empty(&s)) // condition 1, 3
                    return FALSE;
                open_ch = pop(&s); // condition 2, 3
                if ((open_ch == '(' && ch != ')') ||
                    (open_ch == '{' && ch != '}') ||
                    (open_ch == '[' && ch != ']')) {
                    return FALSE;
                }
                break;
        }
    }
    if (!is_empty(&s)) // condition 1
        return FALSE;
    return TRUE;
}

int main(){
    if (check_matching("{A[(i+1)]=0;}")==TRUE) {
        printf("Success\n");
    } else {
        printf("Fail\n");
    }
    return 0;
}

역시나 어려운 것이 없으므로 자세한 설명은 생략한다.

...근데 맨날 쉬운것 같다. -_- 농담아니고..