스택(stack)

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

 

1. 스택의 이해와 ADT 정의

• 후입선출 방식의 자료구조 (LIFO: Last-In, First-Out)
• 스택자료의 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);
- 마지막에 저장한 요소를 반환하되 삭제하지 않음
- 본 함수의 호출을 위해서는 데이터가 존재해야 함

 

2. 스택의 배열 기반 구현

2.1. 구현의 논리와 헤더파일의 정의

• 인덱스 0의 배열 요소가 스택의 바닥으로 정의
• 마지막에 저장된 데이터의 위치를 기억해야 함
• push: Top을 위로 한 칸 올리고, Top이 가리키는 위치에 데이터 저장
• pop: Top이 가리키는 데이터를 반환하고, Top을 아래로 한 칸 내림

2.2. 배열 기반 스택 구현

typedef struct _arrayStack
{
	Data StackArr[STACK_LEN];
	int topIndex;
} ArrayStack;

void StackInit(Stack *pstack)
{
	pstack->topIndex = -1;  // -1: 빈 상태
}

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

 

• Push와 Pop

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

Data SPop(Stack *pstack)
{
	int rIdx;
	
	if(SIsEmpty(pstack)){
		printf("Stack Memory Error!");
		exit(-1);
	}
	
	rIdx = pstack->topIndex
	pstack->topIndex -=1   // pop 연산으로 topIndex 값 하나 감소
	
	return pstack->stackArr[rIdx];
}

 

• SPeek

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

 

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

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

• “스택도 연결 리스트이다. 다만 저장된 순서의 역순으로 조회가 가능한 연결 리스트”
• 연결리스트 기반 스택 ADT

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

 

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

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;  // 삭제할 노드의 다음 노드를 head가 가리킴
	free(rnode);  // 노드 삭제
	return rdata;
}

Data SPeek(Stack *pstack)
{
	if(SIsEmpty(pstack)){
		printf("Stack Memory Error!");
		exit(-1);
	}
	
	return pstack->head->data;
}

 

4. 계산기 프로그램 구현

4.1. 계산기 프로그램의 성격

• 소괄호를 파악하여 그 부분 먼저 연산
• 연산자의 우선순위를 근거로 연산 순위 결정

4.2. 수식의 표기법: 중위(infix), 전위(prefix), 후위(postfix) 표기법

• 중위 표기법: 5 + 2 / 7
• 전위 표기법: + 5 / 2 7
• 후위 표기법: 5 2 7 / +

4.3. 과정 1: 중위 표기법 → 후위 표기법 - 괄호 X

• 계산기 구현 과정
  1. 중위 표기법의 수식을 후위 표기법의 수식으로 바꾸고
  2. 후위 표기법으로 바뀐 수식을 계산하여 결과를 얻는다.
• 연산자를 만나면 무조건 쟁반으로
  
  

• 숫자를 만날 경우 변환된 수식이 위치할 자리로 이동

• 다시 연산자를 만난 경우

• 쟁반에 위치한 연산자의 우선순위가 높으면
  • 쟁반에 위치한 연산자를 꺼내서 변환된 수식이 위치할 자리로 옮긴다
  • 그리고 새 연산자는 쟁반으로
• 쟁반에 위치한 연산자의 우선순위가 낮은 경우
  • 쟁반에 위치한 연산자의 위에 새 연산자를 쌓는다

• 정리
  • 피연산자는 그냥 옮긴다
  • 연산자는 쟁반으로 옮긴다
  • 연산자가 쟁반에 있다면 우선순위를 비교하여 처리방법 결정
    • 우선순위가 동일한 경우, 먼저 등장한 연산자를 먼저 진행
    • 둘 이상의 연산자가 쌓여 있고 쟁반의 연산자 순위가 높으면, 우선순위가 낮은 연산자가 나올때까지 옮긴다.
  • 마지막까지 쟁반에 남아있는 연산자들은 하나씩 꺼내서 옮김

 

4.4. 과정 1: 중위 표기법 → 후위 표기법 - 괄호 존재

• ( 연산자는 )연산자가 등장할 때까지 쟁반 위에 남아야 하기 때문에 사칙 연산자들보다 우선순위가 낮다고 가정
• ) 연산자를 만나면 쌓인 연산자를 다 꺼내어 수식 자리로 옮긴다.

 

4.5. 중위 표기법 → 후위 표기법 구현

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)   // op1의 우선순위가 높은 경우
		return 1;
	else if(op1Prec < op2Prec)  // op2의 우선순위가 높은 경우
		return -1;
	else
		return 0;  // op1와 op2의 우선순위가 같다면
}

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);  // 할당된 배열을 0으로 초기화
	StackInit(&stack);
	
	for(i=0; i<expLen; i++) {
		tok = exp[i];
		if(isdigit(tok))  // tok에 저장된 문자가 숫자인지 확인
		{
			convExp[idx++] = tok;  // 숫자이면 배열 conExp에 그냥 저장
		}
		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) 
					conExp[idx++] = SPop(&stack);
				SPush(&stack, tok);
				break;
			}
		}
	}
	while(!SIsEmpty(&stack))  // 스택에 남아 있는 모든 연산자를,
		convExp[idx++] = SPop(&stack);  // 배열 conExp로 이동한다.
	
	strcpy(exp, convExp);  // 변환된 수식을 exp에 복사하고,
	free(convExp);  // conExp는 소멸시킨다.
}

 

4.6. 후위 표기법 수식 계산

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

int EvalRPExp(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];  // 한 문자씩 tok에 저장하고
		if(isdigit(tok))  // 문자 내용이 정수인지 확인
		{
			SPush(&stack, tok - '0');  // 정tnaus 숫자로 변환후 스택에 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);
}

 

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)