승섭 7/21

섭승이·2023년 7월 20일
개발일기자료구조
0

자료구조

목록 보기
5/12
post-custom-banner

Chapter 06. 스택(stack)

“스택” 이란 “먼저 들어간 것이 나중에 나온다!” 의 특성을 지닌 선형 자료구조의 일종이다.

스택은 선입선출 방식이 아닌 ‘후입선출’(LIFO) 의 방식으로 스택의 ADT는 상대적으로 정형화된 편이다.

  • push - 초코볼 통에 초코볼을 넣는다
  • pop - 초코볼 통에서 초코볼을 꺼낸다
  • peek - 이번에 꺼낼 초코볼의 색이 무엇인지 통 안을 들여다본다.
  • empty - 초코볼 통이 비었는지 확인한다.

이 정도가 있으며 한쪽이 막여있는 초코볼 통을 예시로 들어 쉽게 설명한 표이다.

스택 자료구조의 ADT

  • void StackInit(Stack * pstack);
    • 스택의 초기화를 진행한다.
    • 스택 생성 후 제일 먼저 호출되어야 하는 함수이다.
  • int SIsEmpty(Stack * pstack);
    • 스택이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.
  • void SPush(Stack * pstack, Data data);
    • 스택에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.
  • Data SPop(Stack * pstack);
    • 마지막에 저장된 요소를 삭제한다.
    • 삭제된 데이터는 반환이 된다.
    • 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.
  • Data SPeek(Stack * pstack);
    • 마지막에 저장된 요소를 반환하되 삭제하지 않는다.
    • 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

우선 스택의 구현을 보일텐데, 배열을 기반으로 하는 구현이다.

위 그림에서 주목할 것 두 가지는 다음과 같다.

  • 인덱스 0의 배열 요소가 ‘스택의 바닥’으로 정의되었다.
  • 마지막에 저장된 데이터의 위치를 기억해야 한다.

아래는 이를 기반으로 구현한 스택의 코드이다.

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

// 초기화할 멤버는 가장 마지막에 저장된 데이터의 위치를 가리키는 topIndex 하나이다.
void StackInit(Stack * pstack)
{
	pstack->topIndex = -1; // topIndex의 -1은 빈 상태를 의미함
}

// 스택이 비어있는지 확인할 때 호출하는 함수이다.
int SIsEmpty(Stack * pstack)
{
	if(pstack->topIndex == -1)
		return TRUE;
	else
		return FALSE;
}

// push 연산 담당 함수
void SPush(Stack * pstack, Data data)
{
	pstack->topIndex += 1; // 데이터 추가를 위한 인덱스 값 증가
	pstack->stackArr[pstack->topIndex] = data; // 데이터 저장
}

// pop 연산 담당 함수
Data SPop(Stack * pstack)
{
	int rIdx;

	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	rIdx = pstack->topIndex; // 삭제할 데이터가 저장된 인덱스 값 저장
	pstack->topIndex -= 1; // pop 연산의 결과로 topIndex 값 하나 감소

	return pstack->stackArr[rIdx]; // 삭제되는 데이터 반환
}

// peek 연산 담당 함수
Data SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack))
	{
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->stackArr[pstack->topIndex]; // 맨 위에 저장된 데이터 반환
}

다음으로 연결 리스트 기반으로 스택을 구현해보겠다.

따라서 연결 리스트가 갖는 특성이 그대로 스택에 반영된다.

“스택도 연결 리스트이다. 다만 저장된 순서의 역순으로 조회(삭제)가 가능한 연결 리스트일 뿐이다!”

결국 새로운 노드를 꼬리가 아닌 머리에 추가한 형태로 구현한 연결 리스트이다.

위의 그림과 같은 메모리 구조를 바탕으로 push 연산과 pop 연산이 포함된 ADT를 갖는다면 이것이 스택이 되는 것이다.

아래는 이를 기반으로 구현한 스택의 코드이다.

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

// 스택을 초기화 해주는 함수
void StackInit(Stack * pstack)
{
	pstack->head = NULL; // 포인터 변수 head는 NULL로 초기화한다.
}

