GeneradorExpresionRegular

/*
    @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;

    }

}