스택

리스트는 대표적인 선형 자료 구조 입니다. 스택이란 자료구조도 선형 자료구조의 일종입니다. 쌓아 올려진 상자더미나 쟁반 위에 쌓인 접시. 먼저 들어간 것이 나중에 나옵니다. Last-In, First-Out 구조의 자료구조라고도 불립니다. 

스택 ATD의 정의

스택을 대표하는 넣고, 꺼내고, 들여다 보는 연산을 가리켜 각각 push, pop, peek이라 합니다. 때문에 스택의 ADT는 다음과 같이 정의가 되며, 이것이 스택의 보편적인 ADT입니다. void StackInit(Stack * pstack); 스택의 초기화를 진행합니다. 스택 생성 후 제일 먼저 호출되어야 하는 함수입니다. int SIsEmpty(Stack * pstack); 스택이 빈 경우 TRUE를, 그렇지 않은 경우 FALSE를 반환합니다. void SPush(Stack * pstack, Data data); 스택에 데이터를 저장합니다. 매개변수 data로 전달된 값을 저장합니다. Data SPop(Stack * pstack); 마지막에 저장된 요소를 삭제합니다. 삭제된 데이터는 반환이 됩니다. 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 합니다. Data SPeek(Stack * pstack); 마지막에 저장된 요소를 반환하되 삭제하지 않습니다. 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 합니다. 스택을 배열 기반으로 구현할 것인가. 아니면 연결 리스트 기반으로 구현할 것인가? 

스택의 배열 기반 구현

처음부터 끝까지 새로이 구현하는 것은 부담스러운 일입니다. 하지만 그 대상이 스택이라면 그 부담은 반으로 줄어듭니다. 구현의 논리와 헤더파일의 정의. 인덱스 0의 배열 요소가 스택의 바닥으로 정의되었습니다. 마지막에 저장된 데이터의 위치를 기억해야 합니다. 이넥스 0의 요소르 스택의 바닥으로 정의하면, 배열의 길이에 상관 없이 언제나 인덱스 0의 요소가 스택의 바닥이 됩니다. Top이 가리키는 위치의 인덱스 값을 변수 topIndex에 저장하고 있습니다. 

#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

배열 기반 스택의 구현

초기화할 멤버는 가장 마지막에 저장된 데이터의 위치를 가리키는 topIndex 하나입니다. 따라서 StackInit 함수는 다음과 같이 간단히 정의됩니다. topIndex에 0이 저장되면, 이는 인덱스 0의 위치에 마지막 데이터가 저장되었음을 뜻하는 것이 됩니다. 따라서 topIndex 를 0이 아닌 -1로 초기화 해야 합니다. 이어서 SIsEmpty 함수를 정의를 봅니다. 이 함수는 스택이 비어있는지 확인할 때 호출하는 함수입니다. 꺼낸다는 의미의 pop에는 삭제와 반환의 의미가 함께 담겨 있습니다. 스택이 반환할 다음 데이터를 확인할 필요가 간혹 있습니다. 

#include <stdio.h> #include "example.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; }

실행 결과에서 입력된 데이터가 역순으로 출력됨을 보이고 있습니다. 이것이 스택의 가장 중요한 특성입니다.

스택의 연결 리스트 기반 구현

기능적인 부분만 고려를 한다면 배열은 대부분 연결 리스트로 교체가 가능합니다. 배열도 연결 리스트도 기본적인 선형 자료구조이기 때문입니다.

연결 리스트 기반 스택의 논리와 헤더파일 정의

스택에서 배열을 연결 리스트로 변경할 경우, 연결 리스트가 갖는 특징이 그대로 스택에 반영됩니다. 스택도 연결 리스트이다. 다만 저장된 순서의 역순으로 조회가 가능한 연결 리스트일 뿐입니다. 연결 리스트 모델과 정의한 스택 ADT를 기준으로 연결 리스트 기반의 스택을 구현해보겠습니다.

#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

#include <stdio.h> #include <stdlib.h> #include "example.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; }

#include <stdio.h> #include "example.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; }

계산기 프로그램 구현

구현한 스택을 활용할 차례입니다. 자료구조에서 스택의 활용과 관련해서 빠지지 않고 등장하는 사례가 계산기 프로그램입니다.

구현할 계산기 프로그램의 성격

프로그램은 연산자의 우선순위와 괄호의 위치를 인식하여 연산의 결과를 프로그램 사용자에게 보여야 합니다. 즉, 우리가 구현할 계산기는 다음 두가 지를 고려해서 연산을 진행 할 수 있어야 합니다. 소괄호를 파악하여 그 부분을 먼저 연산합니다. 연산자의 우선순위를 근거로 연산의 순위를 결정합니다. 

