miércoles, 14 de marzo de 2012

Balanceo con Pilas

Planteo del problema:
Este práctico tiene por objetivo mostrar la importancia de las pilas en las Ciencias de la Computación y más precisamente en la programación de software de bajo nivel.
Todo compilador o intérprete de un lenguaje tiene un módulo dedicado a analizar si una expresión está correctamente codificada, es decir que los paréntesis estén abiertos y cerrados en un orden lógico y bien balanceados.
Se debe desarrollar una clase que tenga las siguientes responsabilidades (clase Formula):


- Ingresar una fórmula que contenga paréntesis, corchetes y llaves.
- Validar que los ( ) [] y {} estén correctamente balanceados.


Para la solución de este problema la clase formula tendrá un atributo de la clase Pila.
Veamos como nos puede ayudar el empleo de una pila para solucionar este problema.
Primero cargaremos la fórmula en un JTextField.
Ejemplo de fórmula: (2+[3-12]*{8/3})
El algoritmo de validación es el siguiente:
Analizamos caracter a caracter la presencia de los paréntesis, corchetes y llaves.
Si vienen símbolos de apertura los almacenamos en la pila.
Si vienen símbolos de cerrado extraemos de la pila y verificamos si está el mismo símbolo pero de apertura: en caso negativo podemos inferir que la fórmula no está correctamente balanceada.
Si al finalizar el análisis del último caracter de la fórmula la pila está vacía podemos concluir que está correctamente balanceada.
Ejemplos de fórmulas no balanceadas:

}(2+[3-12]*{8/3})
Incorrecta: llega una } de cerrado y la pila está vacía.
{[2+4}]
Incorrecta: llega una llave } y en el tope de la pila hay un corchete [.
{[2+4]
Incorrecta: al finalizar el análisis del último caracter en la pila queda pendiente una llave {.



public boolean balanceada() {
        Pila pila1;  
     pila1 = new Pila ();    
     String cadena=tf1.getText();
     for (int f = 0 ; f < cadena.length() ; f++)
     {
         if (cadena.charAt(f) == '(' || cadena.charAt(f) == '[' || cadena.charAt(f) == '{') {
          pila1.insertar(cadena.charAt(f));
         } else {
          if (cadena.charAt(f)==')') {
              if (pila1.extraer()!='(') {
                  return false;
              }
           } else {
              if (cadena.charAt(f)==']') {
                  if (pila1.extraer()!='[') {
                      return false;
                  }
              } else {
                  if (cadena.charAt(f)=='}') {
                      if (pila1.extraer()!='{') {
                          return false;
                      }
                  }
              }
             }
        }   
        }
     if (pila1.vacia()) {
         return true;
     } else {
        return false;
     }
    }

0 comentarios:

Publicar un comentario en la entrada