// 스택이 비어있는지 확인하는 함수
int SIsEmpty(Stack * pstack)
{
	if(pstack->head == NULL)
		return TRUE;
	else
		return FALSE;
}

// push 연산 담당 함수
void SPush(Stack * pstack, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성

	newNode->data = data; // 새 노드에 데이터 저장
	newNode->next = pstack->head; // 새 노드가 최근에 추가된 노드를 가리킴

	pstack->head = newNode; // 포인터 변수 head가 새 노드를 가리킴
}

// pop 연산 담당 함수
Data SPop(Stack * pstack)
{
	Data rdata;
	Node * rnode;

	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	rdata = pstack->head->data; // 삭제할 노드의 데이터를 임시로 저장
	rnode = pstack->head; // 삭제할 노드의 주소 값을 임시로 저장

	pstack->head = pstack->head->next; // 삭제할 노드의 다음 노드를 head가 가리킴
	free(rnode); // 노드 삭제

	return rdata; // 삭제된 노드의 데이터 변환 
}

// peek 연산 담당 함수
Data SPeek(Stack * pstack)
{
	if(SIsEmpty(pstack)) {
		printf("Stack Memory Error!");
		exit(-1);
	}

	return pstack->head->data; // head 가 가리키는 노드에 저장된 데이터 반환
}

계산기 프로그램 구현

  1. 소괄호를 파악하여 그 부분을 먼저 연산한다.
  2. 연산자의 우선순위를 근거로 연산의 순위를 결정한다.

계산기 프로그램을 구현하기 위해서는 중위, 전위, 후위 표기법에 대해 알아야한다

  • 중위 표기법(infix notation) - 5 + 2 / 7
  • 전위 표기법(prefix notation) - + 5 / 2 7
  • 후위 표기법(postfix notation) - 5 2 7 / +

우리가 주로 사용하는 중위 표기법에는 수식의 연산 순서에 대한 정보가 담겨있지 않으므로 전위나 후기표기법으로 바꾼 후(연산자가 자리한 위치로 우선순위 판별 가능) 계산하는 과정이 필요하다.

따라서 스택을 이용해 중위 표기법을 후위 표기법으로 바꾸는 과정을 진행한다.

2가지로 나눌 수 있는데

  • 쟁반에 위치한 연산자의 우선순위가 높다면
    • 쟁반에 위치한 연산자를 꺼내서 변환된 수식이 위치할 자리로 옮긴다.
    • 그리고 새 연산자는 쟁반으로 옮긴다.
  • 쟁반에 위치한 연산자의 우선순위가 낮다면
    • 쟁반에 위치한 연산자의 위에 새 연산자를 쌓는다.

소괄호를 고려해도 동일한 방식으로 진행되는데 ‘(’가 나오면 그 안에 들어있는 연산자를 스택에 쌓고 ‘)’ 가 나오게 되면 그 안에 들어있는 연산자를 모두 빼내는데 연산자를 넣을 때 연산자의 우선순위를 적용한다. 

#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "ListBaseStack.h"

// 연산자의 우선순위 정보를 정수의 형태로 반환하는 함수
int GetOpPrec(char op)
{
	switch(op)
	{
	// 가장 높은 연산의 우선 순위
	case '*':
	case '/':
		return 5;
	// 5보다 작고 1보다 높은 연산의 우선 순위
	case '+':
	case '-':
		return 3;
	// 가장 낮은 연산의 우선순위(항상 바닥에 깔려야함)
	case '(':
		return 1;
	}

	return -1; // 등록되지 않은 연산자임을 알림
}

// 연산자의 우선순위를 비교하여 그 결과를 반환하는 함수
int WhoPrecOp(char op1, char op2)
{
	int op1Prec = GetOpPrec(op1);
	int op2Prec = GetOpPrec(op2);

	if(op1Prec > op2Prec)
		return 1;
	else if(op1Prec < op2Prec)
		return -1;
	else
		return 0;
}