수식의 표기법:중의, 전위, 후의 infix, prefix, postfix 표기법

수식을 이루는 피연산자는 한자리 숫자로만 이뤄진다고 가정합니다. 전위 표기법의 수식이나 후의 표기법의 수식은 연산자의 배치순서에 따라서 연산순서가 결정되기 때문에, 이 두 표기법의 수식을 계산하기 위해서 연산자의 우선순위를 알 필요가 없고, 소괄호도 사빕되지 않으니 소괄호에 대한 처리도 불필요합니다. 본인은 그 수식을 전위 표기법 또는 후위 표기법의 수식으로 변환하여 계산이 진행되도록 할 것입니다. 참고로 본인이 프로그램상에서 작성하는 연산문도 컴파일러에 의해서 후위 표기법으로 바뀌어 처리가 됩니다. 

중위 표기법을 후위 표기법으로 바꾸는 방법 1/2: 소괄호를 고려하지 않고

중위 표기법의 수식을 후위 표기법의 수식으로 바꿉니다. 후위 표기법으로 바뀐 수식을 계산하여 그 결과를 얻습니다. 쟁반에 위치한 연산자의 우선순위가 높다면 쟁반에 위치한 연산자를 꺼내서 변환된 수식이 위치할 자리로 옮깁니다. 새 연산자는 쟁반으로 옮깁니다. 쟁반에 위치한 연산자의 우선순위가 낮다면 쟁반에 위치한 연산자의 위에 새 연산자를 쌓습니다. 정리하자면, 피연산자는 그냥 옮긴다. 연산자는 쟁반으로 옮긴다. 연산자가 쟁반에 있다면 우선순위를 비교하여 처리방법을 결정합니다. 마지막까지 쟁반에 남아있는 연산자들은 하나씩 꺼내서 옮깁니다. 사칙연산의 경우 연산자의 우선순위가 동일하면, 먼저 등장한 연산자를 먼저 진행합니다. 정리하면, 쟁반으로 이동하는 연산자는 자신보다 나중에 연산이 이뤄져야 하는 연산자의 위에 올라서 있어야 합니다. 

중위 표기법을 후위 표기법으로 바꾸는 방법 2/2: 소괄호를 고려하고

후위 표기법의 수식에서는 먼저 연산이 이뤄져야 하는 연산자가 뒤에 연산이 이뤄지는 연산자봐 앞에 위치해야 합니다. / 연산자를 쟁반 위에 올릴 떄, 쟁반 위에 + 연산자와 * 연산자가 존재한다면, 이들을 모두 빼서 변환된 수식의  자리에 가져다 놓습니다. 후위 표기법으로 변환을 하면서 소괄호는 소멸됩니다. (, ) 연산자가 등장할 때까지 쟁반 위에 남아있어야 하기 때문에 사칙 연산자들보다 연산의 우선순위가 낮다고 간주합니다. 

중위 표기법을 후위 표기법으로 바꾸는 프로그램의 구현

중위 표기법의 수식을 담고 있는 배열의 주소 값을 인자로 전달하면서 함수를 호출하면, 인자로 전달된 주소 값의 배열에는 후위 표기법으로 바뀐 수식이 저장됩니다. 

중위 표기법을 후위 표기법으로 바꾸는 프로그램의 실행

#ifndef __INFIX_TO_POSTFIX_H__ #define __INFIX_TO_POSTFIX_H__ void ConvToRPNExp(char exp[]); #endif

#pragma warning(disable:4996) #include <string.h> #include <stdlib.h> #include <ctype.h> #include "example.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); }

#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; }

후기 표기법으로 표현된 수식의 계산방법

후위 표기법의 수식에서는 연산자의 앞에 등장하는 두 개의 숫자가 피연산자입니다. 

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

피연산자는 무조건 스택으로 옮깁니다. 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내서 계산을 합니다. 계산결과는 다시 스택에 넣습니다. 

#ifndef __POST_CALCULATOR_H__ #define __POST_CALCULATOR_H__ int EvalRPNExp(char exp[]); #endif

#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; }

중위 표기법의 수식을 후위 표기법의 수식으로 변환하는 함수도 정의하였고, 후위 표기법의 수식을 계산하는 함수도 정의하였으니, 프로그램 사용자로부터 소괄호를 포함하는 중위 표기법의 수식을 입력 받아서, 그 결과를 계산하여 출력하는 것이 가능해졌습니다. 프로그램 사용자로부터 소괄호가 포함된 중위 표기법의 수식을 입력 받아서 그 연산결과를 출력해줍니다. 

#ifndef __INFIX_CALCULATOR__ #define __INFIX_CALCULATOR__ int EvalInfixExp(char exp[]); #endif

#pragma warning(disable:4996) #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; }

#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; }