#include<conio.h>
#include<stdio.h>
typedef struct NFAstack
{
 int s,e; //start n end states..
}NFAstack;

typedef struct NFAtable
{
 int s,e; //start n end states..
 char label;//symbol name..
}NFAtable;

NFAstack stack[10];
NFAtable table[25];
int optop=-1,stacktop=-1,tablecnt=0,statecnt=0;

void operate(char op)
{
 NFAstack entry1,entry2; //temp entries..

 if(op=='+')
 {
	//pop 2 entries..
	entry1.s=stack[stacktop].s;
	entry1.e=stack[stacktop--].e;
	entry2.s=stack[stacktop].s;
	entry2.e=stack[stacktop--].e;

	table[tablecnt].s=statecnt;
	table[tablecnt].e=entry1.s;
	table[tablecnt++].label='E';
	table[tablecnt].s=statecnt++;
	table[tablecnt].e=entry2.s;
	table[tablecnt++].label='E';

	table[tablecnt].e=statecnt;
	table[tablecnt].s=entry1.e;
	table[tablecnt++].label='E';
	table[tablecnt].e=statecnt++;
	table[tablecnt].s=entry2.e;
	table[tablecnt++].label='E';

	//push new start and end ..
	stack[++stacktop].s=statecnt-2;
	stack[stacktop].e=statecnt-1;

 }

 else //if(op=='*')
 {
	//pop 1 entry..
	entry1.s=stack[stacktop].s;     //store
	entry1.e=stack[stacktop--].e;   //temporarily..

	table[tablecnt].s=statecnt++;   //new table entries..
	table[tablecnt].e=entry1.s;     //transitions..
	table[tablecnt++].label='E';    //1

	table[tablecnt].e=statecnt++;   //2
	table[tablecnt].s=entry1.e;
	table[tablecnt++].label='E';

	table[tablecnt].s=statecnt-2;   //3
	table[tablecnt].e=statecnt-1;
	table[tablecnt++].label='E';

	table[tablecnt].s=entry1.e;     //4
	table[tablecnt].e=entry1.s;
	table[tablecnt++].label='E';

	//push new start and end ..
	stack[++stacktop].s=statecnt-2;
	stack[stacktop].e=statecnt-1;
 }

}

void alpha(char ch)
{
   //alphabet...
   //create 2 states..push on both stack & table

 stack[++stacktop].s=statecnt++;
 stack[stacktop].e=statecnt++;

 table[tablecnt].s=stack[stacktop].s;
 table[tablecnt].e=stack[stacktop].e;
 table[tablecnt++].label=ch;

}

void nfa2dfa()
{
 int i,j;

 for(i=0;i<=tablecnt;i++)
 {
  if(table[i].label=='E')
  {
	int temp1,temp2;
	if(table[i].s>table[i].e)
	{
	 temp1=table[i].e;//replacer..(lower no.)
	 temp2=table[i].s;
	}
	else
	{
	 temp1=table[i].s;
	 temp2=table[i].e;
	}

	for(j=0;j<=tablecnt;j++)
	{
	 if(table[j].s==temp2)
	 table[j].s=temp1;
	 if(table[j].e==temp2)
	 table[j].e=temp1;

	 if(stack[stacktop].s==temp2)
	 stack[stacktop].s=temp1;
	 if(stack[stacktop].e==temp2)
	 stack[stacktop].e=temp1;
	}
  }//end if..
 }//end of outer for..
}

void main()
{
 char opstack[10],*s;
 NFAstack entry1,entry2;
 int i=0,flag=0;
 char temp;

 clrscr();
 printf("ENTER THE STRING: ");
 scanf(" %s",s);

 while(1)
 {
  char ch;

  if(flag==0)
  ch=s[i++];
  else
  ch=opstack[optop--];

  if(ch=='\0')
  flag=1;
  if(optop==-1 && flag==1)
  break;



  if(isalnum(ch))
  //alphabet...
  //create 2 states..push on both stack & table
    alpha(ch);

  else if(!isalnum(ch))
  {
   //operator...

	if(ch=='*')  //operate immediately...
	operate(ch); //higest priority

	else if( ch=='+'&&
		(opstack[optop]=='('||opstack[optop]==')'))
	opstack[++optop]='+';

	else if(ch=='+'&& (opstack[optop]=='*'))
	{
	 //operate for * and push +
	 operate('*');
	 opstack[optop]='+';
	}

	else if(ch=='(')
	opstack[++optop]='(';

	else if(ch==')')
	{
	 //pop opstack ,operate, and pop ')'
	 char temp=opstack[optop--];
	 if(temp=='('||temp==')')
	 continue;
	 else    //operator..
	 operate(temp);
	}
  }//operator if ends..

 }//end of while..
 getch();

 printf("\n---<NFA TABLE>---");
 i=tablecnt;
 while(i-->0)
 printf("\n %3d -> %3d : %c ",table[i].s,table[i].e,table[i].label);

 printf("\n\nSTART:%3d -> END:%3d",statecnt-2,statecnt-1);

 nfa2dfa();
 printf("\n\n---<DFA TABLE>---");
 while(tablecnt-->0)
 {
  if(table[tablecnt].label!='E')
  printf("\n %3d -> %3d : %c ",table[tablecnt].s,table[tablecnt].e,table[tablecnt].label);
 }
 printf("\n\nSTART:%3d -> END:%3d",stack[stacktop].s,stack[stacktop].e);

 getch();
}