[자료구조] 스택 활용 - 괄호 검사 프로그램 ( Check Balanced Parentheses Using Stack)

 

 

data.txt
{A[(i+1)]=0}
{B[100-(i+5)]*5}
{C/(5/5*(5-4)}
(10+5)-(30-20)



전체 코드 :

#include <stdio.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;
	}

	s->data[++(s->top)] = item;
}

element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		return -1;
	}
	return 	s->data[(s->top)--];
}

element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		return -1;
	}
	return 	s->data[s->top];
}

int bracket_checker(char* exp) {
	StackType s;
	char ch, open_ch;

	int len = strlen(exp);
	init_stack(&s);

	// 문자열 길이만큼 반복

	for (int i = 0;i < len;i++) {
		ch = exp[i];

		switch (ch) {
			// 만약 여는 괄호라면, 스택에 push
		case '(': case '[': case '{':
			push(&s, ch);
			break;

			// 닫는 괄호라면, 스택에서 pop하여 비교 (같지 않다면 오류)
		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() {
	FILE* fp;
	char str[1024] = { 0 };

	fp = fopen("data.txt", "rt");
	while (!feof(fp)) {
		fscanf(fp, "%s", str);

		if (bracket_checker(str))
			printf("%s 괄호 검사 성공 \n", str);
		else
			printf("%s 괄호 검사 실패 \n", str);

	}
}

결과:

---

한 블록씩 자세히 살펴보자.



1. 기호 상수 선언, 구조체 선언

가독성을 높이기 위하여 1과 0을 각각 TRUE, FALSE의 기호 상수로 선언한다.
한 개의 스택에 들어갈 수 있는 요소의 최대 크기 MAX_STACK_SIZE는 100으로 정의하였다.

괄호에 대하여 문자를 체크해야 하므로 char 문자를 element라는 새로운 자료형으로 선언하고
한 개의 스택을 표현하는 StackType에 element 형 스택 배열과 top 정수를 StackType 구조체로 정의하였다.

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

2. 스택 초기화, 스택 공백/포화 체크 함수

init 함수 : 생성된 스택의 top 멤버의 값을 -1로 설정함으로써 스택을 초기화하는 함수
is_empty 함수 : 스택의 top 값이 -1인지 체크하여 공백 스택인지 판별하는 함수 (pop 연산 하기 전 필수)
is_full 함수 : top이 100으로 정의한 MAX_STACK_SIZE보다 1 작은 값인지 체크하여 가득 찬 스택인지 판별하는 함수 (push 연산 하기 전 필수)

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

3. 요소 삽입/삭제 함수

void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}

	s->data[++(s->top)] = item;
}

element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		return -1;
	}
	return 	s->data[(s->top)--];
}

element peek(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		return -1;
	}
	return 	s->data[s->top];
}

 

---

4. 괄호 검사 함수 bracket_checker

