Automata de Pila

   

Iníciales        
 E  ->  (, i

T  ->   (, i

F  ->   (, i

E'  ->  +, #

T'  ->  *, #                                                 

Seguidores

E -> $,)

T -> +, $,)

F -> *,+, $,)

E' -> $,)

T'-> +, $,)

Codigo

// **** Automata2.cpp **** \\



#include
#include "Pila.h"


using namespace std;


#define E1    -1
#define E2 -2
#define E3 0
#define Maximo   100


char *Prod[12] = { "T", "T'", "E", "E'", "F", "+", "*", "#", "I", "(", ")", "$" };


int tblAutomata[6][6]={
{0,99,99,0,99,99},
{99,1,99,99,2,2},
{3,99,99,3,99,99},
{99,5,4,99,5,5},
{6,99,99,7,99,99},
{99,99,99,99,99,100}};


enum Producciones { T, T_P, E, E_P, F, ADD, MUL, V, ID, PAR_A, PAR_C, FC };






CStack Pila( sLong(100) ); // DECLARACION DE LA PILA


int AutoTabla( const char* cadena );








void main()
{
   char cadena_ent[ Maximo ];
   
   cout << "*******AUTOMATA DE PILA**********"<<
     cout << "INCERTA CADENA: ";
     cin.getline( cadena_ent, Maximo);     
     strcat( cadena_ent,"$" ); //AGREGA SIMBOLO AL FINAL DE LA CADENA
     
     switch(AutoTabla(cadena_ent))
      {
        case E1: cout << "Error en la sintaxis" << endl; break;
        case E2: cout << "Caracter no valido" <
        case E3: cout << "ACEPTADA"<
      }
     
     Pila.sDelete();//ELIMINA LA PILA
}


int AutoTabla( const char *cadena )
{
   int i=0,tamCad=strlen(cadena);
   long elem, col=0,fil=0,pa=0;
   char *tmp;
   
   Pila.sPush( (long)&Prod[ FC ][ 0 ],NULL ); // INSERTA SIMBOLO DE FIN DE CADENA
   Pila.sPush( (long)&Prod[ E ][ 0 ], NULL ); // INSERTA INCIAL DE L APILA
   
   while(cadena[i])
    {
       Pila.sPeek( elem, NULL );
       tmp=(char*)elem;
       
       if(tmp[0]==cadena[i] || (isalpha(cadena[i]) && tmp[0]=='I'))
        {
          if( cadena[ i ] == '$' )
            if( !pa ) return E3;
else
return E1;
          
          if( cadena[ i ] == '(' )
 pa++;
          else 
 if( cadena[ i ] == ')' ) pa--;
           
          Pila.sPop( elem,NULL );
          i++; 
 continue;
        }
  
  
  
  
  
  
  ///////////////////////////////////////////////////////////////////////////////////////////////
  /////////////DA VALORES A FINA Y COLUMNA PARA RECORRER LA TABLA////////////////////////////////
  ///////////////////////////////////////////////////////////////////////////////////////////////
         
       if( !strcmp((char*)elem,Prod[E])) 
  fil = 0;   
       else 
  if( !strcmp( (char*)elem,Prod[E_P]) )
  fil = 1;
  else 
  if( !strcmp( (char*)elem,Prod[T]) ) 
  fil = 2;
  else 
  if( !strcmp( (char*)elem,Prod[T_P]) ) 
  fil = 3;
  else 
  if( !strcmp( (char*)elem,Prod[F]) ) 
  fil = 4;
  else
  if( !strcmp( (char*)elem,Prod[FC]) ) 
  fil = 5;
       
       if( isalpha( cadena[ i ] ) ) 
  col = 0;
       else
  if( cadena[ i ] == '+' ) 
  col = 1;
  else 
  if( cadena[ i ] == '*' ) 
  col = 2;
  else 
  if( cadena[ i ] == '(' ) 
  col = 3;
  else if( cadena[ i ] == ')' ) 
  col = 4;
  else 
  if( cadena[ i ] == '$' ) col = 5;


  else return E2;


  ///////////////////////////////////////////////////////////////////////////////////////////////
  ///////////////////////////////////////////////////////////////////////////////////////////////
  ///////////////////////////////////////////////////////////////////////////////////////////////






       switch( tblAutomata[fil][col] )//RECORRE LA TABLA
        {
          case 0:Pila.sPop( elem,NULL ); Pila.sPush( (long)&Prod[E_P][0],NULL );Pila.sPush( (long)&Prod[T][0],NULL ); 
            break;           
          case 1:Pila.sPop( elem,NULL);Pila.sPush( (long)&Prod[E_P][0],NULL );Pila.sPush( (long)&Prod[T][0],NULL );
 Pila.sPush( (long)&Prod[ADD][0],NULL );
            break;           
          case 2:Pila.sPop( elem,NULL );break;
 case 3:Pila.sPop( elem,NULL );Pila.sPush( (long)&Prod[T_P][0],NULL );Pila.sPush( (long)&Prod[F][0],NULL );
           break;           
          case 4:Pila.sPop( elem,NULL );Pila.sPush( (long)&Prod[T_P][0],NULL );Pila.sPush( (long)&Prod[F][0],NULL );
 Pila.sPush( (long)&Prod[MUL][0],NULL );
 break;
 case 5:Pila.sPop( elem,NULL );break;          
          case 6:Pila.sPop( elem,NULL );Pila.sPush( (long)&Prod[ID][0],NULL );break;           
          case 7:Pila.sPop( elem,NULL );Pila.sPush( (long)&Prod[PAR_C][0],NULL );Pila.sPush( (long)&Prod[E][0],NULL );
             Pila.sPush( (long)&Prod[PAR_A][0],NULL );break;           
          case 99: return E2;
          
          case 100: return E3;
        }




    }


   return E1;
}

