Data Structure/자료구조

[자료구조] 스택의 응용 - 괄호 검사 문제

lumana 2024. 1. 15. 07:09

스택(Stack)의 응용 - 괄호 검사 문제


괄호 검사 문제

  • 프로그램에서 괄호들의 쌍이 올바르게 사용되었는지를 판단하는데 스택을 이용

  • 괄호의 검사 조건 3가지

    • 왼쪼 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.

    • 같은 종류의 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.

    • 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 교차하면 안 된다.

    • example

      • { A [(i + 1)] = 0; } // 오류 X

      • if ((i == 0) && (j == 0) // 오류 : 조건 1 위반

      • A [ (i + 1] ) = 0; // 오류 : 조건 3 위반

  • 의사 코드

    check_matching(expr):
    
    while (입력 expr이 끝이 나면):
      ch <- expr의 다음 글자
      switch(ch):
        case '(' : case '[' : case '{':
          ch를 스택에 삽입
          break;
        case ')' : case ']' : case '}':
          if (스택이 비어 있으면)
            then 오류
          else 스택에서 open_ch를 꺼낸다
            if (ch와 open_ch와 같은 짝이 아니다면)
              then 오류 보고
          break;
      if (스택이 비어있지 않으면)
        then 오류
  • C Program

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX_STACK_SIZE 100
    
    typedef char element;        // 교체!
                  // 차후에 스택이 필요하면 여기만 복사하여 붙인다. 
                  // ===== 스택 코드의 시작 ===== 
    #define MAX_STACK_SIZE 100
    
    typedef struct {
      element data[MAX_STACK_SIZE];
      int top;
    } StackType;
    
    // 스택 초기화 함수
    void init_stack(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)) {
        fprintf(stderr, "스택 포화 에러\n");
        return;
      }
      else s->data[++(s->top)] = item;
    }
    // 삭제함수
    element pop(StackType *s)
    {
      if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
      }
      else return s->data[(s->top)--];
    }
    // 피크함수
    element peek(StackType *s)
    {
      if (is_empty(s)) {
        fprintf(stderr, "스택 공백 에러\n");
        exit(1);
      }
      else return s->data[s->top];
    }
    
    int check_matching(const char *in) {
      StackType s;
      char ch, open_ch;
      int i, n = strlen(in); // n = 문자열의 길이
      init_stack(&s); // 스택 초기화
    
      for (i = 0; i < n; i++) {
        ch = in[i];
        switch (ch) {
          case '(' : case '[' : case '{' :
            push(&s, ch);
            break;
    
          case ')' : case ']' : case '}' :
            if (is_empty(&s)) {
              return 0;
            }
            else {
              open_ch = pop(&s);
              if ((open_ch == '(' && ch != ')') || (open_ch == '[' && ch != ']') || (open_ch == '{' && ch != '}')) {
                return 0;
              }
            }
            break;
        }
      }
      if (!is_empty(&s)) return 0; // 스택에 괄호가 남아있으면 오류
      return 1;
    }
    
    int main(void)
    {
      char *p = "{ A[(i+1)]=0; }";
      if (check_matching(p) == 1)
        printf("%s 괄호검사성공\n", p);
      else
        printf("%s 괄호검사실패\n", p);
      return 0;
    }

참조) C언어로 쉽게 풀어 쓴 자료구조(천인국, 2016, 생능출판사)