괄호검사문제[스택]

스택의 구조를 잘 파악할수있는 대표적인 문제인 괄호검사 문제입니다

---

조건

• 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 됨
• 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 됨
• 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호의 쌍은 서로를 교차하면 안됨

---

스택구조

		( (3)	pop('(' == ')')
	[ (2)	[ (2)	[ (2)	pop('[' == ']')
{ (1)	{ (1)	{ (1)	{ (1)	{ (1)	pop('{' == '}')

 

괄호검사를 하게 되면 위 스택의 구조처럼 됩니다

스택은 FIFO구조로 가장 최근에 온 데이터가 가장 먼저 나가게 됩니다

왼쪽 괄호인 (1), (2), (3)이 push()함수를 통해서 순차적으로 스택에 쌓이게 되며 오른쪽 괄호가 나오면 스택에서 가장 나중에 들어온 순서부터 차례대로 pop()하면서 오른쪽 괄호와 일치하는지 비교하며 최종적으로는 스택이 비어지게 됩니다

---

StackType구조체를 생성

*data가 element를 가리키는 포인터로 생성[배열역할]

현재 크기정보를 알수있는 capacity와 스택의 위치를 가리키는 top을 선언

---

init_stack : 스택초기화 [top이 -1인 이유 -> 0으로 초기화 하면 0번째 인덱스에 데이터가 있는것을 의미하기 때문임]

is_empty : 공백상태확인

is_full : 포화상태확인

data : 동적할당을 하여 1개의 요소를 저장할 수 있는 스택의 크기확보

---

push : 스택에 데이터값을 집어넣음

         먼저포화상태확인 -> 포화상태이면 현재크기를 2배늘리고 data의 크기를 realloc을 통해 동적할당->공간확보

         스택의 위치를 1증가하여 data에 값 저장

pop : 스택에 데이터값을 꺼냄

        먼저공백상태확인 -> 공백상태이면(-1) 에러메시지 출력하고 종료, 아니라면 스택의 위치를 감소시켜 데이터 꺼냄

---

실질적으로 괄호일치여부를 검사하는 코드

반복문을 돌리며 왼쪽괄호가 나오면 스택에 저장하여 오른쪽 괄호와 비교하여 리턴값 반환

---

 

참고문헌 : c언어로 쉽게 배우는 자료구조