/*
* Program to convert a regular expression to NFA *
* Author: *
	 Venkateswaran S<wenkat.s@gmail.com>
*
*
* Copyright 2004, 2005 VenkatSoft, Inc.
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the
* Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*
*/

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define ALPHABET 1
#define NON_ALPHABET 0
#define MAX 48

// Function Declaration
int createAutomata (struct automata **); // Just initializes default values of the struct Automata
int createNewState (struct state **);    // The same as create Automata but this initializes struct state
struct automata * find_Nfa();            // Recursive Fn that finds the equivalent automata to the given regular expression

struct automata * applyStar (struct automata *);
// Note: The tranistions that are not named are epsilon transitions.
//                          ________
//                         |        |
// converts (R)* to   3--> 1 --R--> 2 --> 4 
//                    |___________________|
                                          
struct automata * applyOr (struct automata *,struct automata *);

//                     ____1 --R--> 2 ____ 
//                    |                   |
// converts R | S to  5                   6
//                    |____3 --S--> 4_____|
																                      
struct automata * applyAnd (struct automata *, struct automata *);   

// converts R . S to  1--R-->2 --> 3--S-->4

int ct = 1;
int flag = 0;
int last_char = NON_ALPHABET;
char cur_char='0';

struct state {
	char *state_number;
	struct state *transition1;
	char v1;
	struct state *transition2;
	char v2;
};

struct automata {
	struct state *start;
	struct state *final;
};

int createNewState (struct state **ptr) {

	struct state *tmp_st;
	tmp_st =(struct state *) malloc(sizeof(struct state));
	if(tmp_st != (struct state *)NULL) {
		//tmp_st->state_number = (char *) malloc(MAX);
		tmp_st->state_number = (char *)NULL;
		tmp_st->transition1 = (struct state *)NULL;
		tmp_st->v1='$';
		tmp_st->transition2 = (struct state *)NULL;
		tmp_st->v2='$';
		*ptr = tmp_st;
		return TRUE;
	}
	else {
		printf("Unable to create a state");
		return FALSE;
	}
}
int createAutomata (struct automata **ptr) {

	struct automata *tmp_automata;
	tmp_automata = (struct automata *)malloc(sizeof(struct automata));
	if(tmp_automata != (struct automata *)NULL) {
		tmp_automata->start = (struct state *)NULL;
		tmp_automata->final = (struct state *)NULL;
		*ptr = tmp_automata;
		return TRUE;
	}
	else {
		printf("Unable to allocate memory for automata");
		return FALSE;
	}
}

struct automata * applyAnd (struct automata * nfa,struct automata * nfa1) {

	if(nfa != (struct automata *)NULL && nfa1 != (struct automata *)NULL) {
		printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa1->start->state_number);
		nfa->final->transition1 = nfa1->start;
		nfa->final = nfa1->final;
		return (nfa);
	}
	else {
		printf("\nUnable to Apply the 'and' operation on the nfa");
		exit(1);
	}
}

struct automata * applyOr (struct automata * nfa,struct automata * nfa1) {

	if(nfa != (struct automata *)NULL && nfa1 != (struct automata *)NULL) {
		
		struct state *tmp1 = (struct state *)NULL;
		struct state *tmp2 = (struct state *)NULL;
		if(createNewState(&tmp1) && createNewState(&tmp2)) {
			tmp1->state_number = (char *) malloc(MAX);
			itoa(ct++,tmp1->state_number,10);
         tmp2->state_number = (char *) malloc(MAX);
			itoa(ct++,tmp2->state_number,10);

			tmp1->transition1 = nfa->start;
			tmp1->v1 = '0';
			tmp1->transition2 = nfa1->start;
			tmp1->v2 = '0';
			printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp1->transition1->state_number);
			printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp1->transition2->state_number);
			
			nfa->final->transition1 = tmp2;
			nfa1->final->transition1 = tmp2;
			printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition1->state_number);
			printf("\n State : %s -- epsilon --> %s",nfa1->final->state_number,nfa1->final->transition1->state_number);
			
			nfa->start = tmp1;
			nfa->final = tmp2;
			return (nfa);
		}
		else {
			printf("\nProbs in creating new states");
			exit(1);
		}
	}
	else {
		printf("\nUnable to Apply the Or operation on the nfa");
		exit(1);
	}
}

struct automata * applyStar (struct automata * nfa) {

