[C 자료구조] Stack - Balanced Brackets

0) 제목

• Hackerrank 의 Linked Lists 부분의 Balanced Brackets 문제입니다.

• 스택을 이요한 괄호 맞추기? 정도 되겠습니다.

• C언어를 이용하여 풀었습니다.

1) 문제설명

• N개의 갯수만큼의 쿼리(줄) 을 입력받는다.

• 각 줄은 "[{()}]" 등이 input으로 들어온다.
  

• 여는괄호와 닫는괄호가 딱 맞아 떨어지면 YES를 출력하고 그렇지 않으면 NO를 출력하는 문제이다.

2) 풀이과정

• 스택(stack)을 이용해서 풀었습니다.

• 2가지 경우가 있다고 생각했습니다.

• 첫 번째 경우는 여는 괄호가 들어오고 닫는 괄호와 맞지 않는 경우.

• 두 번째 경우는 닫는 괄호만 들어오는 경우.

• 두가지 상황을 예외라고 생각하고 문제를 풀었습니다.

3) 함수설명

• StackInit : 스택 초기화.

• isEmpty : 스택이 비어있는지 확인하고 비었으면 TRUE, 아니면 FALSE 반환.

• push : 스택에 data를 집어넣고 스택의 top을 하나 증가.(top++)

• pop : 스택에 있는 data를 빼면서 스택의 top을 감소.(--top)

• isOpen : 문자가 (, {, [ 여는 괄호 이면 TRUE, 아니면 FALSE 반환.

• isEqual : 문자가 ), }, ] 닫는 괄호 일때, 각 닫는 괄호에 맞는 여는 괄호가 스택의 top에 존재하는지 확인.

4) 코드

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
//문제에서 주어진 n의 범위가 10^3 까지 이고, 데이터 타입이 char 이므로 고정된 메모리로 할당한다.
#define MAX_LEN 1000
#define TRUE 1
#define FALSE 0
typedef char Data;
 
 
/////////////////////stack///////////////////// 
 
typedef struct _stack{
    Data arr[MAX_LEN];
    int top;
} Stack;
 
void StackInit(Stack * sp){
    sp->top = -1;
}
 
int isEmpty(Stack *sp){
    if(sp->top == -1) return TRUE;
    return FALSE;
}
 
void push(Stack *sp, Data data){
    //check full.
    if((sp->top)+1 >= MAX_LEN) return;
    sp->arr[++(sp->top)] = data;
}
 
Data pop(Stack *sp){
    if(isEmpty(sp)) return ' ';
    return sp->arr[(sp->top)--];
}
 
Data peek(Stack *sp){
    if(isEmpty(sp)) return ' ';
    return sp->arr[(sp->top)];
}
 
 
///////////////////function///////////////////
 
int isOpen(Data data){
    if(data == '(' || data == '[' || data == '{') return TRUE;
    return FALSE;
}
 
int isEqual(Stack *stack, Data data){
    if(data == ')' && peek(stack) == '(') return TRUE;
    if(data == ']' && peek(stack) == '[') return TRUE;
    if(data == '}' && peek(stack) == '{') return TRUE;
    return FALSE;
}
 
 
/////////////////////main/////////////////////
 
int main(){
    int n; 
    int len;
    int check;  //check equal brackets
    Stack stack;
    scanf("%d",&n);
    
    for(int i = 0; i < n; i++){
        check =1;
        StackInit(&stack);  //stack init.
        char* str = (char *)malloc(10240 * sizeof(char));
        scanf("%s",str);
 
        len = strlen(str);  //get length of str.
 
        for(int j=0; j<len;j++){
            if(isOpen(str[j])){ //case (, {, [, 이면 push.
                push(&stack, str[j]);
            }else if(isEqual(&stack, str[j])){  //case ),},] 일때 각각 맞는지. 맞으면 pop.
                pop(&stack);
            }else{
                check =0;
                break;
            }
        }
       
        if(check == 1 && isEmpty(&stack)){
            printf("YES\n");            
        }else{
            printf("NO\n");
        }
 
    } 
    return 0;
}

5) 인증

경로 : Dashboard>Data Structures>Stacks>Balanced Brackets

출처 : [HackerRank] https://www.hackerrank.com/challenges/balanced-brackets/problem

더 나은 코드로 보완 할 곳이 있으면 말씀해주세요.

부족한 코드 많은 지적 부탁드립니다.