[자료구조] ep5+) 심볼 균형(스택을 이용한 괄호 쌍의 대칭성 검사)

문제) 스택 응용으로, 키보드로부터 입력된 한 라인의 수식 문장 내 괄호 쌍의 대칭성을 검사하는 프로그램을 작성하세요. 괄호 쌍은 { }, [ ] , ( ), 세 종류가 있다.

※ 주의: 한 개의 수식 문장은 1000개를 넘지 않는 문자로 이루어진다. 수식 문장은 공백문자를 포함할 수 있다. 검사 결과 대칭이 아니면 'Wrong_N'을, 대칭이면 'OK_N'을 출력한다. 여기서 N은 문장 내 괄호의 개수다.

 

test case

 

 

 

 

(전체코드)

#include <stdio.h>

char g_stack[1001] = {0};
int g_top = -1; // 스택의 인덱스값
int g_cnt = 0; // 괄호 총 개수

int isBalanced(char* str);
void push(char bracket);
char pop();
char peek();

int main() {
    char str[1001] = {0};

    gets(str);
    if (isBalanced(str) == 1) {
        printf("OK_%d", g_cnt);
    }
    else {
        printf("Wrong_%d", g_cnt);
    }

    return 0;
}

void push(char bracket) {
    g_stack[++g_top] = bracket;
}

char pop() {
    return g_stack[g_top--];
}

char peek() {
    return g_stack[g_top];
}

int isBalanced(char* str) {
    int res = 1; // True / False
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(' || str[i] == '{' || str[i] == '[') {
            g_cnt++;
            push(str[i]);
        }
        else if (str[i] == ')' || str[i] == '}' || str[i] == ']') {
            g_cnt++;
            if (str[i] == ')') {
                if (peek() != '(') {
                    res = 0;
                }
            }
            else if (str[i] == '}') {
                if (peek() != '{') {
                    res = 0;
                }
            }
            else if (str[i] == ']') {
                if (peek() != '[') {
                    res = 0;
                }
            }
            pop();
        }
    }
    if (res == 0) {
        return 0;
    }

    if (pop() == '(' || pop() == '{' || pop() == '[' || pop() == ')' || pop() == '}' || pop() == ']') {
        return 0;
    }
    else {
        return 1;
    }
}
/*
입력 예시1)
(3+40*(2+(30-7)*2133)
출력 예시1)
Wrong_5

입력 예시2)
3*{4+(2-792)/1} + [3*{4-2* (100 -7)}]
출력 예시2)
OK_10

입력 예시3)
301*{4+(2101-7)/1} + 9*{4-2* (10108-7)}}
출력 예시3)
Wrong_9

입력 예시4)
(3*{4001+(2-7)/1} + [3*{4-2* (1-7)}])
출력 예시4)
OK_12
*/

 

 

 

 

 

 

 

참고 및 출처: 데이터 구조 원리와 응용(국형준교수님)