[자료구조] 스택 응용 - 괄호 검사

프로그램에서는 여러 가지 타입의 괄호들이 같은 타입으로 쌍으로 존재하여야 한다.

프로그램에서는 대괄호[], 중괄호{}, 소괄호() 등이 사용되는데 괄호의 검사 조건은 다음의 3가지 이다.

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

이러한 괄호 사용의 오류를 검사하는 데 스택을 사용할 수 있다.

위의 괄호들을 자세히 살펴보면 가장 가까운 거리에 있는 괄호들끼리 서로 쌍을 이루어야 됨을 알 수 있다.

따라서 왼쪽 괄호들을 만나면 스택에 삽입하다가 오른쪽 괄호들이 나오면 스택에서 가장 최근의 왼쪽 괄호를 꺼내어 타입을 맞추어보면 쉽게 괄호들의 오류를 검사할 수 있다.

스택은 이처럼 최근에 삽입한 것이 먼저 필요한 경우에 유용하다.

괄호의 오류 여부를 조사하려면 먼저 문자열에 있는 괄호를 차례대로 조사하면서 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 맨 위의 괄호를 꺼낸 후 짝이 맞는지를 검사한다.

이때, 스택이 비어 있으면 조건 1 또는 조건 2 등을 위반하게 되고 괄호의 짝이 맞지 않으면 조건 3에 위반된다.

마지막 괄호까지를 조사한 후에도 스택에 괄호가 남아 있으면 조건 1에 위반되므로 FALSE를 반환하고 그렇지 않으면 성공이므로 TRUE를 반환한다.

#include <stdio.h>
#define TRUE 1
#define FALSE 0

typedef char element;

typedef struct StackNode {

	element item;
	struct StackNode* link;

}StackNode;


typedef struct {
	StackNode* top;
}LinkedStackType;

void init(LinkedStackType* s) {
	s->top = NULL;
}

int is_empty(LinkedStackType* s) {
	return (s->top == NULL);
}

void push(LinkedStackType* s, element item) {
	StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
	if (temp == NULL) {
		fprintf(stderr, "메모리 할당에러\n");
		return;
	}
	else {
		temp->item = item;
		temp->link = s->top;
		s->top = temp;
	}
}

element pop(LinkedStackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		StackNode* temp = s->top;
		element item = temp->item;
		s->top = s->top->link;
		free(temp);
		return item;
	}
}

element peek(LinkedStackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		return s->top->item;
	}
}

int check_matching(char* in) {

	LinkedStackType s;
	char ch, open_ch;
	int n = strlen(in);
	init(&s);

	for (int i = 0; i < n; i++) {
		ch = in[i];

		switch (ch) {

		case '(': case '{': case '[':
			push(&s, ch);
			break;
		case ')': case '}': case ']':
			if (is_empty(&s)) return FALSE;
			else {
				open_ch = pop(&s);
				if ((open_ch == '(' && ch != ')') || (open_ch == '{' && ch != '}') || (open_ch == '[' && ch != ']')) return FALSE;
				break;
			}
			
		}
	}
	if (!is_empty(&s)) return FALSE;
	return TRUE;

}

int main() {
	if (check_matching("{ A[(i+1)]=0; }") == TRUE) printf("{ A[(i+1)]=0; } : 괄호검사성공\n");
	else printf("{ A[(i+1)]=0; } : 괄호검사실패\n");

	if (check_matching("if((i==0) && (j==0)") == TRUE) printf("if((i==0) && (j==0) : 괄호검사성공\n");
	else printf("if((i==0) && (j==0) : 괄호검사실패\n");

	if (check_matching("A[(i+1])=0;") == TRUE) printf("A[(i+1])=0; : 괄호검사성공\n");
	else printf("A[(i+1])=0; : 괄호검사실패\n");

}