C언어에서 스택을 활용한 괄호 검사 프로그램 작성법

C언어에서 프로그래밍을 하다 보면 여는 괄호와 닫는 괄호가 짝을 이루지 않거나, 잘못된 순서로 사용되는 경우를 방지하기 위해 괄호 검사 프로그램을 작성하는 경우가 많습니다. 이 과정에서 스택 자료구조는 효과적인 도구로 활용됩니다. 본 기사에서는 스택의 기본 개념과 함께, 이를 활용하여 괄호 검사 프로그램을 구현하는 방법을 단계적으로 설명합니다. 특히 C언어를 사용해 직접 스택을 구현하고, 이를 응용하여 실질적인 문제를 해결할 수 있는 방법을 소개합니다. 이를 통해 독자는 스택의 동작 원리를 이해하고, C언어 프로그래밍 능력을 향상시킬 수 있을 것입니다.

스택과 괄호 검사의 개념

스택은 데이터를 선형으로 저장하는 자료구조로, 후입선출(LIFO, Last In First Out)의 원칙을 따릅니다. 즉, 가장 나중에 추가된 데이터가 가장 먼저 제거됩니다. 이러한 특성은 괄호 검사와 같은 문제를 해결하는 데 매우 적합합니다.

스택 자료구조의 기본 개념

스택은 아래와 같은 두 가지 주요 연산을 지원합니다:

push: 스택의 맨 위에 데이터를 추가합니다.
pop: 스택의 맨 위 데이터를 제거하고 반환합니다.

이 외에도 현재 스택의 맨 위 데이터를 확인하는 peek 연산이 유용하게 사용됩니다.

괄호 검사 프로그램의 원리

괄호 검사란 주어진 문자열에서 여는 괄호와 닫는 괄호가 올바르게 짝을 이루는지 확인하는 작업입니다.
예를 들어:

올바른 괄호: (), ([]), {[()()]}
잘못된 괄호: (], ([)], {[}

스택을 활용하면 다음과 같은 방식으로 괄호 검사를 수행할 수 있습니다:

문자열을 처음부터 끝까지 읽습니다.
여는 괄호 (, [, {를 만나면 스택에 push합니다.
닫는 괄호 ), ], }를 만나면 스택에서 pop하여 짝이 맞는지 확인합니다.
문자열 끝까지 검사 후 스택이 비어 있다면 올바른 괄호 조합입니다.

스택을 사용하면 괄호의 짝을 효율적으로 관리할 수 있어 복잡한 문자열에서도 빠르게 검증할 수 있습니다.

스택을 활용한 괄호 검사 알고리즘

스택 자료구조를 활용하면 괄호 검사를 간단하고 효과적으로 수행할 수 있습니다. 아래는 괄호 검사 알고리즘의 단계별 동작 원리입니다.

알고리즘의 주요 단계

초기화

빈 스택을 생성합니다.
입력 문자열을 처음부터 끝까지 순회할 준비를 합니다.

여는 괄호 처리

문자열을 한 글자씩 읽으면서 여는 괄호 (, [, {를 만나면 스택에 push합니다.

닫는 괄호 처리

닫는 괄호 ), ], }를 만나면 다음을 수행합니다:
- 스택이 비어 있는 경우: 괄호가 올바르지 않은 것으로 판별합니다.
- 스택에서 pop하여 꺼낸 여는 괄호와 현재 닫는 괄호가 짝을 이루는지 확인합니다.
- 짝이 맞지 않으면 괄호가 올바르지 않은 것으로 판별합니다.

문자열 끝까지 검사 후 확인

문자열 순회가 끝난 후 스택이 비어 있으면 괄호가 올바르게 짝지어졌음을 의미합니다.
스택에 값이 남아 있으면 여는 괄호가 닫히지 않은 경우이므로 잘못된 괄호로 판단합니다.

의사 코드

function checkBrackets(input):
    stack = new Stack()
    for char in input:
        if char is an opening bracket:
            stack.push(char)
        else if char is a closing bracket:
            if stack.isEmpty():
                return false
            top = stack.pop()
            if not isMatchingPair(top, char):
                return false
    return stack.isEmpty()

짝 확인 함수

짝이 맞는 여는 괄호와 닫는 괄호를 비교하는 함수는 다음과 같이 정의할 수 있습니다:

bool isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

시간 복잡도

O(n): 문자열의 길이를 n이라고 할 때, 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다.
스택 연산인 push와 pop은 각각 O(1)이므로 전체 알고리즘의 효율성이 높습니다.

이 알고리즘은 간단하면서도 다양한 괄호 검사를 처리할 수 있어 프로그래밍 문제에서 널리 사용됩니다.

C언어로 스택 구현하기

스택은 배열이나 연결 리스트를 사용해 구현할 수 있습니다. 여기서는 배열 기반의 스택 구현을 소개합니다.

스택 구조체 정의

스택은 데이터를 저장할 배열과 현재 스택의 맨 위를 가리키는 인덱스를 포함하는 구조체로 정의됩니다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100 // 스택의 최대 크기

typedef struct {
    char items[MAX];
    int top;
} Stack;

스택 초기화 함수

스택을 초기화하여 사용 준비를 합니다.

void initStack(Stack* stack) {
    stack->top = -1; // 스택이 비어 있음을 나타냄
}

스택 연산 함수

스택의 주요 연산인 push, pop, peek, isEmpty 함수를 구현합니다.

bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

bool isFull(Stack* stack) {
    return stack->top == MAX - 1;
}

void push(Stack* stack, char item) {
    if (isFull(stack)) {
        printf("Stack overflow!\n");
        exit(EXIT_FAILURE);
    }
    stack->items[++(stack->top)] = item;
}

char pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow!\n");
        exit(EXIT_FAILURE);
    }
    return stack->items[(stack->top)--];
}

char peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        exit(EXIT_FAILURE);
    }
    return stack->items[stack->top];
}

스택 사용 예시

스택을 초기화하고, 데이터를 push 및 pop하는 예제입니다.

int main() {
    Stack stack;
    initStack(&stack);

    push(&stack, '(');
    push(&stack, '{');
    printf("Top element: %c\n", peek(&stack)); // 출력: {

    char popped = pop(&stack);
    printf("Popped element: %c\n", popped); // 출력: {
    printf("Is stack empty? %s\n", isEmpty(&stack) ? "Yes" : "No"); // 출력: No

    return 0;
}

요약

위 코드는 배열 기반의 스택을 C언어로 구현한 것입니다. 초기화, 데이터 추가(push), 제거(pop), 최상위 요소 확인(peek)과 같은 주요 연산을 포함하고 있습니다. 이 스택 구현은 괄호 검사 프로그램에서 직접 사용될 것입니다.

괄호 검사 프로그램 작성

이 섹션에서는 스택을 활용해 C언어로 괄호 검사 프로그램을 작성하는 방법을 설명합니다. 구현된 스택 코드를 바탕으로 여는 괄호와 닫는 괄호의 짝을 검사하는 프로그램을 작성합니다.

프로그램의 주요 로직

문자열을 처음부터 끝까지 읽습니다.
여는 괄호 (, [, {를 만나면 스택에 push합니다.
닫는 괄호 ), ], }를 만나면 스택에서 pop하여 짝이 맞는지 확인합니다.
문자열 검사가 끝난 후, 스택이 비어 있으면 올바른 괄호 조합입니다.

코드 구현

다음은 괄호 검사 프로그램의 구현 예제입니다.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100

typedef struct {
    char items[MAX];
    int top;
} Stack;

void initStack(Stack* stack) {
    stack->top = -1;
}

bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

bool isFull(Stack* stack) {
    return stack->top == MAX - 1;
}

void push(Stack* stack, char item) {
    if (isFull(stack)) {
        printf("Stack overflow!\n");
        exit(EXIT_FAILURE);
    }
    stack->items[++(stack->top)] = item;
}

char pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow!\n");
        exit(EXIT_FAILURE);
    }
    return stack->items[(stack->top)--];
}

char peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty!\n");
        exit(EXIT_FAILURE);
    }
    return stack->items[stack->top];
}

bool isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

bool checkBrackets(const char* str) {
    Stack stack;
    initStack(&stack);

    for (int i = 0; i < strlen(str); i++) {
        char ch = str[i];

        // 여는 괄호는 스택에 push
        if (ch == '(' || ch == '[' || ch == '{') {
            push(&stack, ch);
        }
        // 닫는 괄호는 스택에서 pop 후 비교
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (isEmpty(&stack) || !isMatchingPair(pop(&stack), ch)) {
                return false;
            }
        }
    }

    // 스택이 비어 있으면 괄호가 올바르게 짝지어짐
    return isEmpty(&stack);
}

int main() {
    const char* input = "{[()]}";

    if (checkBrackets(input)) {
        printf("The brackets are balanced.\n");
    } else {
        printf("The brackets are not balanced.\n");
    }

    return 0;
}

프로그램 설명

스택 초기화: initStack으로 빈 스택 생성.
여는 괄호 처리: push를 사용해 여는 괄호를 스택에 저장.
닫는 괄호 처리: pop으로 스택에서 여는 괄호를 제거하고, isMatchingPair로 짝이 맞는지 확인.
최종 확인: 문자열 순회가 끝난 후 스택이 비어 있는지 검사.

