Data Structure & Algorithm/Data Structure
[Data Structure] Chapter 06: 스택(Stack)
시데브
2023. 8. 15. 15:27
LIFO구조를 가지는 자료구조인 stack에 대해 이해하고, stack을 이용해 계산기를 구현해보자.
스택
- 스택은 가장 마지막에 들어간 데이터가 가장 먼저 나오는 후입선출, LIFO(Last-In, First-Out)의 자료구조를 가진다.
스택 자료구조의 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)
- 마지막에 저장된 요소를 반환하되 삭제하지 않는다.
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.
스택의 배열 기반 구현
- push: Top을 위로 한 칸 up, 해당 위치에 데이터 저장
- pop: Top이 가리키는 데이터를 반환하고, Top을 아래로 한 칸 down
파일명: ArrayBaseStack.h
#ifndef __AB_STACK_H__
#define __AB_STACK_H__
#define TRUE 1
#define FALSE 0
#define STACK_LEN 100
typedef int Data;
typedef struct _arrayStack
{
Data stackArr[STACK_LEN];
int topIndex;
} ArrayStack;
typedef ArrayStack Stack;
void StackInit(Stack * pstack); //스택의 초기화
int SIsEmpty(Stack * pstack); //스택이 비었는지 확인
void SPush(Stack * pstack, Data data); //스택의 push 연산
Data SPop(Stack * pstack); //스택의 pop 연산
Data SPeek(Stack * pstack); //스택의 peek 연산
#endif
파일명: ArrayBaseStack.c
#include <stdio.h>
#include <stdlib.h>
#include "ArrayBaseStack.h"
void StackInit(Stack * pstack)
{
pstack -> topIndex = -1;
}
int SIsEmpty(Stack * pstack)
{
if(pstack -> topIndex == -1)
return TRUE;
else
return FALSE;
}
void SPush(Stack * pstack, Data data)
{
pstack->topIndex+=1;
pstack->stackArr[pstack->topIndex] = data;
}
Data SPop(Stack * pstack)
{
int rIdx;
if(SIsEmpty(pstack))
{
printf("Stack Memory Error!");
exit(-1);
}
rIdx = pstack->topIndex;
pstack->topIndex-=1;
return pstack->stackArr[rIdx];
}
Data SPeek(Stack * pstack)
{
if(SIsEmpty(pstack))
{
printf("Stack Memory Error!");
exit(-1);
}
return pstack->stackArr[pstack->topIndex];
}
파일명: ArrayBaseStackMain.c
#include <stdio.h>
#include "ArrayBaseStack.h"
int main(void)
{
/***Stack의 생성 및 초기화***/
Stack stack;
StackInit(&stack);
/***데이터 넣기***/
SPush(&stack, 1); SPush(&stack, 2);
SPush(&stack, 3); SPush(&stack, 4);
SPush(&stack, 5);
/***데이터 꺼내기***/
while(!SIsEmpty(&stack))
printf("%d ", SPop(&stack));
return 0;
}5 4 3 2 1
스택의 연결 리스트 기반 구현
파일명: ListBaseStack.h
#ifndef __LB_STACK_H__
#define __LB_STACK_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node * next;
} Node;
typedef struct _listStack
{
Node * head;
} ListStack;
typedef ListStack Stack;
void StackInit(Stack * pstack); //스택의 초기화
int SIsEmpty(Stack * pstack); //스택이 비었는지 확인
void SPush(Stack * pstack, Data data); //스택의 push 연산
Data SPop(Stack * pstack); //스택의 pop 연산
Data SPeek(Stack * pstack); //스택의 peek 연산
#endif
파일명: ListBaseStack.c
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"
void StackInit(Stack * pstack)
{
pstack->head = NULL;
}
int SIsEmpty(Stack * pstack)
{
if(pstack->head==NULL)
return TRUE;
else
return FALSE;
}
void SPush(Stack * pstack, Data data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = pstack->head;
pstack->head = newNode;
}
Data SPop(Stack * pstack)
{
if(SIsEmpty(pstack))
{
printf("Stack Memory Error!");
exit(-1);
}
Node * rpos = pstack->head;
Data rdata = rpos->data;
pstack->head=pstack->head->next;
free(rpos);
return rdata;
}
Data SPeek(Stack * pstack)
{
if(SIsEmpty(pstack))
{
printf("Stack Memory Error!");
exit(-1);
}
return pstack->head->data;
}
파일명: ListBaseStackMain.c
#include <stdio.h>
#include "ListBaseStack.h"
int main(void)
{
Stack stack;
StackInit(&stack);
SPush(&stack, 1); SPush(&stack, 2);
SPush(&stack, 3); SPush(&stack, 4);
SPush(&stack, 5);
while(!SIsEmpty(&stack))
printf("%d ", SPop(&stack));
return 0;
}5 4 3 2 1
문제 06-1
더보기
원형 연결 리스트를 이용해서 스택을 구현
- 이전에 구현했던 원형 연결 리스트의 헤더 파일과 함수 구현 파일을 그대로 가져온다.
- 스택의 구현이므로 함수 LNext는 안 써도 된다!
파일명: CLLBaseStack.h
#ifndef __CLL_STACK_H__
#define __CLL_STACK_H__
#include "CLinkedList.h"
typedef struct __CLLBaseStack
{
List * plist;
} CLLBaseStack;
typedef CLLBaseStack Stack;
void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);
void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);
#endif
파일명: CLLBaseStack.c
#include <stdio.h>
#include <stdlib.h>
#include "CLLBaseStack.h"
void StackInit(Stack * pstack)
{
pstack->plist = (List*)malloc(sizeof(List));
ListInit(pstack->plist);
}
int SIsEmpty(Stack * pstack)
{
if(LCount(pstack->plist)==0)
return TRUE;
else
return FALSE;
}
void SPush(Stack * pstack, Data data)
{
LInsertFront(pstack->plist, data);
}
Data SPop(Stack * pstack)
{
Data data;
LFirst(pstack->plist, &data);
LRemove(pstack->plist);
return data;
}
Data SPeek(Stack * pstack)
{
Data data;
LFirst(pstack->plist, &data);
return data;
}
파일명: CLLBaseStackMain.c
#include <stdio.h>
#include "CLLBaseStack.h"
int main(void)
{
Stack stack;
StackInit(&stack);
SPush(&stack, 1); SPush(&stack, 2);
SPush(&stack, 3); SPush(&stack, 4);
SPush(&stack, 5);
while(!SIsEmpty(&stack))
printf("%d ",SPop(&stack));
return 0;
}5 4 3 2 1
스택 자료구조를 이용한 계산기 프로그램 구현
- 소괄호 내부에 있는 연산을 먼저 진행한다.
- 연산자의 우선순위를 근거로 연산의 순위를 결정한다.
- 피연산자는 한 자리수 정수!
중위(infix), 전위(prefix), 후위(postfix) 표기법
- 중위 표기법(infix notation) -> 5+2/7
- 전위 표기법(prefix notation) -> +5/27
- 후위 표기법(postfix notation) -> 527/+
중위 표기법과 달리 전위 표기법과 후위 표기법은 연산 우선순위를 몰라도 올바른 연산 순서를 알 수 있다.
>> 사용자로부터 중위 표기법을 입력받아서 후위 표기법(혹은 전위 표기법)으로 변환 후에 연산 처리하도록 구현!!
중위 표기법의 후위 표기법으로의 변환
- 중위 표기법이 담긴 문자열 exp, 비어있는 스택 stack, 비어있는 문자열(후위 표기법이 담길 문자열) convExp
- exp의 왼쪽 구성요소부터 하나씩 읽어서 숫자면 convExp로 옮기고 연산자면 stack으로 옮긴다.
- stack에 연산자를 옮길 때, stack에 이미 위치한 연산자의 우선순위가 옮기려는 연산자보다 우선순위가 높거나 같다면 stack에 있던 연산자를 모두 conExp로 옮기고 stack을 채운다. stack의 연산자 우선순위가 낮을 경우 위에 그대로 쌓는다.
- exp의 모든 구성요소를 옮겼다면, stack에 쌓인 연산자를 모두 convExp로 옮긴다.
- ( 연산자의 경우 ) 연산자가 올 때까지 stack에서 우선순위가 가장 낮은 연산자로 취급된다.
- ) 연산자가 등장할 경우 ( 연산자부터 ) 연산자까지 쌓인 모든 연산자를 convExp로 옮긴다.
- ( ) 연산자는 역할이 끝나면 convExp로 옮기지 않고 사라진다.
중위 표기법의 후위 표기법으로의 변환하는 프로그램 구현
파일명: InfixToPostfix.h
#ifndef __INFIX_TO_POSTFIX_H__
#define __INFIX_TO_POSTFIX_H__
void ConvToRPNExp(char exp[]);
#endif
파일명: InfixToPostfix.c
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "ListBaseStack.h"
int GetOpPrec(char op)
{
switch (op)
{
case '*':
case '/':
return 5;
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); //void memset(void * ptr, int value, size_t num) -> value가 저장된 ptr 반환, 저장 실패시 NULL 반환
StackInit(&stack);
for(i=0; i<expLen; i++)
{
tok = exp[i];
if(isdigit(tok))
convExp[idx++] = tok;
else
{
switch(tok) //tok을 스택에 넣을지, 바로 옮길지 결정하는 구문
{
case '(':
SPush(&stack, tok);
break;
case ')':
while(1)
{
popOp = SPop(&stack);
if(popOp == '(')
break;
convExp[idx++] = popOp;
}
break;
case '+': case '-':
case '*': case '/':
while(!SIsEmpty(&stack) && WhoPrecOp(SPeek(&stack), tok) >= 0) //원래 있던 연산자가 우선순위 높거나 같으면
convExp[idx++] = SPop(&stack); //stack을 비운다.
SPush(&stack, tok);
break;
}
}
}
while(!SIsEmpty(&stack))
convExp[idx++] = SPop(&stack);
strcpy(exp, convExp);
free(convExp);
}
파일명: InfixToPostfixMain.c
#include <stdio.h>
#include "InfixToPostfix.h"
int main(void)
{
char exp1[] = "1+2*3";
char exp2[] = "(1+2)*3";
char exp3[] = "((1-2)+3)*(5-2)";
ConvToRPNExp(exp1);
ConvToRPNExp(exp2);
ConvToRPNExp(exp3);
printf("%s \n", exp1);
printf("%s \n", exp2);
printf("%s \n", exp3);
return 0;
}123*+
12+3*
12-3+52-*
후위 표기법 수식의 계산
- 가장 좌측에 있는 연산자부터 계산한다.
- 연산자 앞의 두 숫자가 피연산자이다.
1 2 * 3 + 4 / -> 2 3 + 4 /
3 2 4 * + -> 3 8 +
후위 표기법 수식을 계산하는 프로그램 구현
- 후위 표기법 수식을 담는 문자열 exp, 스택 stack
- exp의 좌측 구성요소부터 하나씩 읽어서 숫자면 스택에 쌓고, 연산자이면 스택에서 피연산자 op1, op2를 꺼내서 연산을 진행한 결과를 stack에 쌓는다.
파일명: PostCalculator.h
#ifndef __POST_CALCULATOR_H__
#define __POST_CALCULATOR_H__
int EvalRPNExp(char exp[]);
#endif
파일명: PostCalculator.c
#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'); // '0'의 아스키 코드를 뺄셈
else
{
op1 = SPop(&stack);
op2 = SPop(&stack);
switch (tok)
{
case '+':
SPush(&stack, op2 + op1);
break;
case '-':
SPush(&stack, op2 - op1);
break;
case '*':
SPush(&stack, op2 * op1);
break;
case '/':
SPush(&stack, op2 / op1);
break;
default:
break;
}
}
}
int result = SPop(&stack);
return result;
}
파일명: PostCalculatorMain.c
#include <stdio.h>
#include "PostCalculator.h"
int main(void)
{
char postExp1[] = "42*8+";
char postExp2[] = "123+*4/";
printf("%s = %d \n", postExp1, EvalRPNExp(postExp1));
printf("%s = %d \n", postExp2, EvalRPNExp(postExp2));
return 0;
}42*8+ = 16
123+*4/ = 1
ConvToRPNExp와 EvalRPNExp를 합친 함수 EvalInfixExp
파일명: InfixCalculator.h
#ifndef __INFIX_CALCULATOR__
#define __INFIX_CALCULATOR__
int EvalInfixExp(char exp[]);
#endif
파일명: InfixCalculator.c
#include <string.h>
#include <stdlib.h>
#include "InfixToPostfix.h"
#include "PostCalculator.h"
int EvalInfixExp(char exp[])
{
int len = strlen(exp);
int ret;
char * expcpy = (char*)malloc(len+1);
strcpy(expcpy, exp);
ConvToRPNExp(expcpy);
ret = EvalRPNExp(expcpy);
free(expcpy);
return ret;
}
파일명: InfixCalculatorMain.c
#include <stdio.h>
#include "InfixCalculator.h"
int main(void)
{
char exp1[] = "1+2*3";
char exp2[] = "(1+2)*3";
char exp3[] = "((1-2)+3)*(5-2)";
printf("%s = %d \n", exp1, EvalInfixExp(exp1));
printf("%s = %d \n", exp2, EvalInfixExp(exp2));
printf("%s = %d \n", exp3, EvalInfixExp(exp3));
return 0;
}1+2*3 = 7
(1+2)*3 = 9
((1-2)+3)*(5-2) = 6
참고자료
- 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11
728x90
반응형