// 중위 표기법을 후위 표기법으로 바꾸어주는 함수
void ConvToRPNExp(char exp[])
{
	Stack stack;
	int expLen = strlen(exp);
	char * convExp = (char*)malloc(expLen+1); // 변환된 수식을 담을 공간 마련

	int i, idx=0;
	char tok, popOp;
	
	memset(convExp, 0, sizeof(char)*expLen+1); // 할당된 배열을 0으로 초기화
	StackInit(&stack);

	for(i=0; i<expLen; i++)
	{
		tok = exp[i]; // exp로 전달된 수식을 한 문자씩 tok에 저장
		if(isdigit(tok)) // tok에 저장된 문자가 숫자인지 확인
		{
			convExp[idx++] = tok; // 숫자이면 배열 convExp에 그냥 저장
		}
		else
		{
			switch(tok)
			{
			// 여는 소괄호라면 스택에 쌓는다
			case '(':
				SPush(&stack, tok); 
				break;
			// 닫는 소괄호라면 '(' 가 나올때까지 반복
			case ')':
				while(1)
				{
					popOp = SPop(&stack); // 스택에서 연산자를 꺼냄
					if(popOp == '(')
						break;
					convExp[idx++] = popOp; // 배열 convExp 에 저장
				}
				break;

			case '+': case '-': 
			case '*': case '/':
				while(!SIsEmpty(&stack) && 
						WhoPrecOp(SPeek(&stack), tok) >= 0) // 스택이 비어있어있지 않고, 연산자 우선순위가 스택에 들어있는 연산자가 더 높은 경우
					convExp[idx++] = SPop(&stack); // 스택에서 꺼내어 convExp 에 넣어줌

				SPush(&stack, tok); // 연산자 tok를 스택에 넣어줌
				break;
			}
		}
	}

	while(!SIsEmpty(&stack)) // 스택에 남아 있는 모든 연산자를 
		convExp[idx++] = SPop(&stack); // 배열 convExp 로 옮김

	strcpy(exp, convExp); // 변환된 수식을 exp에 복사
	free(convExp); // convExp는 소멸시킴
}

위의 코드로 중위 표기식을 후위 표기식으로 바꾸는 과정을 완료하였으니 남은 과정으로는 후위 표기법으로 표현된 수식을 계산하는 프로그램을 구현하면 완성이다!

후위 표기법으로 표현된 수식을 계산하는 프로그램

  1. 피연산자는 무조건 스택으로 옮긴다.
  2. 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내서 계산을 한다.
  3. 계산결과는 다시 스택에 넣는다.

위의 그림과 같은 방식으로 진행되며 이를 코드로 나타내면

#include <string.h>
#include <ctype.h>
#include "ListBaseStack.h"

// 후위 표기법의 수식을 계산하여 그 결과를 반환하는 함수
int EvalRPNExp(char exp[])
{
	Stack stack;
	int expLen = strlen(exp);
	int i;
	char tok, op1, op2;

	StackInit(&stack);

	for(i=0; i<expLen; i++)
	{
		tok = exp[i];

		if(isdigit(tok))
		{
			SPush(&stack, tok - '0');     // tok이 피연산자라면 stack에 넣는다
		}
		else
		{
			op2 = SPop(&stack);     // 두번째 피연산자
			op1 = SPop(&stack);     // 첫번째 피연산자

			switch(tok)
			{
			case '+':
				SPush(&stack, op1+op2);
				break;
			case '-':
				SPush(&stack, op1-op2);
				break;
			case '*':
				SPush(&stack, op1*op2);
				break;
			case '/':
				SPush(&stack, op1/op2);
				break;
			}
		}
	}
	return SPop(&stack);
}

앞서 보여준 2개의 주요한 기능을 가지고 있는 함수를 활용하여 계산기를 구현 완료 하였다.

profile
섭승이
초보개발자입니당
이전 포스트

승섭 7/20

다음 포스트

승섭 7/22

post-custom-banner

1개의 댓글

comment-user-thumbnail
happy
2023년 7월 20일

소중한 정보 감사드립니다!

답글 달기