#include<stdio.h>
#include<stdlib.h>
 
#define MAX_INPUT_SIZE 100
typedef struct 
{
    char *brackets;
    int *positions;
    int arr_pos;
    int data_size;
} Stack;

Stack* initStack() 
{
    Stack *s=(Stack*)malloc(sizeof(Stack));
    if (s==NULL) 
    {
        return NULL;
    }    
    s->brackets=(char*)malloc(10*sizeof(char));
    s->positions=(int*)malloc(10*sizeof(int));
    if (s->brackets==NULL || s->positions==NULL) 
    {
        free(s->brackets);
        free(s->positions);
        free(s);
        return NULL;
    }    
    s->arr_pos=-1;
    s->data_size=10;
    return s;
}

int resizeStack(Stack *s) 
{
    int new_size=s->data_size*2;
    char *new_brackets=(char*)realloc(s->brackets,new_size*sizeof(char));
    int *new_positions=(int*)realloc(s->positions,new_size*sizeof(int));
    if (new_brackets==NULL || new_positions==NULL) 
    {
        free(new_brackets);
        free(new_positions);
        return 0;
    }
    s->brackets = new_brackets;
    s->positions = new_positions;
    s->data_size = new_size;
    return 1;
}

void freeStack(Stack *s) 
{
    if (s!=NULL) 
    {
        free(s->brackets);
        free(s->positions);
        free(s);
    }
}

void push(Stack *stack,const char symb,const int i)
{
                if (stack->arr_pos+1>=stack->data_size)
            {
                if (!resizeStack(stack))
                {
                    printf("too much data");
                    exit(0);
                    return;
                }
            }
            stack->arr_pos++;
            stack->brackets[stack->arr_pos]=symb;
            stack->positions[stack->arr_pos]=i;
}

int is_closed_bracket(const char symb)
{
    switch (symb)
    {
    case '}':
        return 1;
        break;
    case '>':
        return 1;
        break;
    case ')':
        return 1;
        break;
    case ']':
        return 1;
        break;
    default:
        return 0;
        break;
    }
} 

int is_open_bracket(const char symb)
{
    switch (symb)
    {
    case '{':
        return 1;
        break;
    case '<':
        return 1;
        break;
    case '(':
        return 1;
        break;
    case '[':
        return 1;
        break;
    default:
        return 0;
        break;
    }
}   

char opened_for_closed(const char bracket)
{
    switch (bracket)
    {
    case ')':
        return '(';
        break;
    case '}':
        return '{';
        break;  
    case ']':
        return '[';
        break;
    case '>':
        return '<';
        break;
    }
}

char closed_for_opened(const char bracket)
{
    switch (bracket)
    {
    case '(':
        return ')';
        break;
    case '{':
        return '}';
        break;  
    case '[':
        return ']';
        break;
    case '<':
        return '>';
        break;
    }
}

char* read_input()
{
    int chars=10;
    char *str=(char *)calloc(chars,sizeof(char));
    int countinput=0;
    int c;
    int size_str=0;
    while ((c=getchar())!= '\n'&& c!=EOF)
    {
        if (size_str>=MAX_INPUT_SIZE)
        {
            return 0;
        }
        if (size_str+1>=chars) 
        {
            chars*=2;
            if (chars>MAX_INPUT_SIZE+1) 
            {
                chars=MAX_INPUT_SIZE+1;
            }
            char *newStr=(char*)realloc(str,chars*sizeof(char));
            if (newStr==NULL) 
            {
                free(str);
                return 0;
            }
            str=newStr;
        }
        str[size_str]=(char)c;
        size_str++;   
    }
    str[size_str]='\0';
    return str;
}

int main()
{
    Stack *stack = initStack();
    char* code=NULL;
    if (stack==NULL)
    {
        return 0;
    }   
    code=read_input();
    if (code==NULL)
    {
        freeStack(stack);
        return 0;
    }
    printf("Read: %s\n", code);
    for (int i = 0; code[i]!='\0'; i++)
    {
        char symb=code[i];
        if (is_open_bracket(symb))
        {
            push(stack, symb, i);
        }
        else if (is_closed_bracket(symb))
        {
            if (stack->arr_pos<0)
            {
                printf("Unexpected closing bracket %c in %d\n", symb, i);
                free(code);
                freeStack(stack);   
                return 0;
            }
            char previous=stack->brackets[stack->arr_pos];
            if (previous==opened_for_closed(symb))
            {
                stack->arr_pos--;                   
            }
            if (is_open_bracket(previous) && closed_for_opened(previous)!=symb)
            {
                printf("Crossed bracket %c in %d, expected %c \n", symb, i, closed_for_opened(previous));
                free(code);
                freeStack(stack);
                return 0;
            }
            
        }
    }
       
    if (stack->arr_pos>=0) 
    {
        printf("Missing closing brackets: "); 
        for (int i = stack->arr_pos; i != -1; i--)
        {
            printf("%c", closed_for_opened(stack->brackets[i]));
        }
        printf("\n");
        free(code);
        freeStack(stack);
        return 0;
    }
    printf("All brackets OK\n");
    free(code);
    freeStack(stack);
    return 0;
}