[Data Structure] 스택 - 괄호 검사

괄호 검사

- 대괄호 [], 중괄호 {}, 소괄호 ()가 서로 짝이 맞는지 검사

1. 왼쪽 괄호 개수 = 오른쪽 괄호 개수
2. 같은 종류의 괄호이면, 왼쪽 괄호가 더 먼저 나와야 한다
3. 서로 다른 종류의 괄호면 쌍을 이루면 안된다

 

 

알고리즘

- 하나의 문자열 str이 존재

1. str안에 왼쪽 괄호 [, {, (는 push를 통해서 stack에 저장
2. 오른쪽 괄호 ], }, )를 만나면 stack에 저장된 왼쪽 괄호를 pop시켜서 서로 짝이 맞는지 확인
3. 오른쪽 괄호를 만났는데 stack이 비어있거나, pop한 문자가 다르면 검사 실패
4. 모든 괄호 검사가 끝난 다음, stack을 봤는데 stack이 안비워져 있다면 검사 실패

int check_bracket(const char* str) {
	stack s;
	char ch, pop_ch; // ch(괄호 저장) = [, {, (, ), }, ] -- pop_ch(stack에서 왼쪽 괄호 리턴) = [, {, (
	int n = strlen(str); // 문자열 str의 길이
	init_stack(&s); // 스택 초기화

	for (int i = 0; i < n; i++) {
		ch = str[i];
		switch (ch) { 
		case '[' : case '{' : case '(':
			push(&s, ch);
			break;
		case ')' : case '}' : case']': 
			if (is_empty(&s)) return 1; // 1 (괄호 검사 실패) 리턴
			else {
				pop_ch = pop(&s);
				if ((ch == ')' && pop_ch != '(') || (ch == '}' && pop_ch != '{') || (ch == ']' && pop_ch != '[')) // 서로 괄호가 짝이 안맞을 경우
					return 1; // 1 (괄호 검사 실패) 리턴
			}
			break;
		}
	}
	if (!is_empty(&s)) return 1; // push, pop을 통해서 비교를 했는데 아직 스택에서 pop되지 않은 괄호가 있으면 검사 실패
	return 0; // 0 (괄호 검사 성공) 리턴
}

 

※ Example

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 문자열 괄호 검사 [] {} ()

#define MAX_STACK_SIZE 1000

typedef char element;

typedef struct {
	int top;
	element stack[MAX_STACK_SIZE];
}stack;

void init_stack(stack* s) {
	s->top = -1;
}

int is_full(stack* s) {
	return s->top == MAX_STACK_SIZE - 1;
}

int is_empty(stack* s) {
	return s->top == -1;
}

void push(stack* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "Error : Stack is full!!");
		return;
	}
	else s->stack[++(s->top)] = item;
}

element pop(stack* s) {
	if (is_empty(s)) {
		fprintf(stderr, "Error : Stack is empty!!");
		return;
	}
	else
		return s->stack[(s->top)--];
}

element peek(stack* s) {
	if (is_empty(s)) {
		fprintf(stderr, "Error : Stack is empty!!");
		return;
	}
	else
		return s->stack[s->top];
}

int check_bracket(const char* str) {
	stack s;
	char ch, pop_ch; // ch(괄호 저장) = [, {, (, ), }, ] -------- pop_ch(stack에서 왼쪽 괄호 리턴) = [, {, (
	int n = strlen(str); // 문자열 str의 길이
	init_stack(&s); // 스택 초기화

	for (int i = 0; i < n; i++) {
		ch = str[i];
		switch (ch) { 
		case '[' : case '{' : case '(':
			push(&s, ch);
			break;
		case ')' : case '}' : case']': 
			if (is_empty(&s)) return 1; // 1 (괄호 검사 실패) 리턴
			else {
				pop_ch = pop(&s);
				if ((ch == ')' && pop_ch != '(') || (ch == '}' && pop_ch != '{') || (ch == ']' && pop_ch != '[')) // 서로 괄호가 짝이 안맞을 경우
					return 1; // 1 (괄호 검사 실패) 리턴
			}
			break;
		}
	}
	if (!is_empty(&s)) return 1; // push, pop을 통해서 비교를 했는데 아직 스택에서 pop되지 않은 괄호가 있으면 검사 실패
	return 0; // 0 (괄호 검사 성공) 리턴
}

int main(void) {
	char* str1 = "[A{(i+1)}=0;]";
	char* str2 = "if((i==0)&&(j==0)";
	char* str3 = "[]{}()(){}[]";
	char* str4 = "[{()}]";

	if (check_bracket(str1) == 0)
		printf("%s : 괄호 검사 성공!!\n", str1);
	else
		printf("%s : 괄호 검사 실패!!\n", str1);

	if (check_bracket(str2) == 0)
		printf("%s : 괄호 검사 성공!!\n", str2);
	else
		printf("%s : 괄호 검사 실패!!\n", str2);

	if (check_bracket(str3) == 0)
		printf("%s : 괄호 검사 성공!!\n", str3);
	else
		printf("%s : 괄호 검사 실패!!\n", str3);

	if (check_bracket(str4) == 0)
		printf("%s : 괄호 검사 성공!!\n", str4);
	else
		printf("%s : 괄호 검사 실패!!\n", str4);

	return 0;
}