1.Introduccion
Hola bienvenidos a mi blog, en esta oportunidad vamos a realizar un ejercicio interesante que engloba los temas como: pilas, listas , expresiones regulares, notacion postfija.
El ejercicio consiste en ingresar una expresion regular y que esta me genere posibles palaras. antes de Empezar vamos a definir algunos conceptos:
Expresion Regular:
Es una secuencia de caracteres que forma un patrón de búsqueda, principalmente utilizada para la búsqueda de patrones de cadenas de caracteres u operaciones de sustituciones. Es una forma alternativa a una Gramatica Regular, se usa para representar los lenguajes regulares.
Las expresiones regulares tienen las siguientes Caracteristicas:
- (.) Este simbolo se usa para unir dos simbolos o conjutos de simbolos.
Ejemplo: a.b={ab}
a.b.c={abc}
- (*) Cuando denotamos a un simbolo o conjunto de simbolos con (*),este puede iterar y repetir el simbolo o el conjunto de simbolos, tambien puede generar un vacio en lugar de un simbolo, esta propiedad se llama Clausura.
Ejemplos:
a*={vacio, a, aa, aaa, aaaa, ...}
(a.b)={vacio, ab, abab, ababab}
-(|) Este simbolo se usa como una funcion logica OR, lo que hace es elegir uno o lo otro.
Ejemplo:
a|b={a,b}
Nota: Esta forma de denotar a las expresiones regulares esta basada en la teoria de lenguajes Regulares, no confundir con la notacion de expresiones regulares que se usan en java u otro lenguaje. La finalidad es la misma sino que por cuestiones tecnicas y aplicativas los lenguajes como java, agregaron abreviaciones ejemplo : [a-z1-9] esto es lo mismo que (a|b|c|b|...|x|y|z|1|2|3|...|8|9).
Notacion Postfija:
Esta notacion representa una operacion de la manera primero se escribe el primer operando, luego el segundo y al final la operacion.
Ejemplo
Notacion Infija: a+b
Notacion Postija: ab+
Notacion Infija: (a*b)+c
Notacion Postija: ab*c+
2.Explicacion del Codigo
La estructura del codigo se divide en tres partes fundamentales:
1°.- Se recibe la expresion y se valida si los parentesis u otros simbolos estan ordenados sintacticamente.
Para esto usamos una pila que apilara cuando encuentre un parentesis izquierdo, y desapilara cuando encuentre un parentesis derecho.
2°.- Una vez verificado que la expresion este correctamente ingresada se necesita pasarlo a la notacion Postifija, necesitamos pasarlo a esta notacion porque la notacion postfija nos da un orden de operacion mas fiable, ¿Porque ?, es mas facil para la maquina operar ab*+c pues lee los dos operandos y luego la operacion, en cambio en la notacion infija seria (a*b)+c, para poder operar esa operacion tendriamos que buscar los parentesis, buscar los operandos, y cual operar primero. Ahora para nuestro problema que es en expresiones regulares debemos saber que si leemos un (*) es mas prioritario que leer un (.) o un (|), y se debe considerar prioridades de simbolos en el codigo, para almacenar la notacion postfija usamos una lista enlazada..
3°.- El tercer paso es una vez obtenido la notacion en postfija comenzar operar y generar la palabra, para eso usamos una pila que si lee un caracter del alfabeto lo inserta en la pila y luego si lee un operando lo extrae, ejemplo inserta "a", inserta "b" y luego lee un "." extrae "a" y "b" los une "ab" y lo vuelve a insertar en la pila, y asi sucesivamente hasta terminar de leer la expresion.
Esto es solo para una palabra, de manera que en un buble iteramos el tercer paso "n" veces como queramos generar "n" palabras.
3.Implementacion
4. Pruebas
Espero que les haya sido util, no se olviden de darle like a mi pagina de facebook y suscribirse a mi canal de youtube , mi recomendacion es que mejoren mucho mas el codigo pues para algunas operaciones uso random y heuristicas que ustedes pueden mejorar. Saludos!
SOCIALIZA ESTO →