¿Te gustaría Java desde cero?
Tenemos los diplomados que necesitas.¡Haz clic aquí!

Introducción

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+

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.

Implementacion

  1. /*
  2.     @Autor : Joel Fernandez
  3.     @curso : Compiladores
  4.     @Tema  : Generador de Palabras a partir de una Expresion Regular
  5.     @web   : www.codebotic.com
  6. */
  7. #include<iostream>
  8. #include<cstdlib>
  9. #include<stdio.h>
  10. #include<stdlib.h>
  11. #include<string.h>
  12. #include <time.h>
  13. #define max 200
  14.  
  15.  
  16. /*
  17. Este algoritmo lo que hace es recibir una expresion regular y generar un numero
  18. determinado de palabras.
  19.  
  20. Como explicacion general:
  21. el algoritmo consta de tres partes fundamentales
  22. 1: verifica que la expresion ingresada este balanceada(que no le falte un parentesis, etc)
  23. 2: transforma la expresion a notacion postfija
  24. 3: mediante una pila va recorriendo la expresion en postfija y operando segun el operador,
  25. al final lo que queda almacenado en la pila sera la palabra generada.
  26.  
  27. */
  28. using namespace std;
  29.  
  30. struct nodo {     //NODO DE LA PILA Y DE LA LISTA
  31.        char palabra;
  32.        struct nodo *sgte;
  33.        };
  34.  
  35. struct nodo2 {     //NODO DE LA PILA PARA LA PALABRA GENERADA
  36.        string palabra;
  37.        struct nodo2 *sgte;
  38.        };
  39. typedef struct nodo *Ptrpila; //creamos puntero tipo pila
  40. typedef struct nodo *Tlista; //creamos puntero tipo lista
  41. typedef struct nodo2 *Ptrpila2; //creamos puntero tipo pila para evaluacion de postfija
  42.  
  43. /*– Declaramos las funciones a usar—*/
  44. void push(Ptrpila &,char);
  45. char pop(Ptrpila &);
  46. void apilar(Ptrpila2 &,string);
  47. string desapilar(Ptrpila2 &);
  48. void agregar_atras(Tlista &,char);
  49. void destruir(Ptrpila &);
  50. int  prioridad_infija(char );
  51. int  prioridad_pila(char );
  52. void imprimir( Tlista &);
  53. void generar_palabras( Tlista &, int );
  54.  
  55. void balanceoSimbolos( Ptrpila &, char []);
  56.  
  57.  
  58. /*                 Funcion Principal
  59. —————————————————–*/
  60.   int main(void)
  61.     {   Ptrpila p=NULL;
  62.         Ptrpila M=NULL;
  63.         Tlista lista=NULL;
  64.         char cad[max], c,x;
  65.         int tam;
  66.         int n;
  67.         srand(time(NULL));
  68.         system(“color 0b”);
  69.  
  70.         cout<<“GENERADOR DE PALABRAS A PARTIR DE ER \n\n“;
  71.         do{
  72.            cout<<“INGRESE EXPRESION:”;
  73.            gets(cad);
  74.            cout<<” Nro PALABRAS A GENERAR:”;
  75.            cin>>n;
  76.               if(M!=NULL)//condicion para verificar que la pila este vacia
  77.                  destruir(M);
  78.            balanceoSimbolos(M,cad); //verificamos si los simbolos de agrupacion estan
  79.            }while(M!=NULL);         //correctamente valanceados
  80.  
  81.         tam=strlen(cad);
  82.         /*
  83.         Este bucle recorre toda la expresion, si es un caracter lo alamcena en una lista
  84.         si es un operador lo almacena en una pila, pero antes evalua las prioridades
  85.         de los operadores luego de acuerdo a eso desapila el operador y lo agrega a la lista
  86.         o sino apila el operador en la pila
  87.         */
  88.         for(int i=0;i<tam;i++)
  89.         {
  90.             if((cad[i]>=48&&cad[i]<=57)||(cad[i]>=97&&cad[i]<=122)||cad[i]==’+’||cad[i]==’-‘)//validado para numeros de 0-9,letras y ‘+’, ‘-‘
  91.                 agregar_atras(lista,cad[i]);
  92.             if(cad[i]==’.’||cad[i]==’|’||cad[i]=='(‘||cad[i]==’*’)
  93.             {   if(p==NULL)
  94.                     push(p,cad[i]);
  95.                 else
  96.                 {
  97.                     if(prioridad_infija(cad[i])>prioridad_pila(p->palabra))//compara prioridad de operadores
  98.                         push(p,cad[i]);
  99.                     else
  100.                     {   if(prioridad_infija(cad[i])==prioridad_pila(p->palabra))
  101.                           {
  102.                             c=pop(p);
  103.                             agregar_atras(lista,c);
  104.                             push(p,cad[i]);
  105.                           }
  106.                         else
  107.                           {
  108.                             c=pop(p);
  109.                             agregar_atras(lista,c);
  110.                             push(p,cad[i]);
  111.                           }
  112.                     }
  113.                 }
  114.             }
  115.             if(cad[i]==’)’)
  116.                {
  117.                 while(p->palabra!='(‘&&p!=NULL)//desapilamos y agregamos a lista
  118.                    {
  119.                        c=pop(p);
  120.                        agregar_atras(lista,c);
  121.                     }
  122.                 if(p->palabra=='(‘)
  123.                         c=pop(p);
  124.                 }
  125.         }
  126.  
  127.         while(p!=NULL)//si es que la pila aun no esta nula pasamos los operadores a lista
  128.             {
  129.                 c=pop(p);
  130.                 agregar_atras(lista,c);
  131.             }
  132.  
  133.         //llamamos a la funcion imprimir la expresion ya en postfija
  134.         imprimir(lista);
  135.  
  136.         //llamamos a la funcion generar palabras
  137.         cout<<“\n\t PALABRAS GENERADAS\n“;
  138.         generar_palabras(lista,n);
  139.         system(“pause”);
  140.         return 0;
  141.     }
  142.  
  143. /*                 Apilar
  144. ————————————————-*/
  145. void push(Ptrpila &p,char a)
  146. {
  147.     Ptrpila q=new struct nodo;
  148.     q->palabra=a;
  149.     q->sgte=p;
  150.     p=q;
  151.  }
  152.  
  153. /*                 Desapilar
  154. ————————————————-*/
  155. char pop(Ptrpila &p)
  156. {
  157.     int n;
  158.     Ptrpila aux;
  159.  
  160.     n=p->palabra;
  161.     aux=p;
  162.     p=p->sgte;
  163.     delete(aux);
  164.     return n;
  165.  
  166. }
  167. /*                Funcion Apilar para evaluacion de postfija
  168. ————————————————-*/
  169. void apilar(Ptrpila2 &p,string a)
  170. {
  171.     Ptrpila2 q=new struct nodo2;
  172.     q->palabra=a;
  173.     q->sgte=p;
  174.     p=q;
  175.  }
  176.  
  177. /*         Funcion Desapilar para evaluacion de postfija
  178. ————————————————-*/
  179. string desapilar(Ptrpila2 &p)
  180. {
  181.     string n;
  182.     Ptrpila2 aux;
  183.  
  184.     n=p->palabra;
  185.     aux=p;
  186.     p=p->sgte;
  187.     delete(aux);
  188.     return n;
  189.  
  190. }
  191. /*                 Agregar a la Lista
  192. ————————————————–
  193. funcion para agregar caracter a la lista de salida*/
  194. void agregar_atras(Tlista &lista,char a)
  195. {
  196.     Tlista t, q = new(struct nodo);
  197.  
  198.     q->palabra  = a;
  199.     q->sgte = NULL;
  200.  
  201.     if(lista==NULL)
  202.       {
  203.         lista = q;
  204.       }
  205.     else
  206.       {
  207.         t = lista;
  208.         while(t->sgte!=NULL)
  209.         {
  210.             t = t->sgte;
  211.         }
  212.         t->sgte = q;
  213.       }
  214.  
  215. }
  216. /*                 Destruir Pila
  217. ————————————————–*/
  218. void destruir(Ptrpila &M)
  219. {    Ptrpila aux;
  220.  
  221.      if(M !=NULL)
  222.      {
  223.          while(M!=NULL)
  224.          {
  225.              aux=M;
  226.              M=M->sgte;
  227.              delete(aux);
  228.          }
  229.  
  230.       }
  231. }
  232.  
  233. /*          Prioridad en Notacion Infija
  234. —————————————————-
  235. esta prioridad se usa al momento de leer el caracter
  236. de la cadena*/
  237. int prioridad_infija(char a)
  238. {
  239.     if( a=='(‘)
  240.         return 5;
  241.     if( a==’*’)
  242.         return 4;
  243.     if( a==’.’)
  244.         return 2;
  245.     if( a==’|’)
  246.         return 2;
  247.  
  248. }
  249.  
  250. /*                 Prioridad en Pila
  251. —————————————————
  252. esta prioridad es usada para los elementos que se
  253. encuentran en la pila */
  254. int prioridad_pila(char a)
  255. {
  256.     if( a==’*’)
  257.         return 3;
  258.     if( a==’.’)
  259.         return 2;
  260.     if( a==’|’)
  261.         return 2;
  262.     if( a=='(‘)
  263.         return 0;
  264. }
  265. /*               Imprimir Lista
  266. —————————————————-*/
  267. void imprimir( Tlista &lista)
  268. {
  269.     Ptrpila aux;
  270.     aux=lista;
  271.  
  272.     if(lista!=NULL)
  273.      {    cout<<“\n NOTACION POSTFIJA\n\n“;
  274.           while(aux!=NULL)
  275.           {    cout<<aux->palabra;
  276.                aux = aux->sgte;
  277.           }
  278.       }
  279.       cout<<endl<<endl;
  280. }
  281. /*                Balanceo de simbolos de agrupacion
  282. ———————————————————————*/
  283. void balanceoSimbolos( Ptrpila &p, char cad[])
  284. {
  285.      Ptrpila aux;
  286.      int i = 0;
  287.  
  288.      while( cad[i] != ‘\0‘)
  289.      {
  290.             if( cad[i]=='(‘ || cad[i]=='[‘ || cad[i]=='{‘ )
  291.             {
  292.                  push( p, cad[i] );
  293.             }
  294.             else if( cad[i]==’)’ || cad[i]==’]’ || cad[i]==’}’ )
  295.             {
  296.                  aux = p;
  297.  
  298.                  if(aux!=NULL)
  299.                  {
  300.                       if( cad[i]==’)’ )
  301.                       {
  302.                            if( aux->palabra == ‘(‘)
  303.                               pop( p );
  304.                       }
  305.                       else if( cad[i]==’]’ )
  306.                       {
  307.                            if( aux->palabra == ‘[‘)
  308.                               pop( p );
  309.                       }
  310.                       else if( cad[i]==’}’ )
  311.                       {
  312.                            if( aux->palabra == ‘{‘)
  313.                               pop( p );
  314.                       }
  315.                  }
  316.                  else
  317.                      push( p, cad[i] );
  318.             }
  319.             i++;
  320.      }
  321.  
  322.      if(p==NULL)
  323.          cout<<“\n Balanceo CORRECTO…”<<endl<<endl;
  324.      else
  325.          cout<<“\n Balanceo INCORRECTO, faltan simbolos de agrupacion…”<<endl;
  326.  
  327.  
  328. }
  329.  
  330. /*               Generar Palabras
  331. —————————————————-*/
  332. void generar_palabras( Tlista &lista, int n )
  333. {
  334.     char L[max];
  335.     string op1, op2;
  336.     string Z;
  337.     string temp;
  338.     int x=1;
  339.     int i=0;
  340.     int random;
  341.  
  342.     Ptrpila aux;
  343.     Ptrpila2 m=NULL;
  344.  
  345.     aux=lista;
  346.     L[0]=’\0‘;
  347.     Z=””;
  348.     // este if transforma la lista en una cadena
  349.     if(lista!=NULL)
  350.      {
  351.           while(aux!=NULL)
  352.           {     int s=strlen(L);
  353.                 L[s]=aux->palabra;
  354.                 L[s+1]=’\0‘;
  355.                 aux = aux->sgte;
  356.           }
  357.       }
  358.  
  359.     /*
  360.     Este bucle genera palabras usando un random de 1 a 10 caracteres iguales
  361.     cuando el operador es ‘*’.
  362.     Cuando el operador es ‘|’ simplemente genera un numero entre 1 y 1000
  363.     luego obtiene su modulo con 10, y dependiendo del numero de manera
  364.     aleatoria elige uno o el otro.
  365.     */
  366.     for(int j=0;j<n;j++)// for que mostrara la cantidad de palabras a generar
  367.     {   m=NULL;
  368.         Z=””;
  369.  
  370.         for(int i=0;i<strlen(L);i++)//recorremos toda la cadena
  371.         {
  372.             if((L[i]>=48&&L[i]<=57)||(L[i]>=97&&L[i]<=122)||L[i]==’+’||L[i]==’-‘)
  373.             {
  374.                 temp=L[i];
  375.                 apilar(m,temp);
  376.  
  377.             }else if(L[i]==’*’)
  378.             {
  379.                 random=1+rand()%(11-1);
  380.                 op1=desapilar(m);
  381.                 Z=””;
  382.                 for(int k=0;k<random;k++)
  383.                 {   if(j==0)
  384.                     {
  385.                         Z=””;
  386.                     }else
  387.                     {
  388.                         Z=Z+op1;
  389.                     }
  390.  
  391.                 }
  392.                 apilar(m,Z);
  393.  
  394.             }else if(L[i]==’.’)
  395.             {
  396.                 op1=desapilar(m);
  397.                 op2=desapilar(m);
  398.                 Z=op2+op1;
  399.                 apilar(m,Z);
  400.             }else if(L[i]==’|’)
  401.             {
  402.                 random=1+rand()%(1001-1);
  403.                 op1=desapilar(m);
  404.                 op2=desapilar(m);
  405.                 if(random%10==1||random%10==5||random%10==9||random%10==6||random%10==3)
  406.                 {
  407.                     Z=op1;
  408.                 }else
  409.                 {
  410.                     Z=op2;
  411.                 }
  412.                 apilar(m,Z);
  413.             }
  414.         }
  415.         Z=desapilar(m);
  416.         cout<<Z<<endl;
  417.  
  418.     }
  419.  
  420. }

4. Pruebas

Te esperamos en los siguientes artículos en donde hablaremos mas acerca de estos temas, los cuales hoy en día son de vital importancia en el mundo de la tecnología.

¿Te gustaría Java desde cero?
Tenemos los diplomados que necesitas.¡Haz clic aquí!

About Author

NGuerrero

0 0 votos
Article Rating
Suscribir
Notificar de
0 Comments
Comentarios.
Ver todos los comentarios
0
¿Te gusta este articulo? por favor comentax
()
x
Abrir chat
¿Quieres aprender a programar?
Hola 👋,
¿Te interesa información de nuestros cursos?