스택의 응용: 괄호 검사 문제

괄호가 올바르게 사용되었는지 스택을 사용하여 검사한다.

 

괄호의 검사 조건은 아래와 같다.

• 조건 1: 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 동일
• 조건 2: 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 함
• 조건 3: 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차할 수 없음

{A[(i + 1) = 0]}		->오류 없음
if ((i == 0) && (j == 0)	->오류: 조건 1
A[(i + 1]) = 0			->오류: 조건 3

 

이러한 괄호 사용 오류 검사에 스택을 사용할 수 있다. 가장 가까운 거리에 있는 괄호들끼리 서로 쌍을 이루어야 하므로, 스택을 사용하여 왼쪽 괄호들('(', '{', '[')을 만나면 계속 삽입하다가 오른쪽 괄호들(')', '}', ']')이 나오면 스택에 저장된 가장 최근의 왼쪽 괄호와 비교해 오류를 검사한다.

 

문자열에 있는 괄호를 차례대로 조사하며 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택에서 맨 위의 괄호를 꺼낸 후 오른쪽 괄호와 짝이 맞는지 검사한다. 이 때, 스택이 비어 있으면 조건 1 또는 조건 2에 위배되고, 괄호의 짝이 맞지 않으면 조건 3에 위배된다. 마지막 괄호까지 조사한 후에도 스택에 괄호가 남아 있으면 조건 1에 위배되므로 오류이다.

 

괄호 검사 알고리즘을 의사 코드로 만들어보면 아래와 같다.

---

프로그램 4.6 괄호 검사 프로그램

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_STACK_SIZE 100

typedef char element;
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType;

void init_stack(StackType* s) {
	s->top = -1;
}
int is_empty(StackType* s) {
	return (s->top == -1);
}
int is_full(StackType* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}
void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else
		s->data[++(s->top)] = item;
}
element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return s->data[(s->top)--];
}
element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else
		return s->data[s->top];
}

int check_matching(const char* in) {
	StackType s;
	char ch, open_ch;
	int i, n = strlen(in);
	init_stack(&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 0;
			else {
				open_ch = pop(&s);
				if ((open_ch == '(' && ch != ')') ||
					(open_ch == '[' && ch != ']') ||
					(open_ch == '{' && ch != '}'))
					return 0;
				break;
			}
		}
	}
	if (!is_empty(&s)) return 0;
	return 1;
}

int main(void) {
	char* p = "{ A[(i+1)]=0; }";
	if (check_matching(p) == 1)
		printf("%s 괄호검사성공\n", p);
	else
		printf("%s 괄호검사실패\n", p);

	return 0;
}

>>