// **** Pila.h **** \\

#ifndef STACK_CPP_H

#define STACK_CPP_H

#ifndef NULL

 #define NULL 0

#endif

  // constantes de excepciones

#define STACK_SUCCESS    0

#define STACK_EMPTY     -1

#define STACK_FULL      -2

#define STACK_ERR_MEM   -3

#define STACK_OUT_RANGE -4

#define sShort(code) (short)code

#define sLong(value) (long)value

typedef struct _STACK_SEGMENT // segmento de pila

{

  long dwData;

  void *vpAux;

  

} STACK_SEGMENT;

  

class CStack // clase manejadora de pila

{

   private:

    STACK_SEGMENT **sSegments;

    long dwSP;

    long dwSSize;

    short wExCod;

    

   public:

    CStack( long sMaxSize );

    CStack( short wCode ) : wExCod(wCode) { this-> sSegments = NULL; }

    ~CStack();

    

    const char* what() const throw();

    

    short sGetExCode();

    long GetSP();

    long GetStackMaxSize();

    long sPush( long dwData, const void** vpAux );

    long sPop( long& dwData, void** vpAux );

long sPeek( long& dwData, void** vpAux );

    long sDelete();

};

  // constructor

CStack::CStack( long sMaxSize )

{ 

  this-> dwSP      = -1;

  this-> wExCod    = 0;

  this-> dwSSize   = sMaxSize;

  this-> sSegments = NULL;

}

CStack::~CStack() { this-> sDelete(); } // Destructor

inline long CStack::GetSP() { return this-> dwSP; } // obtiene el puntero de pila

inline long CStack::GetStackMaxSize() { return this-> dwSSize;} // obtiene el tamaño maximo de pila

inline short CStack::sGetExCode() { return this-> wExCod; } // obtiene el codigo de excepcion

long CStack::sPush( long dwData, const void** vpAux ) // inserta un elemento en la pila

