[TIL/크래프톤 정글9기] 37일차(C언어 스택)

오늘의 문제를 스택과 큐를 활용하는 문제로 알고리즘에서 많이 나오는 괄호가 입력되면 밸런스가 맞는지 안 맞는지 확인하는 함수를 작성하는 문제이다.

7. balanced (괄호 균형 검사)

문제 설명

()[]{}로 구성된 표현식이 균형잡혀 있는지 판단하는 C 함수 balanced()를 작성하시오.

함수 프로토타입

int balanced(char *expression);

균형잡힌 표현식 예시

()
([])
{[]()[]}

균형잡히지 않은 표현식 예시

{{)]
[({{)])

샘플 입출력

1: Enter a string
2: Check whether expressions comprised of the characters ()[]{} is balanced
0: Quit

Please input your choice(1/0): 1
Enter expressions without spaces to check whether it is balanced or not: {[]()[]}
{[]()[]}
balanced!

Please input your choice(1/0): 0

Please input your choice(1/0): 1
Enter expressions without spaces to check whether it is balanced or not: [({{)])
[({{)])
not balanced!

Please input your choice(1/0): 0

함수 작성 아이디어

• 괄호의 짝이 맞는지 안 맞는지 확인을 하려면 입력 받은 괄호 문자열을 while문을 사용하여 반복
• 마지막엔 다음 문자로 이동을 해 마지막에 '\0' 문자가 나오면 반복문이 종료
• 입력받은 문자열은 여는 괄호면 스택에 푸쉬를 하고 닫는 괄호열들은 스택에 있는 탑이 자기 자신과 짝이 맞는지 확인하고 짝이 맞으면 Pop을 하여 스택을 비우기
• 반복문이 끝이나면 스택에 남아있는 문자들이 없으면 균형이 맞음. 만약 스택에 아직 남아 있다면 균형이 맞지 않으므로 not balanced를 출력

작성 함수

int balanced(char *expression)
{
	// 스택 초기화, head와 size도 초기화 해줘야함, 
	Stack *myStack = malloc(sizeof(Stack));
	myStack->ll.head = NULL;
	myStack->ll.size = 0;

	// 입력받은 문자열의 '\0' 까지 반복 {}{}\0
	while (*expression)
	{	
		// 괄호를 시작하는 문자열이면 스택에 추가
		if (*expression == '(' || *expression == '{' || *expression == '['){
			push(myStack, *expression);
		} 
		// 괄호를 닫는 문자열이면
		else {
			// 닫는 괄호인데 스택이 비어있으면, 짝이 맞지 않으므로 not balanced (1 리턴)
			if (isEmptyStack(myStack)) {
				return 1;
			} 
			// 닫는 괄호와 스택의 top 괄호가 짝이 맞으면 pop
			if (*expression == ')' && peek(myStack) == '(' || *expression == '}' && peek(myStack) == '{' || *expression == ']' && peek(myStack) == '['){
				pop(myStack);
			} 
			// 짝이 맞지 않으므로 not balance 리턴 1
			else {
				return 1;
			}
		}
		// 다음 문자로 이동
		expression++;
	}

	// 결과 저장용 변수 
	int result;

	// 스택이 비어 있으면 balanced (모든 괄호 짝이 맞음), 비어있지 않으면 not balanced, 처음부터 비어있는 건 위에서 처리  
	if (isEmptyStack(myStack)){
		result = 0;
	} else {
		result = 1;
	}

	//동적할당한 스택 메모리 프리
	free(myStack);

	// 결과 리턴
	return result;
}

전체 코드

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

/* CE1007/CZ1007 Data Structures
Lab Test: Section C - Stack and Queue Questions
Purpose: Implementing the required functions for Question 7 */

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

#include <stdio.h>
#include <stdlib.h>

#define MIN_INT -1000

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

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;	// You should not change the definition of ListNode

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


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

///////////////////////// function prototypes ////////////////////////////////////

// You should not change the prototypes of these functions
int balanced(char *expression);

void push(Stack *s, int item);
int pop(Stack *s);
int peek(Stack *s);
int isEmptyStack(Stack *s);
void removeAllItemsFromStack(Stack *s);

void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);

//////////////////////////// main() //////////////////////////////////////////////

int main()
{
	char str[256];
	// int c, i;
	int c = 1;

	LinkedList ll;
	Stack s;

	// Initialize the linked list as an empty linked list
	ll.head = NULL;
	ll.size = 0;

	// Initalize the stack as an empty stack
	s.ll.head = NULL;
	s.ll.size = 0;

	printf("1: Enter a string:\n");
	printf("2: Check whether expressions comprised of the characters ()[]{} is balanced:\n");
	printf("0: Quit:\n");


	while (c != 0)
	{
		printf("Please input your choice(1/2/0): ");
		scanf("%d", &c);

		switch (c)
		{
		case 1:
			printf("Enter expressions without spaces to check whether it is balanced or not: ");
			scanf("%s", str);
			break;
        case 2:
            if(balanced(str))
                printf("not balanced!\n");
            else
                printf("balanced!\n");
			break;
		case 0:
			break;
		default:
			printf("Choice unknown;\n");
			break;
		}

	}

	return 0;
}

////////////////////////////////////////////////////////////
int balanced(char *expression)
{
	// 스택 초기화, head와 size도 초기화 해줘야함, 
	Stack *myStack = malloc(sizeof(Stack));
	// myStack->ll.head = NULL;
	// myStack->ll.size = 0;

	// 입력받은 문자열의 '\0' 까지 반복 {}{}\0
	while (*expression)
	{	
		// 괄호를 시작하는 문자열이면 스택에 추가
		if (*expression == '(' || *expression == '{' || *expression == '['){
			push(myStack, *expression);
		} 
		// 괄호를 닫는 문자열이면
		else {
			// 닫는 괄호인데 스택이 비어있으면, 짝이 맞지 않으므로 not balanced (1 리턴)
			if (isEmptyStack(myStack)) {
				return 1;
			} 
			// 닫는 괄호와 스택의 top 괄호가 짝이 맞으면 pop
			if (*expression == ')' && peek(myStack) == '(' || *expression == '}' && peek(myStack) == '{' || *expression == ']' && peek(myStack) == '['){
				pop(myStack);
			} 
			// 짝이 맞지 않으므로 not balance 리턴 1
			else {
				return 1;
			}
		}
		// 다음 문자로 이동
		expression++;
	}

	// 결과 저장용 변수 
	int result;

	// 스택이 비어 있으면 balanced (모든 괄호 짝이 맞음), 비어있지 않으면 not balanced, 처음부터 비어있는 건 위에서 처리  
	if (isEmptyStack(myStack)){
		result = 0;
	} else {
		result = 1;
	}

	//동적할당한 스택 메모리 프리
	free(myStack);

	// 결과 리턴
	return result;
}
////////////////////////////////////////////////////////////

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;
}