Les comparto un código que hice en java.
Recibe como argumento al crear la clase una cadena como la siguiente como expresión: aba
El resultado es una serie de string almacenados en una lista con el siguiente formato, la primer linea pone los terminales que componen el alfabeto en este caso e (vacio), a y b.
Las demas lineas se componen por:
0-_&1&_
1-_&_&2
2-_&3&_
*3-_&_&_
Por ejemplo en la primer linea, el primer numero significa el numero de nodo, si tiene un asterisco se toma como un nodo de aceptación. El guion separa el numero de nodos de las transiciones y van en el orden del alfabeto es decir el primero le corresponde a e(vacío) por lo que como en este caso no existen en el automata pues ponemos _, despues le sigue un & que significa que es el siguiente no terminal por lo tanto si es el primero viene un 1, porque quiere decir que con "a" se va al nodo 1, el ultimo & da vacío porque en el primer estado no avanza con b.
El proyecto esta basado en el algoritmo de thompson
El proyecto esta conformado por:
CobyException: Es una clase simbólica que yo programe para arrojar una serie de códigos como nuestra aplicación es solo un backend que trabajara por detrás no tiene interfaz grafica por lo que decidimos mandar los mensajes de validación a través de CobyException.
Codigo:
package common;
/**
*
* @author cobymotion
*/
public class CobyException extends RuntimeException{
/**
* Codigos de error
* Cod01: Es posible que la transicion se haya perdido revisar algoritmo
* Cod02: Los operadores no pueden ir al principio y el operador + no puede ir al final
* Cod03: En esta version no funcionan los parentesis
* Cod 04: Los parentesis tienen un orden incorrecto
* Cod05: Dos cerraduras de kleene juntas
* Cod06: Dos operadores en un mal orden
* @param codigo
*/
public CobyException(String codigo) {
super(codigo);
}
}
Points: Es un archivo plano de java que solo tiene como fundamental almacenar los puntos de inserción de las tablas, ya que en la primera versión no aceptaba paréntesis tuvimos que agregar dicha clase para almacenar puntos en los que se adaptarían las tablas.
Codigo:
package common;
/**
* Esta clase me permite almacenar los pares donde se enlazaran las tablas,
* solo me sirve como modelo
* @author cobymotion
*/
public class Points {
int init;
int end;
public Points() {
}
public Points(int init) {
this.init = init;
}
}
TableTransition: Otra nueva clase que tenia como objetivo almacenar tablas de los contenidos de los paréntesis, es decir solo almacena resultados de lo que los paréntesis arrojan, en una expresión normal hay una tabla que por cada paréntesis lo sustituirá por letras Mayúsculas por lo que eso quiere decir que esa No terminal será sustituida por otra tabla
Codigo:
package common;
import java.util.List;
/**
* Clase modelo que solo permite almacenar las tablas que se van opteniendo del interno de los parentesis
* @author cobymotion
*/
public class TableTransition {
private List table;
private int num;
public List getTable() {
return table;
}
public void setTable(List table) {
this.table = table;
}
public int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
}
ConvertToAFN: Siguiendo ayuda del algoritmo de Thompson que es una forma de convertir una expresión regular a un afd con e transición.
Codigo:
package common;
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
/**
*Clase que permite cambiar una expresion regular a un conjunto de lineas de texto
* que representan una tabla de transicion de un automata-e
* @author cobymotion
*/
public class ConvertToAFN {
private String exp;
/**
* Constructor, permite solo instanciar la clase mandandole una expresion
* Debe de cumplir con la forma correcta tomando en cuenta el cierre de
* parentesis
*
* @param exp cadena con la expresion regular
*/
public ConvertToAFN(String exp) {
this.exp = exp;
}
/**
* Obtiene el valor de la expresion que se esta evaluando
* @return la expresion
*/
public String getExp() {
return exp;
}
/**
* Permite modificar el valor de la expresion que sera evaluada en el programa
* @param exp Nueva expresion por la que sera cambiada
*/
public void setExp(String exp) {
this.exp = exp;
}
/**
* Busca que la cadena no tenga ninguna mayuscula al dar de alta la cadena
*
* @return retorna verdadero si la encuentra
*/
private boolean encuentraMayusculas() {
boolean res = false;
for (int i = 0; i < exp.length(); i++) {
if (Character.isUpperCase(exp.charAt(i))) {
res = true;
}
}
return res;
}
/**
* Metodo que regresa una serie de lineas de texto con el formato que tendra
* logico el automata, esta clase solo saca tokens de los parentesis para
* que sean convertidos, una vez que se convierten se concatena con lo ya
* obtenido por la expresiòn
*
* @return lista, la primer linea esta compuesta por el alfabeto de la
* expresión las demas lineas siguen el formato que la maestra sigue para
* representacion de los algoritmos si regresa un null quiere decir que no
* hay expresion a evaluar
*/
public List toAFDe() {
List AFDe = new ArrayList<>();
List listTable = new ArrayList<>();
if (encuentraMayusculas()) {
throw new CobyException("Cod 08: Esta version de software no acepta mayusculas ya que tienen una función en el sistema");
}
if (faltaParentesis()) {
throw new CobyException("Cod 07: Hay algun problema con los parenteris");
} else if (!exp.contains("(")) {
AFDe = toAFDInterno(exp);
} else {
List regInitial = toAFDInterno(getTables(exp, "", listTable, 0));
//System.out.println(mergeADF(exp,"",listTable,0,0));
TableTransition tableNew = new TableTransition();
tableNew.setNum(listTable.size());
tableNew.setTable(regInitial);
listTable.add(tableNew);
///solo para probar que funciona
AFDe = mergeTables(listTable);
/* for (TableTransition tableTransition : listTable) {
System.out.println("----------- " + tableTransition.getNum() + "---------");
for (String cadena : tableTransition.getTable()) {
System.out.println(cadena);
}
}*/
}
return AFDe;
}
/**
* Esta clase permite a cada bloque de parenteris convertirlo en una tabla
* independiente
*
* @param exp La cadena con la expresion completa
* @param nueva Es una cadena auxiliar que permite ir manejando los tokens
* de la expresion
* @param listTable Lista con las tablas que se fueron formando
* @param i contador de caracteres
* @return la expresion resultante despues de haber trabajado los parentesis
*/
private String getTables(String exp, String nueva, List listTable, int i) {
while (exp.length() > i && exp.charAt(i) != ')') {
char car = exp.charAt(i);
if (car == '(') {
String nueva2 = getTables(exp, "", listTable, ++i);
while (exp.length() > i && exp.charAt(i) != ')') {
i++;
}
nueva += String.valueOf((char) ('A' + listTable.size()));
TableTransition tableNew = new TableTransition();
tableNew.setNum(listTable.size());
tableNew.setTable(toAFDInterno(nueva2));
listTable.add(tableNew);
} else {
nueva += car;
i++;
}
}
return nueva;
}
/**
* Junta las tablas en la ultima que fue almacenada en la lista
* @param lista es un conjunto de tablas.
* @return
*/
private List mergeTables(List lista) {
List complete = lista.get(lista.size() - 1).getTable();
///
boolean mayus = false;
do {
mayus=false;
String alphabet = complete.get(0);
for (int i = 0; i < alphabet.length(); i++) {
if (Character.isUpperCase(alphabet.charAt(i))) {
//hay un cambio
//obtener el registro que vamos a combianar
mayus=true;
int nodo = (int) (alphabet.charAt(i) - 'A');
List tabla = lista.get(nodo).getTable(); //tabla que voy a unir a la otra
List nuevos = encuentraNodos(complete, i); //puntos donde unire
List finales = nodosFinales(tabla);
deleteColum(complete, i);
for (Points points : nuevos) {
int suma = complete.size() - 1;
linkTables(points, suma, complete, tabla,finales);
}
}
}
} while (mayus);
///
return complete;
}
/**
* Enlaza las dos tablas para que puedan ser una sola, destino queda como resultdo de la union
* @param point puntos donde se unira la tabla
* @param suma valor de desface en los estados en la tabla nueva
* @param destino lista con la tabla terminada
* @param toJoin tabla que se va a unir
* @param finales nodos que son de terminacion en la tabla que se unira
*/
public void linkTables(Points point, int suma, List destino, List toJoin, Listfinales) {
String alphabet = destino.get(0);
String cambio = destino.get(point.init + 1);
//mando el nodo inicial con e transicion a un nodo nuevo
String partes[] = cambio.split("-");
String tokens[] = partes[1].split("&");
if (tokens[0].equals("_")) {
tokens[0] = String.valueOf(suma);
} else {
tokens[0] += ",";
tokens[0] += String.valueOf(suma);
}
cambio = partes[0];
cambio += "-";
boolean ban=false;
for (int j = 0; j < tokens.length; j++) {
cambio += tokens[j];
cambio += "&";
ban=true;
}
if(ban)
cambio = cambio.substring(0, indexOfApersonFinal(cambio));
destino.set(point.init+1,cambio);
/// recorrer la tabla e irla uniendo
String alphabetExterno = toJoin.get(0);
//merge alfabeto
alphabet = mergeAlphabets(alphabet,alphabetExterno,destino);
destino.set(0, alphabet);
//
for(int i=1;i transiciones = new HashMap<>();
for (int j = 0; j < tokens.length; j++) {
String string = tokens[j];
if(!string.equals("_"))
{
//agrega nodo a la tabla destino
String valores[] = string.split(",");
string = "";
for (String string1 : valores) {
int destinoNum = Integer.parseInt(string1) + suma;
string +=String.valueOf(destinoNum);
string +=",";
}
tokens[j] = string.substring(0, string.length()-1);
transiciones.put(alphabetExterno.charAt(j),tokens[j]);
}
}
//crea una cadena para agregar a destino
String cadena = "";
cadena += (destino.size()-1);
cadena += "-";
for(int j=0;j destino, int pos, Points point){
String cadena = destino.get(pos);
String partes[] = cadena.split("-");
String tokens[] = partes[1].split("&");
if (tokens[0].equals("_")) {
tokens[0] = String.valueOf(point.end);
} else {
tokens[0] += ",";
tokens[0] += String.valueOf(point.end);
}
String cambio = partes[0];
cambio += "-";
boolean ban=false;
for (int j = 0; j < tokens.length; j++) {
cambio += tokens[j];
cambio += "&";
ban=true;
}
if(ban)
cambio = cambio.substring(0, indexOfApersonFinal(cambio));
destino.set(pos,cambio);
}
/**
* Sirve para poder agregar una columna en caso que haya elementos que no esten en el alfabeto
* @param destino La serie de cadenas ya con el formato
*/
private void agregarcolumna(List destino){
for(int i=1;i nodosFinales(List complete){
List finales = new ArrayList<>();
for(int i=1;i complete, int colum) {
//empezar a settear todas las cadenas
String alphabet = complete.get(0);
alphabet = alphabet.replace(String.valueOf(alphabet.charAt(colum)), "");
complete.set(0, alphabet);
for (int i = 1; i < complete.size(); i++) {
String cadena = complete.get(i);
String partes[] = cadena.split("-");
String tokens[] = partes[1].split("&");
cadena = partes[0].toString();
cadena += "-";
for (int j = 0; j < tokens.length; j++) {
if (j != colum) {
cadena += tokens[j];
cadena += "&";
}
}
cadena = cadena.substring(0, indexOfApersonFinal(cadena));
complete.set(i, cadena);
}
}
/**
* Obtiene la posicion donde esta el ultimo aperson para eliminar la columna
* @param cadena la cadena de la entrada
* @return retorna la posicion
*/
private int indexOfApersonFinal(String cadena) {
for (int i = cadena.length() - 1; i >= 0; i--) {
if (cadena.charAt(i) == '&') {
return i;
}
}
return 0;
}
/**
* Encuentra todos los nodos que tengan una relacion con otra tabla
*
* @param cambios Es lista que tiene el automata como va quedando
* @param nodo numero de columna donde encontro una relacion con otra tabla
* @return returna la lista ya modificada
*/
private List encuentraNodos(List cambios, int nodo) {
List nuevos = new ArrayList<>();
Iterator ite = cambios.iterator();
//nodo++;
ite.next();
while (ite.hasNext()) {
String tokens[] = ite.next().toString().split("&");
if (!tokens[nodo].equals("_")) {
Points punto = new Points();
punto.end = Integer.parseInt(tokens[nodo]);
int num = obtenerNumero(tokens[0]);
punto.init = num;
nuevos.add(punto);
}
}
return nuevos;
}
/**
* Este metodo se utiliza para extraer el numero de nodo donde se unira la
* tabla
*
* @param cad cadena que se buscara digitos para convertirlos en numero, no
* considera que puden estar separados
* @return returna un entero con el numero que se obtuvo
*/
private int obtenerNumero(String cad) {
String subcadena = "";
for (int i = 0; i < cad.length(); i++) {
if (Character.isDigit(cad.charAt(i))) {
subcadena += cad.charAt(i);
}
}
int numero = 0;
try {
numero = Integer.parseInt(subcadena);
} catch (NumberFormatException e) {
numero = -1;
}
return numero;
}
/**
* El metodo que permite convertir pequeñas expresiones en el formato de
* AFDe
*
* @param exp se lleva la expresion que esta dentro de un parentesis y la
* expresion completa sin parentesis
* @return
* @throws CobyException
*/
private List toAFDInterno(String exp) throws CobyException {
//algunas validaciones
if (exp.charAt(0) == '*' || exp.charAt(0) == '+' || exp.charAt(exp.length() - 1) == '+') {
throw new CobyException("Cod02: Los operadores no pueden ir al principio y el operador + no puede ir al final");
} else if (exp.contains("(") || exp.contains(")")) {
throw new CobyException("Cod03: Se escapo un parentesis en un token");
} else if (exp.contains("**")) {
throw new CobyException("Cod05: Dos cerraduras de kleene juntas");
} else if (exp.contains("+*")) {
throw new CobyException("Cod06: Dos operadores en un mal orden");
}
//usa ya por definicion la expresion regular que viene especificada en la ca
//primero declaramos las variables que se necesitaran
String[][] table = new String[100][100]; //tabla de transciciones
//contadores
int col, row, contnodos, trans, inicial;
int ban = 0;
col = row = 0;
//agregamos al alfabeto la e
table[0][1] = "e";
//agregamos el nodo inicial
table[1][0] = "0";
//actualizamos la posicion donde empezaran
row = 2;
trans = 1;
inicial = 1;
contnodos = 0;
//recorremos la expresión de caracter en caracter
for (int i = 0; i < exp.length(); i++) {
//capturamos el caracter a evaluar
char car = exp.charAt(i);
//hacemos comparaciones de los posibles operadores +,*,(,)
if (car == '+') {
trans = inicial;
table[row - 1][0] = "*" + table[row - 1][0];
ban = 0;
} else if (car == '*') {
//cuando es un solo bloque el que sigue entonces regresar la expresion
if (ban == 1) {
String auxExp = exp.substring(0, i);
// auxExp = auxExp;
auxExp += "e";
auxExp += String.valueOf(exp.charAt(i - 1));
auxExp += "*";
exp = auxExp + exp.substring(i + 1);
table[1][0] = "*" + table[1][0];
i--;
} else {
// como la transicion que se maneja es de izquierda a derecha se regresa el control al nodo anterior
row--;
trans = row;
int pos = backNode(table[row - 1], table[0], contnodos--, exp.charAt(i - 1)); //aqui tengo un Errorvuelvo despues
if (pos == -1) {
throw new CobyException("Cod01: Es posible que la transicion se haya perdido revisar algoritmo");
}
table[row - 1][pos] = String.valueOf(contnodos);
String auxExp = exp.substring(0, i);
// auxExp = auxExp;
auxExp += "e";
exp = auxExp + exp.substring(i + 1);
i--;
trans--;
}
} else { // si no es un operador entonces consideramos que es un elemento del alfabeto
int posCol = updateAlfabeto(table[0], car);
contnodos++;
if (table[trans][posCol] != null) {
table[trans][posCol] += ",";
table[trans][posCol] += String.valueOf(contnodos);
} else {
table[trans][posCol] = String.valueOf(contnodos);
}
table[row][0] = String.valueOf(contnodos);
trans = row;
row++;
ban++;
}
}
//actualiza el ultimo nodo para que se haga de aceptacion
table[row - 1][0] = "*" + table[row - 1][0];
/* for (int i = 0; i < 10; i++) {
System.out.println(Arrays.toString(table[i]));
}*/
List formatoDiaz = toConvertFormatDiaz(table, row);
return formatoDiaz;
}
/**
* Esta funcion se encarga de agarrar una matriz en array convertirlo a un formato
* visto en clases por la Maestra Miriam Diaz
* @param table matriz con las transiciones
* @param row numero de lineas que tiene la matriz
* @return Retorna una lista con cadenas que representan la tabla segun el formato
*/
public List toConvertFormatDiaz(String[][] table, int row) {
List formato = new ArrayList<>();
int i = 1;
String alphabet = "";
while (table[0][i] != null) {
alphabet += table[0][i];
i++;
}
formato.add(alphabet);
String linea = "";
for (int j = 1; j < row; j++) {
linea = "";
for (int k = 0; k < i; k++) {
if (table[j][k] != null) {
linea += table[j][k];
} else {
linea += "_";
}
if (k == 0) {
linea += "-";
} else {
linea += "&";
}
}
formato.add(linea.substring(0, linea.length() - 1));
}
return formato;
}
/**
* Permite verificar que los parentesis tengan la misma cantidad entre los
* que abren y cierran Puede ser que esta funcion no salga porque no tenemos
* un orden adecuado de los parentesis
*
* @return un verdadero si faltan parametros
*/
private boolean faltaParentesis() {
Stack pila = new Stack<>();
for (int i = 0; i < exp.length(); i++) {
if (exp.charAt(i) == '(') {
pila.push(1);
} else if (exp.charAt(i) == ')') {
try {
pila.pop();
} catch (EmptyStackException e) {
throw new CobyException("Cod 04: Los parentesis tienen un orden incorrecto");
}
}
}
if (pila.empty()) {
return false;
} else {
return true;
}
}
/**
*
* @param rowData la linea que tiene el valor que se va a modificar
* @param rowAlphabet manda la primer linea donde esta el alfabeto
* @param contNodos el numero de nodo que cambiara por si mismo para formar
* ciclo
* @param car el caracter del estado que se hizo una transcicion anterior
* para buscar la posición
* @return posicion donde esta el parametro que vamos a cambiar, regresa
* menos -1 si no funciona
*/
private int backNode(String[] rowData, String[] rowAlphabet, int node, char car) {
int pos = -1;
try {
pos = updateAlfabeto(rowAlphabet, car);
} catch (Exception e) {
pos = -1;
}
return pos;
}
/**
* Este metodo se encarga verificar si ya existe un elemento en el alfabeto
* en la primera linea de la tabla si no existe entonoces lo agrega
*
* @param rowAlfabeth lleva solo la primera linea del arreglo
* @param car el caracter que se agrega en el alfabeto
* @return Regresa la posicion donde se encuentra el caracter en el alfabeto
*/
private int updateAlfabeto(String rowAlphabet[], Character car) {
int pos = 1;
while (rowAlphabet[pos] != null) {
if (rowAlphabet[pos].equals(car.toString())) {
return pos;
}
pos++;
}
rowAlphabet[pos] = car.toString();
return pos;
}
/**
* Solo me extrae las transiciones
* @param cambio
* @return retorna un arreglo con las transiciones
*/
private String[] internos(String cambio) {
String partes[] = cambio.split("-");
String tokens[] = partes[1].split("&");
return tokens;
}
/**
* Combina mediante cadenas los alfabetos para que son repetidos
* @param oAlphabet Alfabeto de origen
* @param dAlphabet alfabeto que se unira
* @param destino lista de la tabla
* @return cadena ya con el alfabeto combinado
*/
private String mergeAlphabets(String oAlphabet, String dAlphabet, List destino) {
for(int i=0;i resultado = oConvert.toAFDe();
for (String string : resultado) {
System.out.println(string);
}
}
}
Espero les sirva
