Free Web Site - Free Web Space and Site Hosting - Web Hosting - Internet Store and Ecommerce Solution Provider - High Speed Internet
Search the Web

Palabras balanceadas ocupando Autómatas PUSH-DOWN

Sin duda uno de los más importantes usos de las pilas, es en el reconocimientos de gramaticas , a través de lo que se conoce como autómatas apiladores (PUSH - DOWN).

Implementar métodos para reconocer cualquier gramática es un un tanto más complicado que implementar uno o dos métodos.
Es por eso que con el siguiente programa de prueba, se pretende mostrar una solución muy epecífica con respecto a una forma de gramaticas, obviamente para conocer un poco más del uso de las pilas.

El siguiente programa, implementa un método que reconoce una gramatica del tipo : S -> PSX S -> PX P -> símbolo de apilamiento X -> símbolo de desapilamiento que en términos sencillos reconoce una palabra que cumpla que por cada símbolo P a la izquierda, existe un símbolo X a la derecha. Ejemplo : aabb , abab , aababb , aababbab , 0011 , 0101 , ( ( ) ) , ...

La idea de esta solución computacional (personal) para resolver el problema es la siguiente :

Leer simbolo de apilamiento
Leer simbolo de desapilamiento
Leer palabra

ch =  carácter i-esimo de la palabra

SI ( ch == simbolo de apilamiento ) ENTONCES
    apilar simbolo
SINO
    SI (ch == simbolo de desapilamiento) ENTONCES
        desapilar
    FIN SI
FIN SI

SI (se trata de despilar con la pila vacía)ENTONCES
   salir del ciclo y marcar un error
FIN SI 

SI (no hubo error durante el proceso)ENTONCES
    SI la pila es vacía ENTONCES
        se reconoce palabra
    SINO 
        no se reconoce
    FIN SI
SINO
    no se reconoce
FIN SI

Implementación

import java.io.*;

class balance
{
    public static void procesarPalabra (String entrada , char chApila , char chDesapila)
    {
        Pila stack = new PilaLi( );
        
        Character charApila = new Character(chApila);
        Character charDesapila = new Character(chDesapila);
        
        Character ch;
        
        boolean error = false; 
        for(int i = 0; i < entrada.length( ); i++)
        {
            ch = new Character(entrada.charAt(i));
            
            try
            {
                if (charApila.equals(ch))
                    stack.push(ch);    
                else 
                    if ( charDesapila.equals(ch))
                        stack.pop( );
            } 
            catch(Exception e) 
            { 
                error = true;
                break;  
            }    
        }    
        
        if (error == false)
        {
            if (stack.esVacia( ) ) 
                System.out.println("\tCadena balanceada");    
            else
                System.out.println("\tCadena no balanceada");    
         }
         else System.out.println("\tCadena no balanceada");
    }
    
    
    public static void main(String arg[ ])
    {
        BufferedReader in = new BufferedReader(new
            InputStreamReader(System.in));
        
        String entrada = null;
        
        String palabra = null;
        char charApilamiento;
        char charDesapilamiento;
        
        char seguir = 'n';
        
        try
        {
            do
            {
                System.out.print("\n\tIngrese caracter de apilamiento : ");
                entrada = in.readLine( );
                charApilamiento = entrada.charAt(0);
            
                System.out.print("\tIngrese caracter de desapilamiento : ");
                entrada = in.readLine( );
                charDesapilamiento = entrada.charAt(0);
            
                System.out.print("\tIngrese la palabra : ");
                entrada = in.readLine( );
        
                palabra = entrada;
            
                if (palabra != null) 
                    procesarPalabra(palabra,charApilamiento,charDesapilamiento);

                System.out.print("\n\tQuiere seguir (s / n) : ");
                entrada = in.readLine( );
                
                if (entrada.charAt(0) == 's') continue;
                else
                { 
                   if (entrada.charAt(0) == 'n') break;
                   else break;
                }
        
            } while(true);
        
        } catch(IOException e) { System.out.println("\n Error de entrada"); }
    }    
    
}

bajar archivo