[C언어] Stack&Queue(7) - balanced 함수 구현하기

Stack&Queue(7) - balanced 함수 구현하기

괄호 문자열이 올바르게 짝지어졌는지 확인하는 함수

주어진 요소 확인하기

구조체

• Stack: (struct) 스택 구조체
  • ll: (LinkedList) 스택 연산 구현을 위한 연결 리스트 구조체
• LinkedList: (struct) 연결 리스트 구조체
  • size: (int field) 연결 리스트 요소 갯수
  • *head: (pointer field) 연결 리스트 첫 노드의 주소
• ListNode: (struct) 노드 구조체
  • item: (int field) 노드의 값
  • *next: (pointer field) 다음 노드의 주소

balanced 함수의 매개 변수

• *expression: (pointer) 검사할 문자열의 문자 주소

 

핵심 아이디어

• 올바른 괄호 문자열인 경우 result = 0(일치) / 아닌 경우 result = 1(불일치)
• 문자가 널 문자일 때까지 문자열을 차례대로 순회
  • 문자가 여는 괄호인 경우 push
  • 문자가 닫는 괄호인 경우
    • 스택이 비어있는 경우 result = 1(불일치)
    • 스택 최상단의 문자와 짝을 이루는 경우 pop
    • 스택 최상단의 문자와 짝을 이루지 않는 경우 result = 1(불일치)
• 모든 문자열 순회 후, 스택이 비어있지 않다면 result = 1(불일치)
• 스택 해제 후 result 값을 반환

 

구현하기

int balanced(char *expression) {
    // 스택 생성 및 초기화 (괄호 쌍을 확인하기 위해 사용)
    Stack *s = malloc(sizeof(Stack));
    s->ll.head = NULL;
    s->ll.size = 0;

    char c, top;
    int i = 0;
    int result = 0;  // 0: balanced, 1: not balanced

    // 문자열의 각 문자를 순회
    while (*(expression + i)) {
        c = *(expression + i);

        // 여는 괄호는 스택에 push
        if (c == '(' || c == '{' || c == '[') {
            push(s, c);
        } else {
            // 닫는 괄호인데 스택이 비었으면 짝 불일치
            if (isEmptyStack(s)) {
                result = 1;
                break;
            }

            // 스택의 top 확인 후 짝이 맞으면 pop
            top = peek(s);
            if ((c == ')' && top == '(') ||
                (c == '}' && top == '{') ||
                (c == ']' && top == '[')) {
                pop(s);
            } else {
                // 닫는 괄호와 열린 괄호가 다르면 짝 불일치
                result = 1;
                break;
            }
        }
        i++;
    }

    // 반복문을 끝까지 돈 후에도 스택에 값이 남아 있다면 짝 불일치
    if (!result && !isEmptyStack(s)) {
        result = 1;
    }

    // 동적 할당된 스택 구조체 해제
    free(s);

    // 결과 반환 (0: balanced, 1: not balanced)
    return result;
}