06-1. 스택의 이해와 ADT 정의
스택 : 선형 자료구조
먼저 들어간 것이 나중에 나온다
후입선출 방식의 자료구조
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);
- 마지막에 저장된 요소를 반환하되 삭제하지 않는다
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다
배열 혹은 연결리스트 기반으로 구현한다
06-2. 스택의 배열기반 구현
구현의 논리와 헤더파일의 정의
- 인덱스 0의 배열 요소가 스택의 바닥으로 정의되어 있다
- 마지막에 저장된 데이터의 위치를 기억해야 한다
Top : 가장 위에 저장된 데이터의 위치
- push : Top을 위로 한 칸 올리고, Top이 가리키는 위치에 데이터 저장
- pop : Top이 가리키는 데이터를 반환하고, Top을 한 칸 아래로 내림
#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배열 기반 스택의 구현
- 구조체
typedef struct _arrayStack
{
Data stackArr[STACK_LEN];
int topIndex;
} ArrayStack;- 초기화
void StackInit(Stack *pstack)
{
pstack->topIndex = -1; // topIndex의 -1은 빈 상태를 의미
}topIndex에 0이 저장되면, 이는 인덱스 0의 위치에 마지막 데이터가 저장되었음을 의미하므로 -1로 초기화한다
-스택이 비어있는지 확인
int SIsEmpty(Stack *pstack)
{
if(pstack->topIndex == -1) // 스택이 비어있다면
return TRUE;
else
return FALSE;
}- push함수
void SPush(Stack *pstack, Data data) // push 연산 담당 함수
{
pstack->topIndex += 1; // 데이터 추가를 위한 인덱스 값 증가
pstack->stackArr[pstack->topIndex] = data; // 데이터 저장
}- pop함수
Data SPop(Stack *pstack) // pop연산 담당 함수
{
int rIdx;
if(SIsEmpty(pstack)) {
printf(“Stack Memory Error!”);
exit(-1);
}
rIdx = pstack->topIndex; // 삭제할 데이터가 저장된 인덱스 값 저장
pstack->topIndex -= 1; // pop 연산의 결과로 topIndex값 하나 감소
return pstack->stackArr[rIdx]; // 삭제되는 데이터 반환- peek함수
Data SPeek(Stack *pstack) // peek 연산 담당 함수
{
if(SIsEmpty(pstack))
{
printf(“Stack Memory Error!”);
exit(-1);
}
return pstack->stackArr[pstack->topIndex]; // 맨 위에 저장된 데이터 반환06-3. 스택의 연결 리스트 기반 구현
스택도 연결 리스트다. 다만 저장된 순서의 역순으로 조회(삭제)가 가능한 연결 리스트이다.
#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연결 리스트 기반 스택의 구현
void StackInit(Stack * pstack) //스택 초기화
{
pstack->head = NULL; //포인터 변수 head는 NULL로 초기화한다
}int SIsEmpty(Stack *pstack) //스택이 비었는지 확인
{
if(pstack->head == NULL) // 스택이 비면 head에는 NULL이 저장된다.
return TRUE;
else
return FALSE;
}void SPush(Stack *pstack, Data data) //스택의 push 연산
{
Node *newNode = (Node *)malloc(sizeof(Node)); // 새 노드 생성
newNode->data = data; // 새 노드에 데이터 저장
newNode->next = pstack->head; //새 노드가 최근에 추가된 노드를 가리킴
pstack->head = newNode; //포인터 변수 head가 새 노드를 가리킴
}Data SPop(Stack *pstack) //스택의 pop 연산
{
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) //스택의 peek 연산
{
if(SIsEmpty(pstack)) {
printf("Stack Memory Error!");
exit(-1);
}
return pstack->head->data; // head가 가리키는 노드에 저장된 데이터 반환
}06-4. 계산기 프로그램 구현
구현할 계산기 프로그램의 성격
- 소괄호를 파악하여 그 부분을 먼저 연산한다
- 연산자의 우선순위를 근거로 연산의 순위를 결정한다
수식의 표기법 : 중위(infix), 전위(prefix), 후위(postfix) 표기법
- 중위 표기법(infix notation) : 5+2/7
- 전위 표기법(prefix notation) : +5/27
- 후위 표기법(postfix notation) : 527/+
중위 표기법은 연산 순서에 대한 정보가 담겨있지 않다
전위 표기법이나 후위 표기법은 배치순서를 근거로 한 연산순서의 정보가 담기기 때문에 연산자의 우선수위가 필요하지 않다. 연산자의 배치순서를 바꿈으로써 연산의 순서를 바꿀 수 있기 때문에 소괄호를 필요로 하지 않는다
중위 표기법을 후위 표기법으로 바꾸는 방법 1
- 중위 표기법의 수식을 후위 표기법의 수식으로 바꾼다
- 후위 표기법으로 바뀐 수식을 계산하여 그 결과를 얻는다
5 + 2 / 7
숫자는 그냥 변환된 수식이 놓일 위치에 가져다 놓는다
쟁반이 비어있으니 + 연산자는 쟁반으로 옮긴다
2는 숫자이므로 변환된 수식이 놓일 위치에 가져다 놓는다
/ 연산자
- 쟁반에 위치한 연산자의 우선순위가 높거나 같다면
- 쟁반에 위치한 연산자를 꺼내서 변환된 수식이 위치할 자리로 옮긴다
- 그리고 새 연산자는 쟁반으로 옮긴다
- 쟁반에 위치한 연산자의 우선순위가 낮다면
- 쟁반에 위치한 연산자의 위에 새 연산자를 쌓는다
7은 숫자이므로 변환된 수식이 놓일 위치에 가져다 놓는다
쟁반에 쌓인 연산자를 위의 것부터 꺼내서 옮긴다
- 피연산자는 그냥 옮긴다
- 연산자는 쟁반으로 옮긴다
- 연산자가 쟁반에 있다면 우선순위를 비교하여 처리방법을 결정한다
- 마지막까지 쟁반에 남아있는 연산자들은 하나씩 꺼내서 옮긴다
중위 표기법을 후위 표기법으로 바꾸는 방법 2
(1 + 2 * 3 ) / 4
소괄호를 연산자로 인식하고 쟁반에 올린다
1은 숫자이므로 변환된 수식이 위치할 자리에 옮긴다
‘(‘연산자는 ‘)’연산자가 등장할 때까지 쟁반 위에 남아있어야 하기 때문에 사칙 연산자들보다 연산의 우선순위가 낮다고 간주하므로 +연산자를 쟁반에 쌓는다
숫자 2를 변환된 수식의 자리로 이동하고 * 연산자의 우선순위가 + 보다 높으므로 쟁반 위에 쌓는다
숫자 3을 변환된 수식의 자리로 이동하고 ‘)’연산자는 소괄호의 끝을 의미하므로 ‘(‘ 이후에 쌓인 연산자들을 쟁반에서 꺼내어 변환된 수식의 자리로 옮겨야 한다
/ 연산자를 쟁반에 놓고 숫자 4를 변환된 수식이 위치할 자리에 옮긴다
중위 표기법을 후위 표기법으로 바꾸는 프로그램의 구현
실제 후위 표기법으로의 변환을 처리하는 함수
void ConvToRPNExp(char exp[]) // 후위 표기법의 수식으로 변환
{
. . .
}중위 표기법의 수식을 담고 있는 배열의 주소 값을 인자로 전달하면서 ConvToRPNExp 함수를 호출하면, 인자로 전달된 주소 값의 배열에는 후위 표기법으로 바뀐 수식이 저장된다
인자로 전달된 연산자의 우선순위 정보를 정수의 형태로 반환하는 함수
int GetOpPrec(char op) // 연산자의 연산 우선수위 정보를 반환한다
{
switch(op)
{
case '*' :
case '/' :
return 5; // 가장 높은 순위의 연산순위
case '+' :
case '-' :
return 3; // 5보다 작고 1보다 높은 연산의 우선순위
case '(' :
return 1; // 가장 낮은 순위의 연산순위
}
return -1;
}Q. ( 연산자가 타 연산자들보다 낮은 우선순위의 값을 반환하는 이유는?
A. ( 연산자는 ) 연산자가 등장할 때까지 쟁반 위에 남아있어야 하기 때문에
Q. ) 연산자의 반환 값이 정의되어있지 않은 이유는?
A. ) 연산자는 소괄호의 끝이라는 메시지만 전달하기 때문에
GetOpPrec함수의 호출결과를 바탕으로 두 연산자의 우선순위를 비교하여 그 결과를 반환하는 함수
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의 우선순위가 같다면
}
}후위표기법으로의 변환을 담당하는 ConvToRPNExp 함수
void ConvToRPNExp(char exp[])
{
Stack stack;
int explen = strlen(exp);
char *convExp = (char*)malloc(sizeof(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]; //exp로 전달된 수식을 하나씩 tok로 전달
if(isdigit(tok)) //tok에 저장된 문자가 숫자인지 확인
{
convExp[idx++] = tok; //숫자이면 배열 convExp에 그냥 저장
}
else //숫자가 아니라면(연산자라면)
{
switch(tok)
{
case'(' : //여는 소괄호라면
SPush(&stack, tok); //스택에 쌓는다
break;
case ')' : //닫는 소괄호라면
while(1) //반복해서
{
popOp = SPop(&stack); //스택에서 연산자를 꺼내어
if(popOp == '(') //연산자 (을 만날 때까지
{
break;
}
convExp[idx++] = popOp; //배열 convExp에 저장한다
}
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); //배열 convExp로 이동한다
}
strcpy(exp, convExp); //변환된 수식을 exp에 복사하고,
free(convExp); //convExp는 소멸시킨다
}void * memset(void *ptr, int val, size_t len);
ptr로 전달된 주소의 메모리서부터 len바이트를 var의 값으로 채운다int isdigit(int ch);
ch로 전달된 문자의 내용이 10진수라면 1을 반환한다
후위 표기법으로 표현된 수식의 계산방법
후위 표기법의 수식에는 연산자의 앞에 등장하는 두 개의 숫자가 피연산자이다
Ex) 3 2 4 * +
후위 표기법으로 표현된 수식을 계산하는 프로그램 구현
- 피연산자는 무조건 스택으로 옮긴다
- 연산자를 만나면 스택에서 두 개의 피연산자를 꺼내서 계산을 한다
- 계산결과는 다시 스택에 넣는다
- 3 2 4 * +
4 2 가 아니라 2 4 다. 스택에서 먼저 꺼낸 연산자가 두 번째 피연산자가 되고, 나중에 꺼낸 연산자가 첫 번째 피연산자가 된다
2 . 3 8 +
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]; // 한 문자씩 tok에 저장하고,
if(isdigit(tok)) //문자의 내용이 정수인지 확인한다.
{
SPush(&stack, tok - '0'); // 정수면 숫자로 변환 후 스택에 PUSH한다
}
else //정수가 아닌 연산자라면,
{
op2 = SPop(&stack); //스택에서 두 번째 연산자를 꺼낸다
op1 = SPop(&stack); //스택에서 첫 번째 연산자를 꺼낸다
switch(tok) //연산하고 그 결과를 다시 스택에 PUSH!
{
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); //마지막 연산결과를 스택에서 꺼내어 반환
}
Back-end Developer