Home UC3M Universidad Carlos III de Madrid - Departamento de Ingeniería Telemática Home IT
Localización | Personal | Docencia | Investigación | Novedades | Intranet  

Práctica 8.- Pilas

Datos de la práctica

Fecha 15 de abril de 2008
Conceptos Listas enlazadas, pilas

Contenidos

Ejercicio 1.- Implementación de una pila con listas enlazadas

Apartado 1

Implementa una pila utilizando una lista enlazada como estructura de datos. La pila debe permitir almacenar cualquier tipo de objeto, e implementar al menos métodos para:

Diseña la clase, decidiendo el nombre de cada método, sus parámetros y su valor de retorno. (Pista: Crea una clase interna Nodo, que sea la encargada de almacenar los valores de la pila)

Apartado 2

Haz una clase de prueba que lea líneas de teclado y las imprima en orden inverso en pantalla. Por ejemplo, si introduces cuatro líneas "A", "B", "C" y "D", debe imprimir "D", "C", "B" y "A". La solución debe utilizar internamente una pila.

Ejercicio 2.- Comprobación de equilibrado de código

Ahora, utilizaremos la pila para resolver un problema clásico de compiladores: el emparejamiento de llaves { }, corchetes [ ], paréntesis ( ), y comentarios estilo /* */ de un lenguaje de programación (típicamente Java, Pascal, C o C++). Tu programa debe leer el fichero de entrada e indicar si los caracteres anteriores están bien o mal emparejados. Implementa para ello el siguiente algoritmo:

  1. Crear una pila vacía
  2. Leer caracteres hasta el final del fichero. Para cada carácter leído, si es un símbolo de apertura o cierre:
    • Si el símbolo es de apertura, apilarlo en la pila
    • Si el símbolo es de terminación y la pila está vacía, producir un error.
    • Si el símbolo es de terminación y la pila no está vacía, desapilar la cima de la pila. Si el símbolo desapilado no es el símbolo de apertura correspondiente, producir un error.

  3. Al finalizar el fichero, si la pila no está vacía, producir un error.

Ejercicio 3.- Calculadora postfija (complementario)

En este ejercicio debes programar una calculadora sencilla basada en una máquina postfija (simplificación del ejemplo del libro de Weiss recomendado en la bibliografía, páginas 301-312).

La calculadora debe admitir expresiones con operadores "+" y "*", y valores naturales (tipo long). Por ejemplo: "3+2*4". El operador "*" tiene más precedencia que "+". Por tanto, la expresión anterior vale 11 (y no 24, como ocurriría en caso contrario). Para simplificar el ejercicio, no se permite el uso de paréntesis en las expresiones.

Descarga un esqueleto de la clase Calculadora.java, que proporciona los atributos y el constructor de la clase, así como la signatura del resto de los métodos.

La implementación se basa en dos pilas, una de operadores y otra de operandos. La expresión aritmética se descompone en símbolos, representados por números enteros: TOK_EOL (fin de expresión), TOK_VALOR (operando), TOK_MAS (operador "+"), TOK_POR (multiplicación). Cada invocación al método obtenerToken() devuelve el siguiente símbolo de la expresión. Si el símbolo es un operando, su valor se almacena en el atributo valorActual.

El método getValor() debe, sucesivamente, leer un nuevo símbolo y procesarlo. Cuando no queden símbolos por procesar, debería haber un único valor en la pila de operandos, que es el resultado de la operación.

El método procesarToken debe contener el código para procesar cada símbolo:

El cálculo de un operador se realiza en el método operadorBinario(). En él, se desapilan dos valores de la pila de valores, se les aplica el operando correspondiente, y se apila el resultado en la pila de valores.

Se pide: completa el código de la clase Calculadora. Para probarla, añádele un método main que imprima el resultado de evaluar la expresión que reciba como argumento.

Ejercicio 4.- Exploración de Saturno (complementario)

La ESA está desarrollando un proyecto para colocar un robot de exploración sobre la superficie de Saturno. Dado el retardo de comunicaciones existente entre La Tierra y Saturno, el robot debe ser capaz de realizar exploraciones de forma autónoma. Por ello, está controlado por un complejo sistema de inteligencia artificial (IA). Dado que un mal movimiento del robot puede suponer el fracaso de la misión, el módulo de IA debe comportarse de forma conservadora.

El robot parte siempre desde una posición base que considera totalmente segura. A partir de ahí realiza movimientos de exploración siguiendo las órdenes del módulo de IA. En todo momento evalúa su posición y los destinos alcanzables desde ella. Cuando determina que la posición actual es peligrosa o que no puede seguir explorando con seguridad, realiza movimientos de regreso hacia la base: vuelve progresivamente sobre sus propios pasos hasta llegar a una posición anterior más satisfactoria, y continuar desde ella su exploración por otros caminos. Ten en cuenta que, cuando regresa hacia la base, no tiene por qué realizar el camino completo de regreso, sino que puede regresar hasta un punto intermedio y continuar desde él su exploración.

El robot será capaz de realizar dos tipos de movimientos básicos: desplazamientos (avanzar o retroceder) y rotaciones sobre su vertical (derecha o izquierda). Para realizar un desplazamiento es necesario especificar la distancia (entero que representa centímetros, negativo para retroceder). Para realizar una rotación es necesario especificar el ángulo (entero que representa grados, negativo hacia la izquierda, entre -180 y 180).

Formas parte del equipo de ingenieros de la ESA, y se te ha encargado programar la clase RegistroMovimientos, que registre en una pila los movimientos del robot de tal forma que el robot sepa volver en todo momento a la posición base deshaciendo movimientos básicos hechos previamente.

Los movimientos básicos del robot se representan con la clase Movimiento.java.

Programa la clase RegistroMovimientos, incluyendo sus atributos y un constructor sin parámetros. Programa además los siguientes métodos:

Los altos cargos de la ESA no se fían completamente de los ingenieros que desarrollaron el módulo de IA. Por ello, desean tener un mecanismo de control remoto desde la Tierra, para situaciones excepcionales, en que un operario pueda introducir comandos directamente. La interfaz gráfica está desarrollada en las clases: Saturno.java y Mapa.java (descarga también la imagen paisaje.jpg). Ejecútala como programa de prueba de la clase que has implementado.

Soluciones