¿Te gustaría aprender a PHP desde cero?
Tenemos los cursos que necesitas. ¡Haz clic aquí!
Vamos a realizar un ejercicio interesante que engloba los temas como: pilas, listas , expresiones regulares, notación 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+
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 : TecGurus@curso : Practica@Tema : Generador de Palabras a partir de una Expresion Regular@web : www.programaenlinea.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 numerodeterminado de palabras.Como explicacion general:el algoritmo consta de tres partes fundamentales1: verifica que la expresion ingresada este balanceada(que no le falte un parentesis, etc)2: transforma la expresion a notacion postfija3: 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 LISTAchar palabra;struct nodo *sgte;};struct nodo2 { //NODO DE LA PILA PARA LA PALABRA GENERADAstring palabra;struct nodo2 *sgte;};typedef struct nodo *Ptrpila; //creamos puntero tipo pilatypedef struct nodo *Tlista; //creamos puntero tipo listatypedef 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 vaciadestruir(M);balanceoSimbolos(M,cad); //verificamos si los simbolos de agrupacion estan}while(M!=NULL); //correctamente valanceadostam=strlen(cad);/*Este bucle recorre toda la expresion, si es un caracter lo alamcena en una listasi es un operador lo almacena en una pila, pero antes evalua las prioridadesde los operadores luego de acuerdo a eso desapila el operador y lo agrega a la listao 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 operadorespush(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 postfijaimprimir(lista);//llamamos a la funcion generar palabrascout<<"\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 caracterde 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 seencuentran 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 );}}elsepush( p, cad[i] );}i++;}if(p==NULL)cout<<"\n Balanceo CORRECTO..."<<endl<<endl;elsecout<<"\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 cadenaif(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 igualescuando el operador es '*'.Cuando el operador es '|' simplemente genera un numero entre 1 y 1000luego obtiene su modulo con 10, y dependiendo del numero de maneraaleatoria 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 aprender a PHP desde cero?
Tenemos los cursos que necesitas. ¡Haz clic aquí!