int bracket_checker(char* exp) {
	StackType s;
	char ch, open_ch;

	int len = strlen(exp);
	init_stack(&s);

	// 문자열 길이만큼 반복

	for (int i = 0;i < len;i++) {
		ch = exp[i];

		switch (ch) {
			// 만약 여는 괄호라면, 스택에 push
		case '(': case '[': case '{':
			push(&s, ch);
			break;

			// 닫는 괄호라면, 스택에서 pop하여 비교 (같지 않다면 오류)
		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;
}

괄호 검사 문제의 핵심인 위 함수를 자세히 살펴보자.
파일로부터 읽어들인 한 줄의 char 배열 in을 매개 변수로 전달 받아
문자를 하나씩 앞에서부터 스캔하며, 괄호 (, [, {, ), ], } 의 짝이 맞는지 검사를 한다.



괄호의 검사 조건은 다음과 같다.

1. 왼쪽 괄호 개수 == 오른쪽 괄호 개수

왼쪽 괄호의 개수만큼 오른쪽 괄호의 개수를 비교한 후에, 괄호가 스택에 남아있는 경우는 검사 실패!

2. 같은 종류의 괄호에서 왼쪽 괄호가 오른쪽 괄호보다 먼저 나와야 함

왼쪽 괄호 이후 짝이 맞는 오른쪽 괄호가 나와야 한다.

3. 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로를 교차하면 안 됨

최근에 나타났던 왼쪽 괄호에 대하여 짝이 맞는 오른쪽 괄호가 짝을 이루어야 한다.

위 세 가지 조건을 모두 만족하여 검사에 성공하면 TRUE(1),
중간에 조건을 만족하지 않아 오류가 발생하여 실패하면 FALSE(0) 값을 리턴하게 된다.

---

처음부터 하나하나 살펴보자!


1) 필요한 변수들 선언, 스택 초기화

- StackType 구조체 변수 s 선언
- char ch : 문자열의 문자들을 하나씩 스캔하여 임시로 저장
- char open_ch : 스택에서 pop한 문자를 저장 (왼쪽 괄호와 비교할 문자)
- 반복문 제어 변수 i
- 매개변수로 전달받은 문자열 in의 길이를 n에 저장

변수들을 선언하고, 문자들을 저장할 스택을 초기화해준다.

	StackType s;
	char ch, open_ch;
	int i, n = strlen(in); // 문자열의 길이

문자열의 각 문자에 대한 switch-case 조건문 실행 ( 괄호에 대해서만 수행. 피연산자, 숫자는 모두 무시)
왼쪽 괄호에 대해서는 스택에 저장하고, 오른쪽 괄호에 대해서는 스택에 저장한 왼쪽 괄호와 비교한다.


2) 왼쪽(여는) 괄호인 경우
소괄호 parenthesis ( , 중괄호 brace { , 대괄호 bracket [ 중 하나인
왼쪽 괄호라면, push 연산을 이용해 스택에 저장한다.

			// 여는 괄호에 대하여
		case '(': // parenthesis
		case '[': // braclet
		case '{': // bracket
			push(&s, ch);
			break;

3) 오른쪽(닫는) 괄호인 경우

), }, ] 에 대하여 먼저 스택이 비어있는지 확인한다.
오른쪽 괄호에 대하여 검사하는데, 스택에 저장된 것이 아무것도 없다면 FLASE를 리턴한다.
검사 조건의 첫번째 조건(왼쪽, 오른쪽 괄호의 개수가 같아야 함과
두번째 조건(왼쪽 괄호가 오른쪽 괄호보다 먼저 나와야 한다) 을 만족하지 않기 때문에 검사에 실패하게 된다.

is_empty가 TRUE값이 아니라면, 스택에 저장되어 있는 문자를 pop연산을 통해 open_ch에 저장한다.
가장 최근에 저장된 문자이므로, 오른쪽 괄호와 쌍이 맞는 왼쪽 괄호여야 한다.
소, 중, 대괄호인 경우 각각에 대하여 오른쪽 괄호와 짝이 맞는지 체크하고, 아닌 경우 FALSE를 리턴한다.

         // 닫는 괄호에 대하여
		case ')':
		case ']':
		case '}':
			// 스택에 비어 있는 경우 짝이 맞지 않는 경우 false 리턴
			if (is_empty(&s))
				return FALSE;

for문 내에서는 위와 같이 '괄호' (, {, [, ), }, ] 에 대해서만 조건문을 실행하게 된다.
따라서 피연산자인 숫자나 공백문자 등 다른 문자에 대해서는 고려하지 않아도 된다.



4) 스택에 문자가 남아있는지 마지막으로 확인
위에서 살펴보았듯이, 스택에 저장되는 것은 오로지 왼쪽(여는) 괄호 뿐이다.
따라서 오른쪽 괄호와의 비교를 모두 마친 후, 마지막으로 is_empty 함수를 실행하여
스택에 남아있는 값이 있는지 체크를 해보도록 한다.
만약 그 결과값이 FALSE라면 왼쪽 괄호가 오른쪽 괄호의 숫자와 짝을 이루어 스택에 저장되지 않았다는 것을 의미한다.
따라서 이러한 경우 괄호 검사에 실패하게 된다.

위와 같은 경우가 아니라면, TRUE를 반환하여 검사가 성공했음을 알린다.

	if (is_empty(&s))
				return FALSE;
			else {
				open_ch = pop(&s);
				// 짝이 맞지 않는 경우에 false 리턴
				if (open_ch == '(' && ch != ')' ||
					open_ch == '[' && ch != ']' ||
					open_ch == '{' && ch != '}')
					return FALSE;
			}

 

---

5. main 함수
data.txt 파일에 저장되어 있는 데이터를 한 줄씩 읽으므로, 총 4개의 문장에 대하여 check_matching을 실행하게 된다.
check_matching 의 값이 TRUE (괄호 검사에 성공) 한 경우 "matching succeed" 문장과 함께 해당 괄호 문장을 출력한다.
실패한 경우에는 "matching failed" 문자오가 함께 해당 괄호 문장을 출력한다.

int main() {
	char buf[1024] = { 0 };

	FILE* fp = fopen("data.txt", "rt");
	if (fp == NULL) {
		printf("file not open\n");
		return 0;
	}

	while (!feof(fp)) {
		fscanf(fp, "%s", buf);
		if (check_matching(buf) == TRUE)
			printf("matching succeed : ");
		else
			printf("matching failed : ");

		printf("%s\n", buf);
	}

	fclose(fp);
}