¿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
- /*
- @Autor : Joel Fernandez
- @curso : Compiladores
- @Tema : Generador de Palabras a partir de una Expresion Regular
- @web : www.codebotic.com
- */
- #include<iostream>
- #include<cstdlib>
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #include <time.h>
- #define max 200
- /*
- Este algoritmo lo que hace es recibir una expresion regular y generar un numero
- determinado de palabras.
- Como explicacion general:
- el algoritmo consta de tres partes fundamentales
- 1: verifica que la expresion ingresada este balanceada(que no le falte un parentesis, etc)
- 2: transforma la expresion a notacion postfija
- 3: mediante una pila va recorriendo la expresion en postfija y operando segun el operador,
- al final lo que queda almacenado en la pila sera la palabra generada.
- */
- using namespace std;
- struct nodo { //NODO DE LA PILA Y DE LA LISTA
- char palabra;
- struct nodo *sgte;
- };
- struct nodo2 { //NODO DE LA PILA PARA LA PALABRA GENERADA
- string palabra;
- struct nodo2 *sgte;
- };
- typedef struct nodo *Ptrpila; //creamos puntero tipo pila
- typedef struct nodo *Tlista; //creamos puntero tipo lista
- typedef struct nodo2 *Ptrpila2; //creamos puntero tipo pila para evaluacion de postfija
- /*– Declaramos las funciones a usar—*/
- void push(Ptrpila &,char);
- char pop(Ptrpila &);
- void apilar(Ptrpila2 &,string);
- string desapilar(Ptrpila2 &);
- void agregar_atras(Tlista &,char);
- void destruir(Ptrpila &);
- int prioridad_infija(char );
- int prioridad_pila(char );
- void imprimir( Tlista &);
- void generar_palabras( Tlista &, int );
- void balanceoSimbolos( Ptrpila &, char []);
- /* Funcion Principal
- —————————————————–*/
- int main(void)
- { Ptrpila p=NULL;
- Ptrpila M=NULL;
- Tlista lista=NULL;
- char cad[max], c,x;
- int tam;
- int n;
- srand(time(NULL));
- system(«color 0b»);
- cout<<«GENERADOR DE PALABRAS A PARTIR DE ER \n\n«;
- do{
- cout<<«INGRESE EXPRESION:»;
- gets(cad);
- cout<<» Nro PALABRAS A GENERAR:»;
- cin>>n;
- if(M!=NULL)//condicion para verificar que la pila este vacia
- destruir(M);
- balanceoSimbolos(M,cad); //verificamos si los simbolos de agrupacion estan
- }while(M!=NULL); //correctamente valanceados
- tam=strlen(cad);
- /*
- Este bucle recorre toda la expresion, si es un caracter lo alamcena en una lista
- si es un operador lo almacena en una pila, pero antes evalua las prioridades
- de los operadores luego de acuerdo a eso desapila el operador y lo agrega a la lista
- o sino apila el operador en la pila
- */
- for(int i=0;i<tam;i++)
- {
- 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 ‘+’, ‘-‘
- agregar_atras(lista,cad[i]);
- if(cad[i]==’.’||cad[i]==’|’||cad[i]=='(‘||cad[i]==’*’)
- { if(p==NULL)
- push(p,cad[i]);
- else
- {
- if(prioridad_infija(cad[i])>prioridad_pila(p->palabra))//compara prioridad de operadores
- push(p,cad[i]);
- else
- { if(prioridad_infija(cad[i])==prioridad_pila(p->palabra))
- {
- c=pop(p);
- agregar_atras(lista,c);
- push(p,cad[i]);
- }
- else
- {
- c=pop(p);
- agregar_atras(lista,c);
- push(p,cad[i]);
- }
- }
- }
- }
- if(cad[i]==’)’)
- {
- while(p->palabra!='(‘&&p!=NULL)//desapilamos y agregamos a lista
- {
- c=pop(p);
- agregar_atras(lista,c);
- }
- if(p->palabra=='(‘)
- c=pop(p);
- }
- }
- while(p!=NULL)//si es que la pila aun no esta nula pasamos los operadores a lista
- {
- c=pop(p);
- agregar_atras(lista,c);
- }
- //llamamos a la funcion imprimir la expresion ya en postfija
- imprimir(lista);
- //llamamos a la funcion generar palabras
- cout<<«\n\t PALABRAS GENERADAS\n«;
- generar_palabras(lista,n);
- system(«pause»);
- return 0;
- }
- /* Apilar
- ————————————————-*/
- void push(Ptrpila &p,char a)
- {
- Ptrpila q=new struct nodo;
- q->palabra=a;
- q->sgte=p;
- p=q;
- }
- /* Desapilar
- ————————————————-*/
- char pop(Ptrpila &p)
- {
- int n;
- Ptrpila aux;
- n=p->palabra;
- aux=p;
- p=p->sgte;
- delete(aux);
- return n;
- }
- /* Funcion Apilar para evaluacion de postfija
- ————————————————-*/
- void apilar(Ptrpila2 &p,string a)
- {
- Ptrpila2 q=new struct nodo2;
- q->palabra=a;
- q->sgte=p;
- p=q;
- }
- /* Funcion Desapilar para evaluacion de postfija
- ————————————————-*/
- string desapilar(Ptrpila2 &p)
- {
- string n;
- Ptrpila2 aux;
- n=p->palabra;
- aux=p;
- p=p->sgte;
- delete(aux);
- return n;
- }
- /* Agregar a la Lista
- ————————————————–
- funcion para agregar caracter a la lista de salida*/
- void agregar_atras(Tlista &lista,char a)
- {
- Tlista t, q = new(struct nodo);
- q->palabra = a;
- q->sgte = NULL;
- if(lista==NULL)
- {
- lista = q;
- }
- else
- {
- t = lista;
- while(t->sgte!=NULL)
- {
- t = t->sgte;
- }
- t->sgte = q;
- }
- }
- /* Destruir Pila
- ————————————————–*/
- void destruir(Ptrpila &M)
- { Ptrpila aux;
- if(M !=NULL)
- {
- while(M!=NULL)
- {
- aux=M;
- M=M->sgte;
- delete(aux);
- }
- }
- }
- /* Prioridad en Notacion Infija
- —————————————————-
- esta prioridad se usa al momento de leer el caracter
- de la cadena*/
- int prioridad_infija(char a)
- {
- if( a=='(‘)
- return 5;
- if( a==’*’)
- return 4;
- if( a==’.’)
- return 2;
- if( a==’|’)
- return 2;
- }
- /* Prioridad en Pila
- —————————————————
- esta prioridad es usada para los elementos que se
- encuentran en la pila */
- int prioridad_pila(char a)
- {
- if( a==’*’)
- return 3;
- if( a==’.’)
- return 2;
- if( a==’|’)
- return 2;
- if( a=='(‘)
- return 0;
- }
- /* Imprimir Lista
- —————————————————-*/
- void imprimir( Tlista &lista)
- {
- Ptrpila aux;
- aux=lista;
- if(lista!=NULL)
- { cout<<«\n NOTACION POSTFIJA\n\n«;
- while(aux!=NULL)
- { cout<<aux->palabra;
- aux = aux->sgte;
- }
- }
- cout<<endl<<endl;
- }
- /* Balanceo de simbolos de agrupacion
- ———————————————————————*/
- void balanceoSimbolos( Ptrpila &p, char cad[])
- {
- Ptrpila aux;
- int i = 0;
- while( cad[i] != ‘\0‘)
- {
- if( cad[i]=='(‘ || cad[i]=='[‘ || cad[i]=='{‘ )
- {
- push( p, cad[i] );
- }
- else if( cad[i]==’)’ || cad[i]==’]’ || cad[i]==’}’ )
- {
- aux = p;
- if(aux!=NULL)
- {
- if( cad[i]==’)’ )
- {
- if( aux->palabra == ‘(‘)
- pop( p );
- }
- else if( cad[i]==’]’ )
- {
- if( aux->palabra == ‘[‘)
- pop( p );
- }
- else if( cad[i]==’}’ )
- {
- if( aux->palabra == ‘{‘)
- pop( p );
- }
- }
- else
- push( p, cad[i] );
- }
- i++;
- }
- if(p==NULL)
- cout<<«\n Balanceo CORRECTO…»<<endl<<endl;
- else
- cout<<«\n Balanceo INCORRECTO, faltan simbolos de agrupacion…»<<endl;
- }
- /* Generar Palabras
- —————————————————-*/
- void generar_palabras( Tlista &lista, int n )
- {
- char L[max];
- string op1, op2;
- string Z;
- string temp;
- int x=1;
- int i=0;
- int random;
- Ptrpila aux;
- Ptrpila2 m=NULL;
- aux=lista;
- L[0]=’\0‘;
- Z=»»;
- // este if transforma la lista en una cadena
- if(lista!=NULL)
- {
- while(aux!=NULL)
- { int s=strlen(L);
- L[s]=aux->palabra;
- L[s+1]=’\0‘;
- aux = aux->sgte;
- }
- }
- /*
- Este bucle genera palabras usando un random de 1 a 10 caracteres iguales
- cuando el operador es ‘*’.
- Cuando el operador es ‘|’ simplemente genera un numero entre 1 y 1000
- luego obtiene su modulo con 10, y dependiendo del numero de manera
- aleatoria elige uno o el otro.
- */
- for(int j=0;j<n;j++)// for que mostrara la cantidad de palabras a generar
- { m=NULL;
- Z=»»;
- for(int i=0;i<strlen(L);i++)//recorremos toda la cadena
- {
- if((L[i]>=48&&L[i]<=57)||(L[i]>=97&&L[i]<=122)||L[i]==’+’||L[i]==’-‘)
- {
- temp=L[i];
- apilar(m,temp);
- }else if(L[i]==’*’)
- {
- random=1+rand()%(11-1);
- op1=desapilar(m);
- Z=»»;
- for(int k=0;k<random;k++)
- { if(j==0)
- {
- Z=»»;
- }else
- {
- Z=Z+op1;
- }
- }
- apilar(m,Z);
- }else if(L[i]==’.’)
- {
- op1=desapilar(m);
- op2=desapilar(m);
- Z=op2+op1;
- apilar(m,Z);
- }else if(L[i]==’|’)
- {
- random=1+rand()%(1001-1);
- op1=desapilar(m);
- op2=desapilar(m);
- if(random%10==1||random%10==5||random%10==9||random%10==6||random%10==3)
- {
- Z=op1;
- }else
- {
- Z=op2;
- }
- apilar(m,Z);
- }
- }
- Z=desapilar(m);
- cout<<Z<<endl;
- }
- }
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í!
