프로그램에서는 여러 가지 타입의 괄호들이 같은 타입으로 쌍으로 존재하여야 한다.
프로그램에서는 대괄호[], 중괄호{}, 소괄호() 등이 사용되는데 괄호의 검사 조건은 다음의 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");
}