#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdio.h>
#include <assert.h>


#define EPS 256
#define ALL 257
#define MATCH 258

#define MAX_LINE_LENGTH 1024

struct state {
    int c;
    struct state *out1;
    struct state *out2;
    int last_set;
};

typedef struct state state_t;

struct nfa {
    state_t *start;
    state_t *final;
    int n;
};

typedef struct nfa nfa_t;

struct stack {
    int length;
    int capacity;
    nfa_t *data;
};

typedef struct stack stack_t;

struct set {
    int length;
    int id;
    state_t **states;
};

typedef struct set set_t;

state_t *new_state(int c, state_t *out1, state_t *out2){
    state_t* res = malloc(sizeof(state_t));
    res->c = c;
    res->last_set=-1;
    res->out1=out1;
    res->out2=out2;
    return res;
}

nfa_t character(int c){
    state_t* final = new_state(MATCH,NULL,NULL); 
    state_t* init = new_state(c,final,NULL);
    nfa_t res = {init,final,2};
    return res;
}

nfa_t all(void){
    return character(ALL);
}

nfa_t concat(nfa_t a, nfa_t b){
    nfa_t res = {a.start,b.final,a.n+b.n};
    a.final->c=EPS;
    a.final->out1=b.start;
    a.final->out2=NULL;
    return res;

}

nfa_t alternative(nfa_t a, nfa_t b){
    state_t* init = new_state(EPS,a.start,b.start);
    state_t* final = new_state(MATCH,NULL,NULL);
    a.final->c=EPS;
    a.final->out1=final;
    b.final->c=EPS;
    b.final->out1=final;
    nfa_t res={init,final,a.n+b.n+2};
    return res;
}

nfa_t star(nfa_t a){
    state_t* final = new_state(MATCH,NULL,NULL);

    state_t* init = new_state(EPS,a.start,final);
    a.final->c=EPS;
    a.final->out1=a.start;
    a.final->out2=final;
    nfa_t res = {init,final, a.n+2};
    return res;
    

}

nfa_t maybe(nfa_t a){
    state_t* final = new_state(MATCH,NULL,NULL);
    state_t* init = new_state(EPS,a.start,final);
    nfa_t res ={init,final,a.n+1};
    return res;
}

stack_t *stack_new(int capacity){
    stack_t *s = malloc(sizeof(stack_t));
    s->data = malloc(capacity * sizeof(nfa_t));
    s->capacity = capacity;
    s->length = 0;
    return s;
}

void stack_free(stack_t *s){
    free(s->data);
    free(s);
}

nfa_t pop(stack_t *s){
    assert(s->length > 0);
    nfa_t result = s->data[s->length - 1];
    s->length--;
    return result;
}

void push(stack_t *s, nfa_t a){
    assert(s->capacity > s->length);
    s->data[s->length] = a;
    s->length++;
}

nfa_t build(char *regex)
{
    int taille = strlen(regex);
    stack_t* pile = stack_new(2*taille);
    for (int i=0;i<taille;i++){
        if (regex[i]=='*'){
          
            nfa_t a = pop(pile);
            push(pile, star(a));

        }

        else if (regex[i]=='.'){
            push(pile,all());
            
        }
        else if (regex[i]=='|'){ 
            nfa_t a1=pop(pile);
            nfa_t a2 = pop(pile);
            push(pile,alternative(a1,a2));
            
        }
        else if (regex[i]=='?'){
            nfa_t a = pop(pile);
            push(pile,maybe(a));
            
        }
        else if (regex[i]=='@'){
            nfa_t a2=pop(pile);
            nfa_t a1 = pop(pile);
            push(pile,concat(a1,a2));
            
        }
       else if (0<=regex[i]<256)
       {
            push(pile,character(regex[i]));
        
        }
       
    }
    assert(pile->length>0);
    nfa_t res = pop(pile);
    stack_free(pile);
    return(res);
}

bool backtrack(state_t *state, char *s){
    if (state==NULL) return false;
    if (state->c==EPS){
        return(backtrack(state->out1,s)||backtrack(state->out2,s));
    }
    if (s[0]=='\n'||s[0]=='\0'){
        return(state->c==MATCH);
    }
    if(state->c==s[0]||state->c==ALL) return(backtrack(state->out1,&s[1]));
    else return false;

}



bool accept_backtrack(nfa_t a, char *s){
    return backtrack(a.start, s);
}

void match_stream_backtrack(nfa_t a, FILE *in){
    char *line = malloc((MAX_LINE_LENGTH + 1) * sizeof(char));
    while (true) {
       if (fgets(line, MAX_LINE_LENGTH, in) == NULL) break;
        if (accept_backtrack(a, line)) {
            printf("%s", line);
        }
    }
    free(line);
}


set_t *empty_set(int capacity, int id){
    state_t **arr = malloc(capacity * sizeof(state_t*));
    set_t *s = malloc(sizeof(set_t));
    s->length = 0;
    s->id = id;
    s->states = arr;
    return s;
}

void set_free(set_t *s){
    free(s->states);
    free(s);
}


void add_state(set_t *set, state_t *s){
    if (s!=NULL&& s->last_set!=set->id){
        set->states[set->length]=s;
        set->length++;
        s->last_set=set->id;
        if (s->c==EPS){
            add_state(set,s->out1);
            add_state(set,s->out2);
        }
    } 
}



void step(set_t *old_set, char c, set_t *new_set){
    new_set->length=0;
    new_set->id=old_set->id + 1;
    for (int i=0;i<old_set->length;i++){
        if(old_set->states[i]->c==c||old_set->states[i]->c==ALL){
            add_state(new_set,old_set->states[i]->out1);
        }
        
    }
    
}


bool accept_rec(nfa_t a, char* s, set_t* s1, set_t* s2){
    if (s[0]=='\n' || s[0]=='\0'){
        return a.final->last_set == s1->id;


    }
    else{
        step(s1,s[0],s2);
        accept_rec(a,&s[1],s2,s1);
    }
}

bool accept(nfa_t a, char* s, set_t *s1, set_t *s2){
    s1->length =0;
    add_state(s1,a.start);
    return accept_rec(a,s,s1,s2);
}

// bool accept(nfa_t a, char *s, set_t *s1, set_t *s2){
//     s1->length = 0;
//     add_state(s1, a.start);
//     int i = 0;
//     while (s[i] != '\0' && s[i] != '\n') {
//         step(s1, s[i], s2);
//         set_t *tmp = s1;
//         s1 = s2;
//         s2 = tmp;
//         i++;
//     }
//     return a.final->last_set == s1->id;
// }

void match_stream(nfa_t a, FILE *in){
    char *line = malloc((MAX_LINE_LENGTH + 1) * sizeof(char));
    set_t* s1 = empty_set(a.n,0);
    set_t* s2 = empty_set(a.n,1);
    while (true) {
       if (fgets(line, MAX_LINE_LENGTH, in) == NULL) break;
        if (accept(a, line,s1,s2)) {
            printf("%s", line);
        }
        s1->id++;
    }
    free(line);
    set_free(s1);
    set_free(s2);
}

int main(int argc, char* argv[]){
    assert (argc>=2);
    char* regex=argv[1]; FILE* f=stdin;
 
    if (argc>=3){
       char* fichier = argv[2];
       f = fopen(fichier,"r");
    }
    
    nfa_t a = build(regex);
  
    match_stream(a,f);


    return 0;
}