re2enfa.java

Regular Expression to Epsilon-NFA

import java.util.LinkedList;
import java.io.*;
import java.math.*;
import java.util.*;

public class RE2eNFA {
	LinkedList<String> list = new LinkedList<String>();
	LinkedList<Integer> Final = new LinkedList<Integer>();
	LinkedList<Integer> Transport = new LinkedList<Integer>();
	LinkedList<String> text = new LinkedList<String>();
	private String content = "";
	
    public RE2eNFA() {
    }
    public static void main(String[] arg){
    	RE2eNFA RTF = new RE2eNFA();
    	String RE;
    //	RE = "1+";
   		RE = "((0|1)1)*";
    	InfixToPostfix ITP = new InfixToPostfix(RE);
    	System.out.println("Postfix = "+ITP.getPostfix());
    	RTF.linkedList(ITP.getPostfix());
    	RTF.toArray();
    	SVG S1 = new SVG(RTF.toString(),RE);	
    }
	public void toArray(){	
		int[] input0 ,input1,epsilon;				
		int[] nextInput = new int[2];
		int s = 0,c=0, input=0;
		int size = 1;
		while(s< list.size()){
			for(int i =0 ; i<list.get(s).length(); i++){
				if(list.get(s).charAt(i) == 's' || list.get(s).charAt(i) == 'e' ){
					Transport.add(i);
					c++;
				}
				if(list.get(s).charAt(i) == '_'){
					nextInput[input] = i;
					input = 1;
					if(c>size){
						size =c;	
					}					
					c=0;					
				}
			}
			if(c>size){
				size =c;
			}			
			c=0;
			input0= new int[size];
			input1 =new int[size];
			epsilon=new int[size];
			for(int i=0 ; i<size ; i++){
				input0[i] = 0;
				input1[i] = 0;
				epsilon[i] = 0;
			}						
			int i =0;
			int state =1;
			int i2 =0;
			while( nextInput[0] > Transport.get(i)){
				if(list.get(s).charAt(Transport.get(i)+1) != 'n'){
				
					if(nextInput[0] > Transport.get(i+1)){
						state = Integer.parseInt(list.get(s).substring(Transport.get(i)+1,Transport.get(i+1)))+1;												
					}else{
						state = Integer.parseInt(list.get(s).substring(Transport.get(i)+1,nextInput[0]))+1;				
					}
					input0[i] = state;
				}else{
					input0[i] = 0;
				}
				i++;
			}	

			int x =-1, y;	
			while( nextInput[1] > Transport.get(i)){			
				y=0;
				if(list.get(s).charAt(Transport.get(i)+1) != 'n'){
					if(nextInput[1] > Transport.get(i+1)){
				       	state = Integer.parseInt(list.get(s).substring(Transport.get(i)+1,Transport.get(i+1)))+1;
					}else{
						state = Integer.parseInt(list.get(s).substring(Transport.get(i)+1,nextInput[1]))+1;				
					}										
					for(int j =0 ; j<size ; j++){
						if(state == input0[j]){
							x =j;
							y=1;
							if(input1[x] != 0){
								input1[i2] = input1[x];
								i2++;
							}
							input1[x] =state;																					
						}							
					}					
					if(y == 0 ){
						if(i2== x) i2= x+1;
						input1[i2]= state;
						i2++;						
					}																		
				}else{
					input1[i2] =0;
					i2++;					
				}	
				i++;
			}
	
			int i3=0;	
			while(Transport.getLast()!=Transport.get(i)){
				state = Integer.parseInt(list.get(s).substring(Transport.get(i)+1,Transport.get(i+1)))+1;	
				epsilon[i3] = state;
				i3++;
				i++;
			}	
			if(Transport.getLast()==Transport.get(i)){
				if(list.get(s).charAt(Transport.getLast()+1) != 'n'){
					state= Integer.parseInt(list.get(s).substring(Transport.getLast()+1,list.get(s).length()))+1;
					epsilon[i3] =state;
				}				
			}	
			input =0;
			Transport.clear();
			for(int j=0; j<size ;j++){
				if(input0[j] == 0){
					content+=s+",0,n,";
				}else{
					content+= s+",0,"+(input0[j]-1)+",";
				}
				
				if(input1[j] ==0){
					content += "n,";
				}else{
					content += (input1[j]-1)+",";
				}
				
				if(epsilon[j] ==0){
					content += "n\n";
				}else{
					content += (epsilon[j]-1)+"\n";
				}
				
			}		
			size=1;								
			s++;						
		}
		System.out.println("state at,final,input=0,input=1,input=e");
		System.out.println(content);
		System.out.println("::::::::::::::::::::::::::::::::::::::");				
	}
	public String toString(){
		return content;
	}
    public void  linkedList(String Re){
    	int n,m;
    	Final.add(0);
    	for(int i=0 ;i <Re.length() ; i++){
    		
    		if(Re.charAt(i) == '0' ){
    			n = Final.getLast();
    			if(Final.size()==1){
    				list.add("s"+1+"_sn_en"); 
    			}else{    					
    				list.add("s"+(n+2)+"_sn_en");  	
    			}
    			list.add("sn_sn_en");    			
    			Final.add(list.size()-1);    			

    		}else if(Re.charAt(i)== '1'){
    			n = Final.getLast();
    			if(Final.size()==1){
    				list.add("sn_s"+1+"_en");    	
    			}else{
    				list.add("sn_s"+(n+2)+"_en");    	
    			}
    			list.add("sn_sn_en");
    			Final.add(list.size()-1);
    			
    		}else if(Re.charAt(i)=='e'){
    			n = Final.getLast();
    			if(Final.size()==1){
    				list.add("sn_sn_e"+1);
    			}else{    			    			
    				list.add("sn_sn_e"+(n+2));
    			}
    			list.add("sn_sn_en");
				Final.add(list.size()-1);    
					
							
			}else if(Re.charAt(i)== '.'){
				n=Final.getLast();
				m =Final.get(Final.size()-2);
				Final.remove(Final.size()-2);
    			String t = list.get(m);
    			for(int j=0; j<t.length();j++){
    				if(t.charAt(j)=='e'){
    					if(t.charAt(j+1)== 'n'){
    						list.set(m,t.substring(0,(j+1)) + (m+1));  // snsnen > snsne5
    					}else{
    						list.set(m,t+"e"+(m+1)); // snsne2 > snsne2e5
    					}    						
    				}    			
    			}    			    			
    				
			}else if(Re.charAt(i)=='?'){
				n= Final.getLast();
    			m = Final.get(Final.size()-2);
    			String t = list.getLast();
    			
    			/*........   S2--(e)-->S3 ................*/
    			for(int j=0; j< list.get(n).length() ;j++){
    				if(t.charAt(j)=='e'){
    					if(t.charAt(j+1)== 'n'){
    					
    						if(Final.size() ==2){
    							list.set(n,list.getLast().substring(0,(j+1)) + (n+1));  // snsnen > snsne5
    						}else{
    							list.set(n,list.getLast().substring(0,(j+1)) + (n+1)); 
    						}
    					
    						
    					}else{
    						if(Final.size() ==2){   						
    							list.set(n,list.getLast()+"e"+(n+1)); // snsne2 > snsne2e5    							
    						}else{
    							list.set(n,list.getLast()+"e"+(n+1)); // snsne2 > snsne2e5
    						}
    					}
    					break;
    				}
    			}
    			/*....  s1<---(e)(x)---->s2--(e)-->s3 .....*/ // create s3
    			list.add("sn_sn_en");
    		
    			/*...   s1--(e)-->s2<---(e)(x)---->s3--(e)-->s4 ...*/ // create s1
    			if(Final.size()==2){
    				list.add(0,"sn_sn_e1");
    			}else{
    				list.add(m+1,"sn_sn_e"+(m+1));
    			}
    			Final.set((Final.size()-1),(list.size()-1));
			
    			/* shift data of list between s2 and s4 */
    			shiftList(m+1);

    			/*.... s1----(e)--->s4 ....*/
    			if(Final.size()==2){    			
    				list.set(m,list.get(m)+"e"+Final.getLast());  
    			}else{
    				list.set(m+1,list.get(m+1)+"e"+Final.getLast());  
    			}
    			
			
			}else if(Re.charAt(i)=='+'){
    			n= Final.getLast();
    			m = Final.get(Final.size()-2);
    			String t = list.getLast();
    			
    			/*........   S2--(e)-->S3 ................*/
    			/*........   S1<--(e)-- S2  ..............*/
    			for(int j=0; j< list.get(n).length() ;j++){
    				if(t.charAt(j)=='e'){
    					if(t.charAt(j+1)== 'n'){
    						
    						if(Final.size() ==2){
    							list.set(n,list.getLast().substring(0,(j+1)) + (n+1)+"e"+(m));  // snsnen > snsne5
    						}else{
    							list.set(n,list.getLast().substring(0,(j+1)) + (n+1)+"e"+(m+1)); 
    						}
    					
    						
    					}else{
    						if(Final.size() ==2){   						
    							list.set(n,list.getLast()+"e"+(n+1)+"e"+(m)); // snsne2 > snsne2e5    							
    						}else{
    							list.set(n,list.getLast()+"e"+(n+1)+"e"+(m+1)); // snsne2 > snsne2e5
    						}
    					}
    					break;
    				}
    			}
    			/*....  s1<---(e)(x)---->s2--(e)-->s3 .....*/ // create s3
    			list.add("sn_sn_en");
    		
    			/*...   s1--(e)-->s2<---(e)(x)---->s3--(e)-->s4 ...*/ // create s1
    			if(Final.size()==2){
    				list.add(0,"sn_sn_e1");
    			}else{
    				list.add(m+1,"sn_sn_e"+(m+1));
    			}
    			Final.set((Final.size()-1),(list.size()-1));
			
    			/* shift data of list between s2 and s4 */
    			shiftList(m+1);

    		
			 
			
    		}else if(Re.charAt(i)=='*'){
    			n= Final.getLast();
    			m = Final.get(Final.size()-2);
    			String t = list.getLast();
    			
    			/*........   S2--(e)-->S3 ................*/
    			/*........   S1<--(e)-- S2  ..............*/
    			for(int j=0; j< list.get(n).length() ;j++){
    				if(t.charAt(j)=='e'){
    					if(t.charAt(j+1)== 'n'){
    						if(Final.size() ==2){
    							list.set(n,list.getLast().substring(0,(j+1)) + (n+1)+"e"+(m));  // snsnen > snsne5
    						}else{
    							list.set(n,list.getLast().substring(0,(j+1)) + (n+1)+"e"+(m+1)); 
    						}
    					
    						
    					}else{
    						if(Final.size() ==2){   						
    							list.set(n,list.getLast()+"e"+(n+1)+"e"+(m)); // snsne2 > snsne2e5    							
    						}else{
    							list.set(n,list.getLast()+"e"+(n+1)+"e"+(m+1)); // snsne2 > snsne2e5
    						}
    					}
    					break;
    				}
    			}
    			/*....  s1<---(e)(x)---->s2--(e)-->s3 .....*/ // create s3
    			list.add("sn_sn_en");
    		
    			/*...   s1--(e)-->s2<---(e)(x)---->s3--(e)-->s4 ...*/ // create s1
    			if(Final.size()==2){
    				list.add(0,"sn_sn_e1");
    			}else{
    				list.add(m+1,"sn_sn_e"+(m+1));
    			}
    			Final.set((Final.size()-1),(list.size()-1));
			
    			/* shift data of list between s2 and s4 */
    			shiftList(m+1);

    			/*.... s1----(e)--->s4 ....*/
    			if(Final.size()==2){    			
    				list.set(m,list.get(m)+"e"+Final.getLast());  
    			}else{
    				list.set(m+1,list.get(m+1)+"e"+Final.getLast());