[자료구조 - C언어] 자료구조 제15강: 스택(Stack) 개념과 구현(1)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. 스택(Stack)

• 스택은 일종의 리스트
  • 일반 리스트: 아무 곳에서나 삽입/삭제 가능
  • 스택: 삽입과 삭제가 한 쪽 끝에서만 이루어짐
    • 삽입과 삭제가 일어나는 쪽을 스택의 top 이라고 부름
• LIFO(Last-In, First-Out): 가장 나중에 들어간 애가 가장 먼저 나옴

 

2. 스택이 지원하는 연산

• push: 스택에 새로운 원소를 삽입하는 연산
• pop: 스택의 top에 있는 원소를 스택에서 제거하고 반환
• peek: 스택의 top에 있는 원소를 제거하지 않고 반환 → 스택은 변화 없음
• is_empty: 스택이 비었는지 검사

 

3. 스택 응용: 괄호 검사 문제

• 입력 수식의 괄호가 올바른지 검사
  • [a + b * { c / (d - e)}] + (d / e)
  • 여는 괄호와 닫는 괄호의 개수 && 괄호의 순서를 확인
  • 스택을 이용해서 검사하기
    • 여는 괄호는 push
    • 닫는 괄호가 나오면 스택에서 pop → 닫는 괄호와, 스택에서 pop 된 여는 괄호의 타입 비교
    • 마지막에 스택에 남는 괄호가 없어야 한다.

//  main.c

#include <stdio.h>
#include <string.h>
#include "stack.h"    //문자들을 저장하는 스택이 stack.c 파일에 구현되어 있다고 가정

#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)         //1. 여는 괄호라면 스택에 push
            push(ch);
        else if(is_close(ch)>-1){  //2. 닫는 괄호라면 스택에서 pop ~ 비교
            if(is_empty()){        //스택이 비었는지 검사 ~ 열리지 않은 괄호가 닫혔다 = 오류
                balanced = 0;
                break;
            }
            char top_ch = pop();   //스택이 비지 않았다면 pop
            if(is_open(top_ch) != is_close(ch)){  //동일 타입의 괄호인지 비교
                balanced = 0;
            }
        }
        index++;
    }
    //balanced가 1이고, 스택이 비어있어야만 리턴
    return  (balanced==1 && is_empty()==1);     
}

//여는 괄호인지 검사
//OPEN = "([{"
int is_open(char ch){
    for(int i=0; i<strlen(OPEN);i++)
        if(OPEN[i]==ch)
            return i;    //소괄호 0,대괄호 1, 중괄호 2 반환
    return -1;           //여는 괄호가 아니라면 -1 반환
}

//닫는 괄호인지 검사
int is_close(char ch){
    for(int i=0; i<strlen(CLOSE); i++){
        if(CLOSE[i] == ch)
            return i;
    }
    return -1;
}

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?time_continue=1368&v=MaLRjxoaowA&feature=emb_title