자료구조
자료구조 제 13-1 강 (스택의 개념과 구현)
한 면만 쓴 종이
2022. 3. 13. 23:55
스택
- 일종의 리스트
- 단, 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어짐
- LIFO (Last-In, First-Out)
- 삽입/삭제가 일어나는 쪽을 스택의 top이라고 부름
스택이 지원하는 연산
- push: 스택에 새로운 원소를 삽입하는 연산
- pop: 스택의 top에 있는 원소를 스택에서 제거하고 반환
- peek: 스택 top의 원소를 제거하지 않고 변환
- empty: 스택이 비었는지 검사
스택 응용 예: 괄호 검사 문제
- 입력 수식의 괄호가 올바른지 검사
- 단순히 여는 괄호와 닫는 괄호의 개수 비교만으로는 부족
- 스택을 이용하여 검사
ex) [ a + b * { c / ( d - e ) } ] + ( d / e )
- 여는 괄호는 스택에 push
- 닫는 괄호가 나오면 스택에서 pop한 후, 두 괄호가 같은 유형이어야 함
- 마지막에 스택에 남는 괄호가 없어야 함
/*
* 스택 예제 프로그램
*/
#include <stdio.h>
#include <string.h>
#include "stack.h"
#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_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) {
if (is_empty()) {
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);
}
int is_close(char ch) {
for (int i = 0; i < strlen(CLOSE); i++) {
if (CLOSE[i] == ch)
return i; // 소괄호는 0, 대괄호는 1, 중괄호는 2를 반환한다.
}
return -1; // 여는 괄호가 아니면 -1을 반환한다.
}
int is_open(char ch) {
for (int i = 0; i < strlen(OPEN); i++)
if (OPEN[i] == ch)
return i;
return -1;
}