6. 스택

6-1. 스택의 이해와 ADT 정의

 

* 스택의 이해

스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조이다.

스택은 나중에 들어간 것이 먼저 나오는 구조이다.

-> Last In First Out(LIFO)

스택

* 스택의 ADT

Operation:

• 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)
  • 마지막에 저장된 요소를 반환하되 삭제하지 않는다.
  • 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

6-2. 배열 기반 스택의 구현

 

* 배열 기반 스택의 구현 논리

인덱스 0의 배열 요소가 스택의 바닥으로 정의된다.

마지막에 저장된 데이터의 인덱스를 저장해야 한다.

 

* 배열 기반 스택의 구현

#include <stdio.h>
#include <stdlib.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) {
	pstack->topIndex = -1;
}

int SIsEmpty(Stack* pstack) {
	if (pstack->topIndex == -1)
		return TRUE;
	else
		return FALSE;
}

void SPush(Stack* pstack, Data data) {
	(pstack->topIndex)++;
	pstack->stackArr[pstack->topIndex] = data;
}

Data SPop(Stack* pstack) {
	int rIdx;
	if (SIsEmpty(pstack)) {
		printf("Stack Memory Error!\n");
		exit(-1);
	}
	rIdx = pstack->topIndex;
	(pstack->topIndex)--;
	return pstack->stackArr[rIdx];
}

Data SPeek(Stack* pstack) {
	if (SIsEmpty(pstack)) {
		printf("Stack Memory Error!\n");
		exit(-1);
	}
	return pstack->stackArr[pstack->topIndex];
}

 

6-3. 연결 리스트 기반 스택의 구현

 

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

스택은 새로운 노드를 머리에 추가하는 연결 리스트와 같다.

 

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

#include <stdio.h>
#include <stdlib.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) {
	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) {
	int rdata;
	Node* rnode;
	if (SIsEmpty(pstack)) {
		printf("Stack Memory Error!\n");
		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!\n");
		exit(-1);
	}
	return pstack->head->data;
}

 

6-4. 계산기 프로그램 구현

 

* 수식의 표기법

중위(infix) 표기법: 5 + 2 / 7

전위(prefix) 표기법: + 5 / 2 7

후위(postfix) 표기법: 5 2 7 / +

전위 표기법의 수식이나 후위 표기법의 수식은 연산자의 배치 순서에 따라서 연산 순서가 결정되기 때문에, 이 두 표기법의 수식을 계산하기 위해서는 연산자의 우선순위를 알 필요가 없고, 소괄호에 대한 처리도 불필요하다.

우리가 구현할 계산기 프로그램은 중위 표기법을 후위 표기법으로 변환하여 처리한다.

 

* 중위 표기법을 후위 표기법으로 바꾸는 방법

• 피연산자는 바로 출력한다.
• 연산자는 자기보다 우선순위가 높거나 같은 것을 빼고 자신을 스택에 담는다.
• 여는 괄호는 스택에 담는다.
• 닫는 괄호가 나오면 여는 괄호가 나올 때까지 스택에서 연산자를 출력한다.

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

#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 idx = 0;
	char tok, popOp;
	memset(convExp, 0, sizeof(char) * expLen + 1);
	StackInit(&stack);
	for (int 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 <string.h>
#include <ctype.h>
#include "ListBaseStack.h" // 이전에 구현한 스택을 사용한다.

int EvalRPNExp(char exp[]) {
	Stack stack;
	int expLen = strlen(exp);
	char tok, op1, op2;
	StackInit(&stack);
	for (int i = 0; i < expLen; i++) {
		tok = exp[i];
		if (isdigit(tok))
			SPush(&stack, tok - '0');
		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);
}

 

* 계산기 프로그램의 구현

사용자로부터 중위 표기법의 수식을 입력 받아서 그 연산 결과를 출력한다.

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

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

 

참조문헌: 윤성우의 열혈 자료구조