[Data Structure] Chapter 06: 스택(Stack)

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