{

   STACK_SEGMENT **sAux;

   long i;

      // si la pila esta llena

   if( this-> dwSP >= this-> dwSSize-1 ) throw CStack( sShort(STACK_FULL) );

   this-> dwSP++;

   

   if( !this-> dwSP ) // si es el primer elemento

    {

      this-> sSegments = new STACK_SEGMENT* [this-> dwSP+1];

      if( !this-> sSegments ) throw CStack( sShort(STACK_ERR_MEM) );

      

      this-> sSegments[ this-> dwSP ] = new STACK_SEGMENT;

      if( !this-> sSegments[ this-> dwSP ] ) throw CStack( sShort(STACK_ERR_MEM) );

    }

   

   else // numero de elementos > 1

    {

      sAux = new STACK_SEGMENT* [this-> dwSP+1];

      if( !sAux ) throw CStack( sShort(STACK_ERR_MEM) );

      

      sAux[ this-> dwSP ] = new STACK_SEGMENT;

      if( !sAux[ this-> dwSP ] ) throw CStack( sShort(STACK_ERR_MEM) );

      

      for( i=0 ; i < this-> dwSP; i++ ) sAux[ i ] = this-> sSegments[ i ];

      

      delete[] this-> sSegments;

      

      this-> sSegments = sAux;

    }

   this-> sSegments[ this-> dwSP ]-> dwData = dwData;

   

   if( vpAux )

     this-> sSegments[ this-> dwSP ]-> vpAux  = (void*)*vpAux;

   else

     this-> sSegments[ this-> dwSP ]-> vpAux  = NULL;

   

   return this-> dwSP;

} // fin de sPush()

long CStack::sPop( long& dwData, void** vpAux ) // extrae un elemento de la pila

{

   STACK_SEGMENT **sAux;

   long i, tmpSP;

      // si la pila esta vacia

   if( this-> dwSP < 0 ) throw CStack( sShort(STACK_EMPTY) );

     

   dwData  = this-> sSegments[ this-> dwSP ]-> dwData;

   if( vpAux ) *vpAux = this-> sSegments[ this-> dwSP ]-> vpAux;

 

   if( !this-> dwSP ) // si hay un elemento

    {  

      delete this-> sSegments[ this-> dwSP ];

      delete[] this-> sSegments;

      

      this-> dwSP = -1;

    }

   

   else // si hay mas de 1 elemento

    { 

      sAux = new STACK_SEGMENT* [ this-> dwSP ];

      if( !sAux ) throw CStack( sShort(STACK_ERR_MEM) );

      

      delete this-> sSegments[ this-> dwSP ];

   

      this-> dwSP--;

 

      for( i=0; i <= this-> dwSP; i++ ) sAux[ i ] = this-> sSegments[ i ];

   

      delete[] this-> sSegments;

      

      this-> sSegments = sAux;

    }

    

   return this-> dwSP;

} // fin de sPop()

  // obtiene el elemeto en la cima sin extraerlo

long CStack::sPeek( long& dwData, void** vpAux )

{

   if( this-> dwSP < 0 ) throw CStack( sShort(STACK_EMPTY) );

   

   dwData = this-> sSegments[ this-> dwSP ]-> dwData;

   if( vpAux ) *vpAux  = this-> sSegments[ this-> dwSP ]-> vpAux;

   

   return this-> dwSP;

}

long CStack::sDelete() // Elimina la pila

{

   if( this-> sSegments )

    {

      for( ; this-> dwSP >= 0; this-> dwSP-- ) delete this-> sSegments[ this-> dwSP ];

      delete[] this-> sSegments;

    }

    

   return STACK_SUCCESS;

}

const char* CStack::what() const throw() // devuelve el texto de la excepcion

{

   switch( this-> wExCod )

    {

      case STACK_SUCCESS: return "Exito";

      case STACK_FULL:    return "Pila llena";

      case STACK_EMPTY:   return "Pila Vacia";

      case STACK_ERR_MEM: return "Error de asignacion de memoria";

    }

   

   return NULL;

}

#endif