이번시간 알아 볼 것.
스택은 일종의 리스트인데 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어진다
LIFO(Last-In, First-Out)이라고도 한다.
삽입/삭제가 일어나는 쪽을 스택의 top라고 부른다.
1)스택의 기본개념
o push:스택에 새로운 원소를 사입합는 연산
pop: 스택의 top에 있는 원소를 스택에서 제거하고 반환
peek:스택 top의 원소를 제거하지 않고 반환
empty:스택이 비었는지 검사
push("Rich");
push("Rich");
push("Rich");
push("Rich");
push("Rich");
char *str1 = peek();
char *str2 = pop();
push("Phillp");
//스택의 상태는 (a)가 됨
//str1은 "Jonathan"이 됨
//Str2는 "Jonathan"이 되고 스택의 상태는 (b)로 바뀜
//스택의 상태가 (c)로 바뀜
2)스택 응용 예: 괄호 검사 문제
o입력수식의 괄호가 올바른지 검사
예[a + b *{c/ ( d-e) } ] +(d/e)
o단순히 여는 괄호와 닫는 고라호의 개수 비교 만으로는 부족
o스택을 이용하여 검사(순서유의해서 검사)
o여는 괄호는 스택에 push
o닫는 괄호가 나오면 스택에서 pop한 후, 두 괄호가 같은 유형인지
o마지막에 스택에 남는 괄호가 없어
ex)[{(})] x //단지 개수를 카운트하는 것은 오류.
[{()()}()] o //순서가 맞아야 한다.
#include <stdio.h>
#include <string.h>
#include "stack.h" //문자(char)들을 저장하는 스택이 여기에 구현되어있다 가정.
#define MAX_LENGTH 100
char OPEN[] = " ( [ { ";
char CLOSE[] = " ) ] } ";
int is_balanced(char *expr);
int is_open(char ch);
int is_close(char ch);
int main()
{
char expr[MAX_LENGTH];
scanf("%s", expr);
if(is_balanced(expr))
printf("%s: balanced.\n", expr);
else
printf("%s: unbalanced.\n", expr);
}
int is_close(char ch) {
for(int i=0; i<strlen(CLOSE); i++){
if(CLOSE[I] == ch) //소괄호는 0,대괄호는 1, 중괄호는 2를 반환하고
return i;
}
return -1; //여는 괄호가 아니면 -1을 반환한다.
}
int is_open(char ch) {
for(int i=0; i<strlen(OPEN); i++)
if(OPEN[i] == ch)
return i;
return -1;
}
int is_balanced(char *expr) {
int balanced =1;
int index = 0;
while(balanced && index < strlen(expr)) {
char ch = expr[index];
if(is_open(ch)>-1) //여는괄호는 스택에 push한
push(ch);
else if(is_close(ch)>-1) { // -1이 아닌건 닫는 괄호는 스택에 push한다.
if(is_empty()) { //pop하기전에 스택이 비었는지 체크한다.
balanced = 0;
break;
}
char top_ch = pop(); //닫는 괄호가 나오면 스택에서 pop
if(is_open(top_ch) != is_close(ch)) { //같은 유형의 괄호인지 검사
balanced = 0;
}
}
index ++;
}
return (balanced == 1 && is_empty() == 1);
}
0 comments:
Post a Comment