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

스택(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, 생능출판사)