실행 예시

입력: {[()]}
출력: The brackets are balanced.

입력: {[(])}
출력: The brackets are not balanced.

요약

이 프로그램은 스택을 활용해 효율적으로 괄호의 짝을 검사합니다. 입력 문자열이 균형 잡힌 괄호를 가지는지 확인할 수 있으며, 코드의 간결성과 확장성이 높습니다.

다양한 괄호 유형 처리

기본적인 괄호 검사 프로그램은 한 가지 유형의 괄호만 처리할 수 있습니다. 그러나 실제 사용 사례에서는 여러 종류의 괄호(예: (), {}, [])를 동시에 처리해야 하는 경우가 많습니다. 이 섹션에서는 다양한 괄호 유형을 효과적으로 처리할 수 있도록 프로그램을 확장하는 방법을 소개합니다.

여러 유형의 괄호 검사 원리

여러 유형의 괄호를 처리하기 위해 다음의 확장된 로직을 사용합니다:

문자열을 순회하며 여는 괄호((, [, {)를 스택에 저장합니다.
닫는 괄호(), ], })를 만나면 스택에서 pop하여 짝이 맞는지 확인합니다.
짝이 맞지 않는 경우, 즉시 잘못된 괄호로 판단합니다.
문자열이 끝난 후, 스택이 비어 있으면 모든 괄호가 올바르게 짝지어진 것입니다.

코드 구현

기존의 checkBrackets 함수는 이미 여러 유형의 괄호를 처리할 수 있는 형태로 설계되었습니다. 하지만 이를 조금 더 확장하고 다양한 입력을 처리하는 예제를 추가해보겠습니다.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100

typedef struct {
    char items[MAX];
    int top;
} Stack;

void initStack(Stack* stack) {
    stack->top = -1;
}

bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

bool isFull(Stack* stack) {
    return stack->top == MAX - 1;
}

void push(Stack* stack, char item) {
    if (isFull(stack)) {
        printf("Stack overflow!\n");
        exit(EXIT_FAILURE);
    }
    stack->items[++(stack->top)] = item;
}

char pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow!\n");
        exit(EXIT_FAILURE);
    }
    return stack->items[(stack->top)--];
}

bool isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

bool checkBrackets(const char* str) {
    Stack stack;
    initStack(&stack);

    for (int i = 0; i < strlen(str); i++) {
        char ch = str[i];

        // 여는 괄호는 스택에 push
        if (ch == '(' || ch == '[' || ch == '{') {
            push(&stack, ch);
        }
        // 닫는 괄호는 스택에서 pop 후 비교
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (isEmpty(&stack) || !isMatchingPair(pop(&stack), ch)) {
                return false;
            }
        }
    }

    // 스택이 비어 있으면 괄호가 올바르게 짝지어짐
    return isEmpty(&stack);
}

int main() {
    const char* inputs[] = {
        "{[()]}",    // 올바른 괄호
        "{[(])}",    // 잘못된 괄호
        "(([]{}))",  // 올바른 괄호
        "{[}",       // 잘못된 괄호
    };

    for (int i = 0; i < 4; i++) {
        printf("Input: %s\n", inputs[i]);
        if (checkBrackets(inputs[i])) {
            printf("Result: The brackets are balanced.\n\n");
        } else {
            printf("Result: The brackets are not balanced.\n\n");
        }
    }

    return 0;
}

코드 설명

다양한 괄호 처리: isMatchingPair 함수에서 여는 괄호와 닫는 괄호의 짝을 비교하여 모든 유형의 괄호를 처리합니다.
다양한 입력 테스트: inputs 배열을 사용해 여러 입력을 테스트하며 프로그램의 동작을 확인합니다.

실행 결과

입력: {[()]}
출력: The brackets are balanced.

입력: {[(])}
출력: The brackets are not balanced.

입력: (([]{}))
출력: The brackets are balanced.

