스택
-> 삽입과 제거가 한쪽 끝에서만 이루어지는 특수한 선형 리스트. 후입선출(LIFO) 구조.
○ 스택 ADT
| create(s) :: = 스택 s를 생성한다. |
| is_empty(s) :: = 스택 s가 비어있는지를 검사한다. |
| is_full(s) :: = 스택 s가 가득 찼는가를 검사한다. |
| push(s,e) :: = 스택 s에 원소 e를 삽입한다. |
| pop(s) :: = 스택 s에서 가장 최근에 삽입된 원소(top 위치에 있는 원소)를 삭제하면서 그 값을 반환한다. |
| peek(s) :: = 스택 s에서 가장 최근에 삽입된 원소(top 위치에 있는 원소)의 값을 반환한다. |
○ 스택의 구현
· 배열을 이용한 스택의 구현
: 1차원 배열 stack[], 가장 최근에 입력되었던 자료를 가리키는 변수 top. 공백상태면 top은 -1(bottom).
typedef int element;
typedef struct{
element stack[MAX_STACK_SIZE];
int top;
} StackType;
//스택 초기화 함수
void init(StackType *s)
{
s->top = -1;
}
//공백상태 검출 함수
int is_empty(StackType *s)
{
return (s->top == -1);
}
//포화상태 검출 함수
int is_full(StackType *s)
{
return (s->top == (MAX_STACK_SIZE-1));
}
//삽입 함수
void push(StackType *s, element item){
if(is_full(s)){
printf("스택이 포화상태입니다.");
else
s->stack[++(s->top)] = item;
}
//삭제 함수
element pop(StackType *s){
if(is_empty(s)){
printf("스택이 공백상태입니다.");
exit(1);
}
else
return s->stack[(s->top)--];
}
//피크 함수
element peek(StackType *s){
if(is_empty(s)){
printf("스택이 공백상태입니다.");
exit(1);
}
else
return s->stack[(s->top)--];
}
· 연결리스트를 이용한 스택의 구현
: 배열같이 스택의 크기가 제한되지 않으나 구현이 다소 복잡하고 삽입, 삭제시 시간이 약간 더 걸린다.
typedef int element; //원소 타입
typedef struct StackNode{ //노드 구조
element data;
struct StackNode *link;
} StackNode;
typedef struct{ //연결 스택 구조
StackNode *top;
} LinkedStackType;
//삽입 함수
void push(LinkedStackType *s, element item){
StackNode *temp = (StackNode*)malloc(sizeof(StackNode));
if( temp == NULL ){
printf("스택이 포화상태");
return;
}
else{
temp->data = item;
temp->link = s->top;
s->top = temp;
}
}
//삭제 함수
element pop(LinkedStackType *s){
if(is_empty(s)){
printf("스택이 공백상태");
exit(1);
}
else{
StackNode *temp = s->top;
int item = temp->data;
s->top = s->top->link;
free(temp);
return item;
}
}
○ 스택 응용 : 괄호 검사
· 조건
: 왼쪽 괄호와 오른쪽 괄호의 개수가 같아야 하며, 같은 괄호쌍에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 하고, 서로 다른 타입의 왼쪽 괄호와 오른쪽 괄호 쌍은 서로 교차하면 안 된다.
· 알고리즘 개요
: 왼쪽 괄호를 만나면 스택에 삽입하고, 오른쪽 괄호를 만나면 스택 top에 있는 괄호와 짝이 맞는지 비교한다. 이때, 스택이 비어 있거나 괄호의 짝이 맞지 않으면 조건에 위반된다. 또한, 마지막 괄호까지 조사한 후에도 스택에 괄호가 남아 있다면 조건에 위반된다.
//괄호 짝 확인하는 함수
int check_matching(char *in){
StackType s;
char ch, open_ch;
int i, n = strlen(in);
init(&s);
for(i=0; i<n; i++){
ch = in[i];
switch(ch){
case 'C':
case '[':
case '{':
push(&s, ch);
break;
case ')':
case ']':
case '}':
if(is_empty(&s))
return FALSE;
else{
open_ch = pop(&s);
if((open_ch=='(' && ch!=')') || (open_ch=='[' && ch!=']') || (open_ch=='{' && ch!='}'))
return FALSE;
break;
}
}//switch
}//for
if(!is_empty(&s)) return FALSE;
return TRUE; //괄호 짝 일치
}
○ 스택 응용 : 수식 계산
· 조건
: 일반적인 수식의 중위 표기식을 후위 표기식으로 변환한 후 계산한다.
· 알고리즘 개요
- 중위표기식을 후위표기식으로 변환
: 피연산자의 순서는 동일하고, 연산자의 순서만 변화하므로 피연산자를 만나면 그대로 출력하고 연산자를 만나면 새로운 연산자의 스택 진입 우선순위(in-coming priority, ICP)와 스택 상단에 있는 연산자의 스택 내부 우선순위(in-stack priority, ISP)와 비교하여서 전자가 더 크다면 해당 연산자를 스택에 삽입하고, 작거나 같으면 스택 상단에 있는 연산자를 출력한 후 다시 반복한다. 왼쪽 괄호가 나오면 스택에 삽입하고, 오른쪽 괄호가 나오면 스택에서 왼쪽 괄호가 나올 때까지 모든 연산자를 꺼내어 출력하고 왼쪽 괄호는 삭제한다. 처리할 문자가 남지 않았으면 스택에 남은 모든 연산자를 꺼내어 출력한다.
- 후위표기식의 계산
: 피연산자는 스택에 저장하고, 연산자는 필요한 수만큼(이항연산자라면 2개) 스택에서 피연산자를 꺼내어 연산을 실행한 후 연산 결과를 다시 스택에 저장한다.
/*중위표기식 -> 후위표기식*/
void infix_to_postfix(char exp[], char post[]) {
char token, element; //exp의 문자를 post로 이동시키는 데 필요한 문자 변수
int index = 0, count = 0; //exp의 index를 표기하는 index 변수와 post의 index를 표기하는 count 변수
StackType s; //수식 변환에 사용할 스택 생성
init(&s); //스택 초기화
push(&s, '#'); //스택의 마지막에 추가해 수식이 끝나는 시점 파악.
for (token = exp[index++]; token != ';'; token = exp[index++]) { //;를 제외한 중위표기식을 왼쪽부터 읽어나감.
if (isdigit(token)) post[count++] = token; //피연산자인 경우. post에 바로 저장한 후 count값 증가시켜줌.
else if (token == ')') { //오른쪽 괄호인 경우. 스택 최상단 값이 왼쪽 괄호가 될 때까지 스택에 저장된 값들을 post에 저장한 후 count값 증가시킴.
while (s.stack[s.top] != '(') {
element = pop(&s);
post[count++] = element;
}
pop(&s); //왼쪽 괄호 스택에서 삭제
}
else { //왼쪽 괄호 및 연산자인 경우.
while (isp(s.stack[s.top]) >= icp(token)) { //스택 최상단 값의 ISP값과 새로운 연산자의 ICP값을 비교해 스택 최상단의 ISP가 더 큰 경우.
element = pop(&s); //스택 최상단 값을 post에 저장한 후 count 증가시킴.
post[count++] = element;
}
push(&s, token); //새로운 연산자를 스택에 추가.
}
}
while (peek(&s) != '#') { //스택의 최상단 값이 #(스택 맨 밑에 깔려 있는 값)가 아닌 경우.
element = pop(&s); //스택에서 꺼내서 post에 저장한 후 count 증가시킴.
post[count++] = element;
}
post[count++] = ';'; //post에 세미콜론 저장.
}
/*후위표기식의 값 계산*/
int eval(char exp[]) {
int op1, op2, value, i = 0; //피연산자 저장할 변수 2개, 수식의 값 저장할 변수 value, 반복문에 필요한 변수 i.
int len = strlen(exp); //수식 전체 길이 저장.
char ch; //문자 하나씩 읽어가는 데 필요한 변수.
LinkedStackType s; //수식 값 계산에 사용하는 피연산자 스택
init_link(&s); //스택 초기화
for (i = 0; i < len - 1; i++) { //후위표기식에서 세미콜론을 제외한 부분까지만 시행하는 반복문
ch = exp[i];
if (isdigit(ch)) { //피연산자인 경우.
value = ch - '0'; //char 형을 int 형으로 바꾸기 위한 과정.
push_link(&s, value); //피연산자 스택에 저장.
}
else { //연산자인 경우.
op2 = pop_link(&s); //피연산자 두 개를 스택에서 꺼냄.
op1 = pop_link(&s);
switch (ch) { //연산자 값에 따라 맞는 연산 시행.
case '+': push_link(&s, op1 + op2); break;
case '-': push_link(&s, op1 - op2); break;
case '*': push_link(&s, op1 * op2); break;
case '/': push_link(&s, op1 / op2); break;
case '%': push_link(&s, op1 % op2); break;
case '^': push_link(&s, op1 ^ op2); break;
}
}
}
return pop_link(&s); //수식의 최종 연산 결과를 반환
}
int isp(char ch) { //연산자의 ISP(스택 내부 우선순위) 반환하는 함수
switch (ch) {
case '(':
case '#':
return 0;
case '+':
case '-':
return 12;
case '*':
case '/':
case '%':
return 13;
case '^':
return 14;
}
return -1; //예외
}
int icp(char ch) { //연산자의 ICP(스택 진입 우선순위) 반환하는 함수
switch (ch) {
case '(':
return 20;
case '+':
case '-':
return 12;
case '*':
case '/':
case '%':
return 13;
case '^':
return 15;
}
return -1; //예외
}
'CS > 자료구조(DS)' 카테고리의 다른 글
| 이진트리의 성질, 운행과 응용; 수식표현 트리, 이진트리로의 변환법, 이진탐색트리 (0) | 2021.03.24 |
|---|---|
| 큐의 구현과 응용; 덱(deque) (0) | 2021.03.22 |
| 기본 자료 구조; 리스트의 구현 (0) | 2021.02.15 |
| 기본 자료구조; 연결 리스트 (0) | 2021.02.15 |
| 기본 자료구조; 배열의 개념과 응용(다항식 구현) (0) | 2021.02.05 |