#include<stdio.h>
#include<string.h>
#define MAX 100
int state=0;
typedef struct{
         int start;
         int end;
}
NFA;
void printTrans(int s,char c,int d){
         if(c=='e')
         printf("q%d--e-->q%d\n",s,d);
         else
         printf("q%d--%c-->q%d\n",s,c,d);
}

NFA createBasic(char c){
       NFA n;
       n.start=state++;
       n.end=state++;
       printTrans(n.start,c,n.end);
       return n;
}

NFA concatenate(NFA a,NFA b){
       printTrans(a.end,'e',b.start);
       NFA n;
       n.start=a.start;
       n.end=b.end;
       return n;
}

NFA unionNFA(NFA a,NFA b){
        NFA n;
        n.start=state++;
        n.end=state++;
        printTrans(n.start,'e',a.start);
        printTrans(n.start,'e',b.start);
        printTrans(a.end,'e',n.end);
        printTrans(b.end,'e',n.end);
        return n;
}
NFA kleene(NFA a){
        NFA n;
        n.start=state++;
        n.end=state++;
        printTrans(n.start,'e',a.start);
        printTrans(n.start,'e',n.end);
        printTrans(a.end,'e',a.start);
        printTrans(a.end,'e',n.end);
        return n;
}

int main(){
        char regex[MAX];
        NFA stack[MAX];
        int top=-1;
        printf("Enter simple regex(example:a/b*):");
        scanf("%s",regex);
        int i;
        for(i=0;i<strlen(regex);i++){
                 char c=regex[i];
                 if(c=='a'||c=='b'){
                          stack[++top]=createBasic(c);
                 }

                else if(c=='*'){
                         stack[top]=kleene(stack[top]);
                }
                else if(c=='|'){
                         NFA b=stack[top--];
                         NFA a=stack[top--];
                         stack[++top]=unionNFA(a,b);
                }

        }

        printf("\n Start state:q%d\n",stack[top].start);
        printf("Final state:q%d\n",stack[top].end);
        return 0;
}