입력: {[}
출력: The brackets are not balanced.

요약

이 확장된 프로그램은 다양한 괄호 유형을 효율적으로 처리할 수 있습니다. 입력 문자열에 여러 괄호 유형이 포함된 경우에도 올바른 괄호 조합인지 검사할 수 있습니다. 이를 통해 더욱 현실적인 문제를 해결할 수 있는 도구로 활용할 수 있습니다.

예외 상황 처리와 디버깅

괄호 검사 프로그램은 간단해 보이지만, 실제 사용 시 다양한 예외 상황이 발생할 수 있습니다. 이 섹션에서는 예외 상황을 처리하고 디버깅할 수 있는 방법을 설명합니다.

주요 예외 상황

잘못된 입력

문자열에 괄호 이외의 문자가 포함된 경우.
빈 문자열이 입력된 경우.

스택 오버플로우

매우 긴 문자열에서 스택의 크기를 초과하는 경우.

스택 언더플로우

닫는 괄호가 여는 괄호보다 많아 스택이 비었을 때 pop을 호출하는 경우.

예외 처리 로직

문자 유효성 검사
입력 문자열에 괄호 이외의 문자가 포함된 경우 무시하거나 오류 메시지를 출력합니다.

   if (ch != '(' && ch != ')' && ch != '[' && ch != ']' && ch != '{' && ch != '}') {
       printf("Invalid character detected: %c\n", ch);
       return false;
   }

빈 입력 처리
입력 문자열이 빈 경우 스택을 확인하지 않고 바로 결과를 반환합니다.

   if (strlen(str) == 0) {
       printf("Empty input string.\n");
       return true; // 빈 문자열은 균형 잡힌 상태로 간주
   }

스택 크기 초과 방지
스택이 가득 찼을 때 push를 호출하면 오류를 출력하고 프로그램을 종료합니다.

   if (isFull(&stack)) {
       printf("Stack overflow: Input too long.\n");
       return false;
   }

스택이 비었을 때 pop 호출 방지
스택이 비어 있을 때 pop을 호출하면 잘못된 괄호로 간주하고 바로 종료합니다.

   if (isEmpty(&stack)) {
       printf("Stack underflow: Too many closing brackets.\n");
       return false;
   }

코드 예제: 예외 처리 추가

다음은 예외 처리 로직이 추가된 checkBrackets 함수입니다.

bool checkBrackets(const char* str) {
    Stack stack;
    initStack(&stack);

    for (int i = 0; i < strlen(str); i++) {
        char ch = str[i];

        // 유효하지 않은 문자 처리
        if (ch != '(' && ch != ')' && ch != '[' && ch != ']' && ch != '{' && ch != '}') {
            printf("Invalid character detected: %c\n", ch);
            return false;
        }

        // 여는 괄호 처리
        if (ch == '(' || ch == '[' || ch == '{') {
            if (isFull(&stack)) {
                printf("Stack overflow: Input too long.\n");
                return false;
            }
            push(&stack, ch);
        }

        // 닫는 괄호 처리
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (isEmpty(&stack)) {
                printf("Stack underflow: Too many closing brackets.\n");
                return false;
            }
            if (!isMatchingPair(pop(&stack), ch)) {
                printf("Mismatched brackets detected.\n");
                return false;
            }
        }
    }

    // 스택이 비어 있어야 균형 잡힌 상태
    if (!isEmpty(&stack)) {
        printf("Unmatched opening brackets remain in the stack.\n");
        return false;
    }

    return true;
}

디버깅 팁

중간 결과 출력: 스택의 상태를 디버깅 로그로 출력해 프로그램의 동작을 확인합니다.

  printf("Stack after processing %c: ", ch);
  for (int j = 0; j <= stack.top; j++) {
      printf("%c ", stack.items[j]);
  }
  printf("\n");

문제 입력 검증: 오류가 발생한 입력 문자열을 기록하고 반복 테스트합니다.
모의 데이터: 테스트 케이스를 만들어 프로그램의 안정성을 검증합니다.

테스트 케이스

입력 문자열	예상 결과	출력 메시지
`{[()]}`	균형 잡힘 (true)	정상 작동
`{[(])}`	균형 잡히지 않음 (false)	`Mismatched brackets detected.`
`{[a+b]*(c-d)}`	유효하지 않음 (false)	`Invalid character detected: a`
`{[}`	균형 잡히지 않음 (false)	`Unmatched opening brackets remain.`

요약

이 프로그램은 예외 상황 처리와 디버깅 기능을 강화하여 입력값의 오류를 감지하고 프로그램의 안정성을 높입니다. 이를 통해 현실적인 입력값과 다양한 시나리오에서 안정적으로 동작하도록 개선할 수 있습니다.

요약

스택 자료구조를 활용한 괄호 검사 프로그램은 여는 괄호와 닫는 괄호의 짝을 효율적으로 검사하는 방법을 제공합니다. 본 기사에서는 C언어로 스택을 구현하고 이를 기반으로 괄호 검사 알고리즘을 작성하는 방법을 설명했습니다. 다양한 유형의 괄호를 처리하고, 예외 상황에 대한 처리 및 디버깅 기능을 통해 프로그램의 안정성을 향상시킬 수 있었습니다.

스택은 간단하지만 강력한 자료구조로, 괄호 검사뿐만 아니라 다양한 프로그래밍 문제에서 응용할 수 있습니다. 이를 통해 독자는 C언어의 기본 개념과 자료구조 활용 능력을 한층 더 발전시킬 수 있을 것입니다.