스택·큐 Q7. 괄호 균형 검사하기

자료구조 C 실습 · 스택과 큐 · Q7

스택·큐 Q7. 괄호 균형 검사하기

C 파일 하나를 문제 하나로 보고 정리한 풀이 글이다.
이번 글은 함수가 실제로 어떤 연결, 순회, 변환을 수행하는지에 초점을 맞춘다.

Section C Stack and Queue balanced

문자열 안의 괄호 `()[]{}` 가 올바르게 짝지어졌는지 스택으로 검사하는 문제다. 열린 괄호를 스택에 쌓고, 닫힌 괄호를 만날 때마다 top과 짝이 맞는지 확인하는 것이 전형적인 스택 활용 패턴이다.

한눈에 보는 문제 정보

원본 파일: C:\Users\cedis\OneDrive\문서\ANTIWORK\WEKK6~~~~~\data_structures_docker\Data-Structures\Stack_and_Queue\Q7_C_SQ.c

대상 함수: balanced

카테고리: 스택과 큐

문제에서 요구한 것

메뉴와 출력 문자열을 보면 이 파일은 특정 자료구조 연산 하나를 직접 구현하도록 만든 실습 문제다. 입력 흐름은 아래처럼 정리할 수 있다.

• 1: Enter a string
• 2: Check whether expressions comprised of the characters ()[]{} is balanced
• 0: Quit
• Enter expressions without spaces to check whether it is balanced or not
• not balanced!
• balanced!

핵심 구현 흐름

STEP 1

문자열을 왼쪽부터 읽으며 열린 괄호는 push한다.

STEP 2

닫힌 괄호를 만나면 스택이 비었는지와 top이 대응 괄호인지 검사한다.

STEP 3

끝까지 읽은 뒤 스택이 비어 있으면 균형 잡힌 수식으로 판단한다.

핵심 코드

문제 파일 전체를 다 옮기기보다, 실제로 구현해야 했던 함수만 뽑아서 보면 로직이 더 선명하게 들어온다.

핵심 코드: balanced

int balanced(char *expression)
{
	Stack s;
	int i = 0;

	s.ll.head = NULL;
	s.ll.size = 0;

	while (expression[i] != '\0')
	{
		if (expression[i] == '(' || expression[i] == '[' || expression[i] == '{')
		{
			push(&s, expression[i]);
		}
		else if (expression[i] == ')')
		{
			if (isEmptyStack(&s) || peek(&s) != '(')
				return 1;
			pop(&s);
		}
		else if (expression[i] == ']')
		{
			if (isEmptyStack(&s) || peek(&s) != '[')
				return 1;
			pop(&s);
		}
		else if (expression[i] == '}')
		{
			if (isEmptyStack(&s) || peek(&s) != '{')
				return 1;
			pop(&s);
		}
		i++;
	}

	if (isEmptyStack(&s))
		return 0;
	else
		return 1;
}

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

void removeAllItemsFromStack(Stack *s)
{
	if (s == NULL)
		return;
	while (s->ll.head != NULL)
	{
		pop(s);
	}
}


void removeAllItems(LinkedList *ll)
{
	ListNode *cur = ll->head;
	ListNode *tmp;

	while (cur != NULL){
		tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	ll->head = NULL;
	ll->size = 0;
}

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

void push(Stack *s, int item)
{
	insertNode(&(s->ll), 0, item);
}

int pop(Stack *s)
{
	int item;
	if (s->ll.head != NULL)
	{
		item = ((s->ll).head)->item;
		removeNode(&(s->ll), 0);
		return item;
	}
	else
		return MIN_INT;
}

int peek(Stack *s){
    if(isEmptyStack(s))
        return MIN_INT;
    else
        return ((s->ll).head)->item;
}

int isEmptyStack(Stack *s)
{
	if ((s->ll).size == 0)
		return 1;
	else
		return 0;
}


void printList(LinkedList *ll){

	ListNode *cur;
	if (ll == NULL)
		return;

	cur = ll->head;
	if (cur == NULL)
		printf("Empty");
	while (cur != NULL)
	{
		printf("%d ", cur->item);
		cur = cur->next;
	}
	printf("\n");
}

ListNode * findNode(LinkedList *ll, int index){

	ListNode *temp;

	if (ll == NULL || index < 0 || index >= ll->size)
		return NULL;

	temp = ll->head;

	if (temp == NULL || index < 0)
		return NULL;

	while (index > 0){
		temp = temp->next;
		if (temp == NULL)
			return NULL;
		index--;
	}

	return temp;
}

int insertNode(LinkedList *ll, int index, int value){

	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index > ll->size + 1)
		return -1;

	// If empty list or inserting first node, need to update head pointer
	if (ll->head == NULL || index == 0){
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		if (ll->head == NULL)
		{
			exit(0);
		}
		ll->head->item = value;
		ll->head->next = cur;
		ll->size++;
		return 0;
	}


	// Find the nodes before and at the target position
	// Create a new node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL){
		cur = pre->next;
		pre->next = malloc(sizeof(ListNode));
		if (pre->next == NULL)
		{
			exit(0);
		}
		pre->next->item = value;
		pre->next->next = cur;
		ll->size++;
		return 0;
	}

	return -1;
}


int removeNode(LinkedList *ll, int index){

	ListNode *pre, *cur;

	// Highest index we can remove is size-1
	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;

	// If removing first node, need to update head pointer
	if (index == 0){
		cur = ll->head->next;
		free(ll->head);
		ll->head = cur;
		ll->size--;
		return 0;
	}

	// Find the nodes before and after the target position
	// Free the target node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL){

		if (pre->next == NULL)
			return -1;

		cur = pre->next;
		pre->next = cur->next;
		free(cur);
		ll->size--;
		return 0;
	}

	return -1;
}

구현할 때 체크할 점

• 닫는 괄호를 먼저 만났을 때 empty 검사를 하지 않으면 바로 잘못된다.
• 문자열 끝까지 읽은 뒤 남은 열린 괄호가 없는지도 마지막에 확인해야 한다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 열린 괄호를 스택에 쌓고, 닫힌 괄호를 만날 때마다 top과 짝이 맞는지 확인하는 것이 전형적인 스택 활용 패턴이다.

같은 카테고리의 다른 문제와 함께 보면, 연결 리스트에서는 재배선, 스택과 큐에서는 순서 제어, 트리에서는 재귀 순회라는 감각이 반복해서 나온다는 점도 같이 볼 수 있다.