[C / 자료구조] 3주차 실습문제 - 괄호 매칭

괄호 매칭

 

main

#include "stack.h"
#include <string.h>
#include <stdio.h>

int check_matching(const char* input) {
    int i, n = strlen(input);
    char ch, open_ch;

    stackType s;
    init_stack(&s);
    print_stack(&s, input);

    for (i = 0; i < n; i++) {
        ch = input[i];
        switch (ch) {
        case '(': case '{': case '[':
            push(&s, ch);
            print_stack(&s, input + (i + 1));   // * input + (i + 1) 은 input[i] 이후의 문자를 모두 출력
            break;

        case ')': case '}': case ']':
            if (is_empty(&s)) return 0;
            else {
                open_ch = pop(&s);
                print_stack(&s, input + (i + 1));
                if ((open_ch == '(' && ch != ')') ||
                    (open_ch == '{' && ch != '}') ||
                    (open_ch == '[' && ch != ']')) {
                    return 0;
                }
                break;
            }
        default: break;
        }
    }
    if (!is_empty(&s)) return 0;
    return 1;
}

int main(void) {
    char buf[20];
    printf(">>");
    scanf_s("%s", buf, 20);
    if (check_matching(buf) == 1) {
        printf("Sucess\n");
    }
    else {
        printf("fail\n");
    }
    return 0;
}

 

stack.h

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

typedef char element;
typedef struct {
    element* stack;
    int top;
    int capacity;
} stackType;

void init_stack(stackType* s);
int is_full(stackType* s);
int is_empty(stackType* s);
void push(stackType*, element item);
element pop(stackType* s);
element peek(stackType* s);
void delete_stack(stackType* s);
void print_stack(stackType* s);

 

stack.c

#include "stack.h"

void init_stack(stackType* s) {
    s->top = -1;
    s->capacity = 8;
    s->stack = (element*)malloc(sizeof(element) * s->capacity);
}

int is_full(stackType* s) {
    return (s->top >= (s->capacity - 1));
}

int is_empty(stackType* s) {
    return (s->top <= -1);
}

void push(stackType* s, element item) {
    if (is_full(s)) {
        s->capacity *= 2;
        s->stack = (element*)realloc(s->stack, s->capacity * sizeof(element));
        printf("\n*** Extend Array %d => %d ***\n\n", s->capacity / 2, s->capacity);
    }
    s->stack[++(s->top)] = item;
}

element pop(stackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "Stack Underflow\n");
        exit(1);
    }
    return s->stack[(s->top)--];
}

element peek(stackType* s) {
    if (is_empty(s)) {
        fprintf(stderr, "Stack Underflow\n");
        exit(1);
    }
    return s->stack[s->top];
}

void delete_stack(stackType* s) {
    free(s);
}

void print_stack(stackType* s, const char* ch) {
    printf("%-20s [stack]", ch);
    for (int i = 0; i <= s->top; i++) {
        printf("%2c ", s->stack[i]);
    }
    printf("\n");
}