Balanced Brackets

[Data Structures/Stack/Medium]

https://www.hackerrank.com/challenges/balanced-brackets/problem

Balanced Brackets | HackerRank

괄호들을 입력하고 (), {}, [] 짝을 이루고 있는지 확인하는 문제이다.

 

C++ 수업에서 이 문제를 stack으로 구현해서 출력하는 과제를 한 적이 있다.

다만 이번에는 주어진 함수로만 풀기위해 stack을 따로 구조체를 선언하지 않고 풀어서 사용했다. 그리고 push(), pop()함수도 현재 주어지지 않았기 때문에 사용하지 않고 그 원리를 적용시켜 코드로 풀어서 사용했다. 

isBalanced()함수의 for문에서 첫 if문에서는 (, {, [ 일 때 (스택) 배열 arr에 push되는 작업을 하게 했다. 이를 ++index로 해서 현재 저장되어 있는 arr의 가장 윗 index의 위에 저장되도록 한다. 그 다음 ), }, ] 일 때 (스택) arr의 가장 위의 인덱스의 값이 (, {, [ 로 대응되지 않는 경우 balanced되지 않은 것으로 간주하는 경우이다. arr[--index]로 조건문 검사를 마치고 난 후 index가 하나 감소하도록 한다.

 

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();

// Complete the isBalanced function below.

// Please either make the string static or allocate on the heap. For example,
// static char str[] = "hello world";
// return str;
//
// OR
//
// char* str = "hello world";
// return str;
//
char* isBalanced(char* s) {
    char *result;
    char *arr;
    int index=0;
    arr=malloc(sizeof(char)*strlen(s));
    for(int i=0;i<strlen(s);i++){
        arr[i]='\0';
    }
    for(int i=0;i<strlen(s);i++){
        char c=*(s+i);
        if(c=='('||c=='{'||c=='[')
        {
            arr[index++]=c;
        }
        else if((c==')')||(c=='}')||(c==']')){
            if(index==0)    result = "NO";
            if(c==')' && arr[--index]!='('){
                
                return "NO";
            }   
            else if(c=='}' && arr[--index]!='{'){
                
                return "NO";
            }  
            else if(c==']' && arr[--index]!='['){
                
                return "NO";
            }
            arr[index]='\0';  
        }
    }
    
    if(index == 0)  return "YES";
    else {
    return "NO";
    }
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* t_endptr;
    char* t_str = readline();
    int t = strtol(t_str, &t_endptr, 10);

    if (t_endptr == t_str || *t_endptr != '\0') { exit(EXIT_FAILURE); }

    for (int t_itr = 0; t_itr < t; t_itr++) {
        char* s = readline();

        char* result = isBalanced(s);

        fprintf(fptr, "%s\n", result);
    }

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}

계속 arr 배열 malloc해줄 때 malloc(sizeof(strle(s)));로 해서 계속 overflow가 발생해 엄청 길게 입력받았을 때 Abort Called라는 메시지가 떴다...