함수 전문

////////////////////////////////////////////////////////////
int balanced(char *expression)
{
	Stack *s = malloc(sizeof(Stack));
//	s->ll.head = NULL;
//	s->ll.size = 0;

	int idx = 0;
	char c = expression[idx];
	while (c != '\\0')
	{
		if (c == ')')
		{
			if (peek(s) == '(')
				pop(s);
		}
		else if (c == ']')
		{
			if (peek(s) == '[')
				pop(s);
		}
		else if (c == '}')
		{
			if (peek(s) == '{')
				pop(s);
		}
		else if (c == '(' || c == '[' || c == '{')
		{
			push(s, c);
		}
		else
		{
			return 0;
		}
		idx++;
		c = expression[idx];
	}

	if (!isEmptyStack(s))
	{
		removeAllItemsFromStack(s);
		free(s);
		return 1;
	}
	else
	{
		removeAllItemsFromStack(s);
		free(s);
		return 0;
	}
}

////////////////////////////////////////////////////////////

초기화 문제

typedef struct stack
{
	LinkedList ll;
} Stack; // You should not change the definition of stack

위와 같은 구조체를

Stack *s = malloc(sizeof(Stack));

위와 같이 동적 할당하였다.

이러면 힙 영역에 LinkedList 구조체만큼의 빈 영역이 할당된다.

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList; // You should not change the definition of LinkedList

LinkedList 구조체의 멤버 변수들은 위와 같다. 이 상태에서 멤버 변수들을 초기화해주지 않으면 *head는 쓰레기 값을 가리키게 된다. 하지만 맨 처음에 push(), peek(), pop()은 정상적으로 작동되는 듯 보였으나, 디버깅 시 free()에서 자꾸 세그멘테이션 폴트가 발생하게 되었다.

왜 처음엔 정상적으로 작동되는 듯 보였나?

push() 함수는 내부적으로 insertNode() 함수를 작동시킨다.

if (ll->head == NULL || index == 0) {
    cur = ll->head;
    ll->head = malloc(sizeof(ListNode));
    ll->head->item = value;
    ll->head->next = cur;  // ⚠️ cur는 쓰레기값
}

맨 앞에 push() 할 때는 위와 같이 동작하는데, ll→head는 현재 쓰레기 값이므로 cur 또한 같은 곳을 가리키게 되었다. 그 쓰레기 주소에 새로 ListNode를 할당해주었고, 그 값을 초기화 해 주었다. 하지만 여전히 ListNode의 next는 쓰레기 값이지만, 할당을 해 주어서 ll→head 자체는 유효한 주소가 되어버렸다.

만약 peek()이나 pop()을 먼저 실행시켰다면, 쓰레기 값을 역참조해서 바로 세그멘테이션 폴트가 발생했을 것이다.

그럼 push 연산 후 free 할 때 왜 세그멘테이션 폴트가 발생했나?

사실 removeAllItemsFromStack(s) 에서 이미 ll.head→next 안에서 여전히 존재하던 쓰레기 값을 따라가면서 free를 하려고 했기 때문에 문제가 발생했음. 컴파일러가 세그멘테이션 폴트를 한발 늦게 발생시켜주어서 free에서 발생했다고 착각하는 것 !!

디버깅 시에만 발생하는 이유는?

쓰레기 주소가 우연히 쓸만한 주소면 운영체제는 그냥 실행을 허용함 하지만 디버깅 툴은 그런 쓰레기 값을 예민하게 감지하고 에러를 발생시킴