스택(Stack)
나중에 들어간 것이 먼저 나오는 구조.
후입선출 방식의 구조, 영어로는 LIFO(Last-In, First-Out) 구조라 불린다.
스택을 대표하는 넣고, 꺼내고, 들여다 보는 연산을 push, pop, peek이라 한다.
스택을 배열 기반으로 구현할 지, 연결리스트 기반으로 구현할 지 선택 필요.
스택은 상황이 그리 다양하지 않아서 데이터를 추가하는 상황과 꺼내는 상황만 주로 생각하면 된다.
스택의 배열 기반 구현
// 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);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);
#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);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);
#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)
{
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;
free(rnode);
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 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
계산기 프로그램 구현
자료구조에서 스택의 활용과 관련해서 빠지지 않고 등장하는 사례가 계산기 프로그램.
만약 (3+4) * (5/2) + (7+(9-5)) 수식을 계산하려면 연산자의 우선순위와 괄호의 위치를 인식하여 연산의 결과를 낼 수 있어야 한다.
중요하지 않은 부분은 생략하기 위해 수식을 이루는 피연산자는 한자리 숫자로만 이뤄지도록 한다.
중위(infix), 전위(prefix), 후위(postfix) 표기법 예시
중위 표기법 : 5 + 2 / 7
전위 표기법 : + 5 / 2 7
후위 표기법 5 2 7 / +
중위 표기법을 후위 표기법으로 바꾸는 코드
// InfixToPostfix.h
#ifndef __INFIX_TO_POSTFIX_H__
#define __INFIX_TO_POSTFIX_H__
void ConvToRPNExp(char exp[]);
#endif// InfixToPostfix.c
#include <string.h>
#include <stdlib.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);
StackInit(&stack);
for (i = 0; i < expLen; i++)
{
tok = exp[i];
if (isdigit(tok))
{
convExp[idx++] = tok;
}
else
{
switch (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);
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-*후위 표기법으로 표현된 수식을 계산하는 코드
// 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];
// isdigit 십진수로 표현 가능한지 판별 ctype.h 헤더
if (isdigit(tok))
{
// 문자이므로 아스키코드값 저장
// 따라서 아스키 코드값으로 연산값을 고려
SPush(&stack, tok - '0'); // 숫자로 변환하여 PUSH!
}
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);
}// 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중위 표기법 소스 코드
// InfixCalculator.h
#ifndef __INFIX_CALCULATOR__
#define __INFIX_CALCULATOR__
int EvalInfixExp(char exp[]);
#endif// InfixCalculator.c
#include <string.h>
#include <stdlib.h>
#include "InfixToPostfix.h" // ConvToRPNExp()
#include "PostCalculator.h" // EvalRPNExp()
int EvalInfixExp(char exp[])
{
int len = (int)strlen(exp);
int ret;
char* expcpy = (char*)malloc(len + 1);
strcpy(expcpy, exp);
ConvToRPNExp(expcpy); // notation converting.
ret = EvalRPNExp(expcpy); // expression evaluating.
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
댓글 없음:
댓글 쓰기