PRÁCTICA Nş 4: 1 sesión
(del 2 de Abril al 6 de Abril de 2001)
Estructuras de datos lineales. Trabajo con Pilas.
0. Objetivo
El objetivo de esta práctica es la realización de una clase en C++ que implemente el tipo abstracto de datos pila, y la realización de un programa que haga uso de ella.
1. ESTRUCTURAS DE DATOS LINEALES. tAD PILA
Las pilas son estructuras de datos lineales, denominadas así, porque consisten en una secuencia de elementos a0, a1, ..., an-1 dispuestos en una dimensión. Dependiendo del tipo de elementos que queramos almacenar, podremos tener distintos tipos de pilas. Así, tendremos pilas de enteros, de caracteres, etc, pudiendo tener también pilas de otros TAD’s.
Dentro de las estructuras lineales, las pilas también se conocen como estructuras LIFO (Last In, First Out). El nombre LIFO hace referencia al modo en que se accede a los elementos, ya que todas las inserciones y supresiones tienen lugar en un extremo denominado tope.
Suponiendo que los elementos a0, a1, ..., an-1 son de un cierto tipo Valor, las operaciones de las que consta el TAD PILA son las siguientes:
IniciarPila ( ) ® Pila
Que inicia la pila como una pila vacía
PilaVacia (Pila) ® Booleano
Que devuelve true en caso de que la pila esté vacía
Apilar (Pila, Valor) ® Pila
Que apila, si es posible, el elemento x en la cima de la pila.
Desapilar (Pila) ® Pila
Que desapila, si es posible, el elemento situado en la cima de la pila.
CimaPila (Pila) ® Valor
Que devuelve, si es posible, el valor situado en la cima de la pila.
2. IMPLEMENTACIÓN DE LA CLASE PILA DE CARACTERES
Deseamos crear una clase PilaCar que represente al TAD Pila de caracteres.
Realizaremos dos implementaciones distintas, tal y como se ha visto en clase: Una implementación estática y una implementación dinámica.
En la representación estática preveremos un máximo de 1000 caracteres.
En cualquier caso, las operaciones de acceso a la pila serán las presentes en la parte pública de la clase, y serán las mismas en el caso estático y en el caso dinámico:
Pila (void);
Constructor de la clase. Inicia la pila a vacía
bool PilaVacia (void);
Comprobación de si hay o no elementos en la pila
bool Apilar (char ch);
Apilará, si se puede ch en la cima de la pila y devolverá true. Si no se puede, devolverá false.
bool Desapilar (void);
Si hay elementos en la pila, eliminará uno y devolverá true. Si no hay elementos en la pila devolverá false
bool CimaPila (char & ch);
Si hay elementos en la pila, pondrá en ‘ch’ el que esté en la cima y devolverá true. Si no hay elementos en la pila devolverá false
3. Utilización del tipo abstracto de datos pila de caracteres
Tarea 1: Trabajo con ficheros de texto
Debido a la dificultad que tenemos en detectar los errores de parsing que nos muestra el compilador en nuestros programas, deseamos implementar un programa que analice un fichero y nos diga si contiene algún error de parsing o no. Los caracteres que vamos a controlar son las llaves, los corchetes y los paréntesis. Por tanto, nos tendremos que asegurar que por cada carácter ‘{‘ existe un ‘}’, que para cada ‘[‘ hay un ‘]’, y que cada ‘(‘ viene cerrado por su correspondiente ‘)’, y todos en el orden adecuado, es decir, anidados y no solapados.
Para poder controlar la existencia o no de errores, utilizaremos la clase pila de caracteres, apilando cada vez que encontremos en el archivo ‘{‘, ‘[‘, y ‘(‘, y desapilando cuando leamos del archivo un ‘}’, ‘)’, ‘]’ y en la cima de la pila se encuentre su correspondiente de apertura. Si no es así, habremos descubierto un error, y deberemos indicar el número de línea en el que se produjo. Para que el archivo procesado sea correcto, la pila deberá estar vacía al final del procesamiento del archivo.
Veamos tres ejemplos de lo que nos debería devolver el programa:
FICHERO 1
#include <iostream.h>
int main ( )
{
cout << "Archivo correcto";
}
Al analizar el fichero 1, el programa nos diría que el programa es correcto.
FICHERO 2
#include <iostream.h>
int main ( )
{
int i;
for (i = 0; i < 10; i++}
cout << i;
}
Al analizar el fichero 2, el programa nos indicaría que existe un error en la línea 7.
FICHERO 3
#include <iostream.h>
int main ()
{
cout << "Hola";
Al analizar el fichero 3, el programa nos indicaría que esperaba un ‘}’ y encontró el final del fichero.
Tarea 2: Análisis de una frase palíndroma mediante la utilización de pilas
Realizar un programa que pida una frase por teclado y evalúe si la frase es palíndroma o no lo es.
El análisis se limitará a guardar en una pila los caracteres de la frase hasta el central, y luego desapilarlos y comprobar que son los correspondientes que quedan en la cadena.
En ningún caso se pide la utilización de menús ni opciones en estos programas.
En esta práctica, se trata, por un lado, de realizar un programa debidamente estructurado, mediante la utilización de subprogramas adecuados, y por otro, empezar a utilizar de forma estricta las normas de estilo de la Guía de C++. Las prácticas que no cumplan las normas de estilo serán mal calificadas.
Es importante destacar que ambos programas han de poder ser compilados con las dos implementaciones de la pila, sólo cambiando el fichero de cabecera incluido en el programa principal y el linkado final del ejecutable.
Las soluciones que no cumplan este requisito serán consideradas incorrectas.
4. Entrega de programas
Al finalizar la siguiente sesión de prácticas se entregarán al profesor los archivos ‘pila_v.h’, ‘pila_v.cpp’, ‘pila_p.h’, ‘pila_p.cpp’ correspondientes al TAD pila con vectores y con punteros, y dos programas principales: ‘ficher.cpp’ y ‘palind.cpp’ correspondientes a las tareas 1 y 2 de la práctica.
ENTREGA DE PROGRAMAS:
Al iniciar la sesión de prácticas siguiente.