	struct state *tmp1 = (struct state *)NULL;
	struct state *tmp2 = (struct state *)NULL;
	if(createNewState(&tmp1) && createNewState(&tmp2)) {
		tmp1->state_number = (char *) malloc(MAX);
		itoa(ct++,tmp1->state_number,10);
		tmp1->transition1 = nfa->start;
		tmp1->v1 = '0'; 
		tmp1->transition2 = tmp2;
		tmp1->v2 = '0';
      tmp2->state_number = (char *) malloc(MAX);
		itoa(ct++,tmp2->state_number,10);
			
		nfa->final->transition1 = nfa->start;
		nfa->final->v1 = '0';
		nfa->final->transition2 = tmp2;
		nfa->final->v2 = '0';
		
		printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition1->state_number);
		printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition2->state_number);

		printf("\n State : %s -- epsilon --> %s",tmp1->state_number,nfa->start->state_number);
		printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp2->state_number);
		
		nfa->start = tmp1;
		nfa->final = tmp2;
		return (nfa);
	}
	else {
		printf("\nUnable to Apply the star operation on the nfa");
		exit(1);
	}
}

struct automata * find_Nfa() {

	struct automata * nfa;
	if(!createAutomata(&nfa)) {
		printf("\nUnable to create automata called nfa");
		exit(1);
	}
	while(cur_char != '$' || cur_char != '\n' || cur_char != '\r') {
		if(flag == 0)
			scanf("%c",&cur_char);
		if( cur_char >= 'a' && cur_char <= 'z') {
			if(last_char == ALPHABET) {
				struct state *tmp1;
				if(createNewState(&tmp1)) {
            	tmp1->state_number = (char *) malloc(MAX);
					itoa(ct++,tmp1->state_number,10);
					nfa->final->transition1 = tmp1;
					nfa->final->v1 = cur_char;
					printf("\n State : %s -- '%c' --> %s",nfa->final->state_number,nfa->final->v1,nfa->final->transition1->state_number);
					nfa->final = tmp1;
				}
			}
			else if (last_char == NON_ALPHABET) {
				struct state *tmp1,*tmp2;
				if(createNewState(&tmp1) && createNewState(&tmp2)) {
					tmp1->state_number = (char *) malloc(MAX);
					itoa(ct++,tmp1->state_number,10);
					tmp2->state_number = (char *) malloc(16);
					itoa(ct++,tmp2->state_number,10);
					tmp1->transition1 = tmp2;
					tmp1->v1=cur_char;
					printf("\n State : %s -- '%c' --> %s",tmp1->state_number,tmp1->v1,tmp1->transition1->state_number);
					nfa->start = tmp1;
					nfa->final = tmp2;
				}
				last_char = ALPHABET;
			}
			else {
				printf("Unable to create 2 new states");
				exit(1);
			}
		}
		else if ( cur_char == '(') {
			last_char = NON_ALPHABET;
			nfa = find_Nfa();
		}
		else if ( cur_char == ')' ) {
			last_char = NON_ALPHABET;
			return (nfa);
		}
		else if (cur_char == '*') {
			last_char = NON_ALPHABET;
			nfa = applyStar(nfa);
		}
		else if (cur_char == '|') {
			last_char = NON_ALPHABET;
			struct automata * temp2;
			if(!createAutomata(&temp2)) {
				printf("\nUnable to create automata called temp2");
				exit(1);
			}
			temp2 = find_Nfa();
			nfa = applyOr(nfa,temp2);
		}
		else if (cur_char == '.') {
			last_char = NON_ALPHABET;
			struct automata * temp3 = (struct automata *)NULL;
			if(!createAutomata(&temp3)) {
				printf("\nUnable to create automata called nfa");
				exit(1);
			}
			temp3 = find_Nfa();
			nfa = applyAnd(nfa,temp3);
		}
		else {
			if(cur_char =='\n' || cur_char == '$' || cur_char == '\r') {
				flag = 1;
				return (nfa);
			}
			else {
				printf("\nInvalid Input Character(s): %c\n",cur_char);
				exit(1);
			}
		}
	}
}

int main() {
	
	struct automata * ans;
	ans = find_Nfa();
	printf("\n\n State : %s is the starting state",ans->start->state_number);
	printf("\n State : %s is the Final State\n",ans->final->state_number);
	return 0;
}