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

1.괄호 검사의 조건

①왼쪽 괄호의 개수 = 오른쪽 괄호의 개수

②같은 종류의 괄호에서 왼쪽 괄호가 더 먼저 나와야 함

③서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차X

 

ex. {A[(i+1)]=0;}             ->오류 없음

      if ((i==0) && (j==0)  ->오류: 조건 1 위반

     A[(i+1])=0;                ->오류: 조건 3 위반

 

 

2.괄호 검사 구현 알고리즘

①왼쪽 괄호를 만나면 -> 스택에 삽입

②오른쪽 괄호를 만나면

  a.스택에서 맨 위의 괄호를 꺼낸 후

  b.오른쪽 괄호와 짝이 맞는지 검사

괄호 검사 알고리즘

 

3.괄호 검사 프로그램

#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)--];
}

//peek 함수
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); //n=문자열의 길이
	init_stack(&s);//스택의 초기화

	for (i = 0;i < n;i++) {
		ch = in[i]; //ch=다음 문자
		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;
}

 

4.관련 연습문제

[C언어로 쉽게 풀어쓴 자료구조 p.143 #11] 수식에 있는 괄호의 번호를 출력하는 프로그램을 작성하여라. 왼쪽 괄호가 나올 때마다 괄호 번호는 하나씩 증가한다. 오른쪽 괄호가 나오면 매칭되는 왼쪽 괄호 번호를 출력한다.

실행결과

메인함수 코드

#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)--];
}

//peek 함수
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 count = 0;
	int i, n = strlen(in); //n=문자열의 길이
	init_stack(&s);//스택의 초기화

	for (i = 0;i < n;i++) {
		ch = in[i]; //ch=다음 문자
		switch (ch) {
		case '(':case'[':case'{':
			count++;
			printf("%d ", count);
			push(&s, count);
			break;
		case ')':case ']':case'}':
			if (is_empty(&s))return 0;
			else printf("%d ", pop(&s));
				break;
			}
		}
	if (!is_empty(&s))return 0;
	return 1;
}

int main(void)
{
	char line[100];
	printf("수식: ");
	gets_s(line, 100);
	printf("괄호수: ");
	check_matching(line);
	return 0;
}

push할 때, 그 괄호가 아닌 count, 즉 괄호의 번호를 넣었다. 그리고 pop할 때는 완성된 애의 번호가 나오는 방식!

사실 실행 예시가 '('<-소괄호로 이루어진 것밖에 없어서 case 에서 종류를 없애고 아예 open_ch의 존재를 없애버려도 되지만 기존 check_matching 함수와 최대한 비슷하게 냅두고 싶어서 그대로 둔다!