[C] 자료구조 - Stack(괄호 검사 알고리즘)

<Stack 자료구조>

Stack: 가장 최근에 들어온 데이터가 가장 먼저 나감

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

typedef char element; // char 은 int 등으로 대체 가능
typedef struct {
	element data[MAX_STACK_SIZE];
	int top;
} StackType; // 스택 구조체 정의

void init_stack(StackType* s) {
	s->top = -1;
} // 스택 초기화 함수 (구조체 포인터의 멤버는 s->이런식)

int is_empty(StackType* s) {
	return (s->top == -1);
}// 스택 비었는지 검사하는 함수, 빈 상태 return

int is_full(StackType* s) {
	return (s->top == (MAX_STACK_SIZE - 1));
}// 스택 꽉 찼는지 검사하는 함수, 꽉 찬 상태 return

void push(StackType* s, element item) {
	if (is_full(s)) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}// 스택 꽉 찼으면 에러 return
	else s->data[++(s->top)] = item;
}// 스택+1 하고 집어넣기

element pop(StackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}// 스택 비었으면 에러 return
	else return s->data[(s->top)--];
}// 스택에서 꺼내고 -1하기

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


	for (i = 0; i < n; i++) {
		ch = in[i];//스택[0]에 문자열 0번째 저장
		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;
    
}

 

- 문자열은 char * pointer = "happy" 에 저장

- 포인터에 넘길 때만 &pointer(주소)로 사용하고 나머지는 배열 이름마냥 pointer로 쓴다