스택의 적용

이전 포스트에서 사용한 linkedStack 을 이용한 헤더파일

#ifndef _LINKEDSTACK_
#define _LINKEDSTACK_

typedef struct LinkedStackNodetype {
	char data;
	struct LinkedStackNodetype *pLink;		//링크
}	LinkedStackNode;

typedef struct LinkedStacktype {
	int currentCount;
	LinkedStackNode *pTop;				// 탑 노드의 포인터
}	LinkedStack;

LinkedStack	*createLinkedStack(void);
int	pushLS(LinkedStack *pStack, char data);
int	isLinkedStackEmpty(LinkedStack *pStack);
LinkedStackNode *popLS(LinkedStack *pStack);
LinkedStackNode *peekLS(LinkedStack *pStack);
void	deleteLinkedStack(LinkedStack *pStack);
void	displayLinkedStack(LinkedStack *pStack);

#endif

을 사용하여 간단한 예제를 만들어보자

 

1. 역순인 문자열 만들기

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linkedstack.h"

char	*reverseString(char *pSource)
{
	char	*pReturn = NULL;
	int	i = 0, size = 0;
	LinkedStack	*pStack = NULL;
	LinkedStackNode	*pNode = NULL;

	pStack = createLinkedStack();
	if (pStack != NULL)
	{
		while (pSource[size] != 0)
		{
			pushLS(pStack, pSource[size]);
			size++;
		}

		pReturn = (char *)malloc(sizeof(char) * (size + 1));
		memset(pReturn, 0, sizeof(char) * (size + 1));
		while (i < size)
		{
			pNode = popLS(pStack);
			if (pNode != NULL)
			{
				pReturn[i] = pNode->data;
				free(pNode);			// pop된 노드에 노드에 대한 메모리 해제
			}
			i++;
		}
		deleteLinkedStack(pStack);
	}

	return (pReturn);
}

int	main(void)
{
	char	szSource[] = "ABCD";
	char	*pszReverse = reverseString(szSource);

	if (pszReverse != NULL)
	{
		printf("[%s]=> [%s]\n", szSource, pszReverse);

		free(pszReverse);				// 함수 호출 결과로 전달받은 문자열 메모리  해제
	}

	return (0);
}

 

2. 수식에서 괄호 검사하기

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

int	checkBracketMatching(char *pSource)
{
	int	ret = 0, i = 0;
	char symbol = '\0', checkSymbol = '\0';
	LinkedStack	*pStack = NULL;
	LinkedStackNode	*pNode = NULL;

	pStack = createLinkedStack();
	if (pStack != NULL)
	{
		while (pSource[i] != 0 && ret == 0)
		{
			symbol = pSource[i];
			switch (symbol)
			{
				case '(':
				case '[':
				case '{':
					pushLS(pStack, symbol);		// 여는 괄호 만나면 push
					break;
				case ')':
				case ']':
				case '}':
					pNode = popLS(pStack);		// 닫는 괄호 만나면 pop
					if (pNode == NULL)			// 닫는 괄호가 더 많은 경우
						ret = 1;
					else
					{
						checkSymbol = pNode->data;			// 마지막 여는 괄호와 첫번째 닫는 괄호 비교
						if ((symbol == ')' && checkSymbol == '(')
							|| (symbol == ']' && checkSymbol == '[')
							|| (symbol == '}' && checkSymbol == '{'))
								ret = 0;
						else					// 괄호의 쌍이 맞지 않을 경우
							ret = 2;
					}
					free(pNode);
					break;
			}
			i++;
		}

		if (ret == 0 && isLinkedStackEmpty(pStack) == 0)	// 여는 괄호가 더 많은 경우
			ret = 3;

		deleteLinkedStack(pStack);
	}

	return (ret);
}

int main(void)
{
	int		checkResult = 0, i = 0;
	char	szExpresstionStr[][50] = {
		"( A + B ) * C",
		"{ ( A + B ) * C } * D",
		"( A + B ) * C )",			// 여는 괄호 부족
		"( ( A + B ) * C", 			// 닫는 괄호 부족
		"{ ( A + B } ) * C * D"		// 괄호 문자가 맞지 않음
	};

	for (i = 0; i < sizeof(szExpresstionStr) / sizeof(szExpresstionStr[0]); i++)
	{
		checkResult = checkBracketMatching(szExpresstionStr[i]);
		if (checkResult == 0)
			printf("SUCCESS, %s\n", szExpresstionStr[i]);
		else
			printf("FAIL-[%d], %s\n", checkResult, szExpresstionStr[i]);
	}

	return (0);
}