TAD de las pilas: Reconocimiento de subpilas

Utilizando el tipo abstracto de datos de las pilas, definir la función

tal que subPila p1 p2 se verifica si p1 es una subpila de p2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las pilas: Reconocimiento de prefijos de pilas

Utilizando el tipo abstracto de datos de las pilas, definir la función

tal que prefijoPila p1 p2 se verifica si la pila p1 es justamente un prefijo de la pila p2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las pilas: Inclusión de pilas

Utilizando el tipo abstracto de datos de las pilas, definir la función

tal que contenidaPila p1 p2 se verifica si todos los elementos de de la pila p1 son elementos de la pila p2. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las pilas: Pertenencia a una pila

Utilizando el tipo abstracto de datos de las pilas, definir la función

tal que pertenecePila x p se verifica si x es un elemento de la pila p. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las pilas: Aplicación de una función a los elementos de una pila

Utilizando el tipo abstracto de datos de las pilas, definir la función

tal que mapPila f p es la pila formada con las imágenes por f de los elementos de pila p, en el mismo orden. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las pilas: Filtrado de pilas según una propiedad

Utilizando el tipo abstracto de datos de las pilas, definir la función

tal que filtraPila p q es la pila obtenida con los elementos de pila q que verifican el predicado p, en el mismo orden. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

TAD de las pilas: Transformaciones entre pilas y listas

Utilizando el tipo abstracto de datos de las pilas, definir las funciones

tales que

  • listaApila xs es la pila formada por los elementos de xs. Por ejemplo,

  • pilaAlista p es la lista formada por los elementos de la pila p. Por ejemplo,

Comprobar con QuickCheck que ambas funciones son inversa; es decir,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

El tipo abstracto de datos de las pilas

1. El tipo abstracto de datos de las pilas

Una pila es una estructura de datos, caracterizada por ser una secuencia de elementos en la que las operaciones de inserción y extracción se realizan por el mismo extremo.

Las operaciones que definen a tipo abstracto de datos (TAD) de las pilas (cuyos elementos son del tipo a) son las siguientes:

tales que

  • vacia es la pila vacía.
  • (apila x p) es la pila obtenida añadiendo x al principio de p.
  • (cima p) es la cima de la pila p.
  • (desapila p) es la pila obtenida suprimiendo la cima de p.
  • (esVacia p) se verifica si p es la pila vacía.

Las operaciones tienen que verificar las siguientes propiedades:

  • cima(apila(x, p) == x
  • desapila(apila(x, p)) == p
  • esVacia(vacia)
  • not esVacia(apila(x, p))

2. Las pilas en Haskell

2.1. El tipo abstracto de datos de las pilas en Haskell

El TAD de las pilas se encuentra en el módulo Pila.hs cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2.2. Implementación de las pilas mediante listas

La implementación se encuentra en el módulo PilaConListas.hs cuyo contenido es el siguiente:

2.3. Implementación de las pilas mediante sucesiones

La implementación (que usa la librería Data.Sequence) se encuentra en el módulo PilaConSucesiones.hs cuyo contenido es el siguiente:

3. Las pilas en Python

3.1. El tipo abstracto de las pilas en Python

La implementación se encuentra en el módulo pila.py cuyo contenido es el siguiente:

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

3.2. Implementación de las pilas mediante listas

La implementación se encuentra en el módulo pilaConListas.py en el que se define la clase Pila con los siguientes métodos:

  • apila(x) añade x al principio de la pila.
  • cima() devuelve la cima de la pila.
  • desapila() elimina la cima de la pila.
  • esVacia() se verifica si la pila es vacía.

Por ejemplo,

Además se definen las correspondientes funciones. Por ejemplo,

Finalmente, se define un generador aleatorio de pilas y se comprueba que las pilas cumplen las propiedades de su especificación.

3.3. Implementación de las pilas mediante deque

La implementación (que usa la librería deque) se encuentra en el módulo pilaConDeque.py y su contenido es el siguiente:

Valor de una expresión vectorial

Se consideran las expresiones vectoriales formadas por un vector, la suma de dos expresiones vectoriales o el producto de un entero por una expresión vectorial. El siguiente tipo de dato define las expresiones vectoriales

Definir la función

tal que valorEV e es el valorEV de la expresión vectorial e. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Valor de expresiones aritméticas generales

Las operaciones de suma, resta y multiplicación se pueden representar mediante el siguiente tipo de datos

La expresiones aritméticas con dichas operaciones se pueden representar mediante el siguiente tipo de dato algebraico

Por ejemplo, la expresión

se representa por

Definir la función

tal que valor e es el valor de la expresión e. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python

Máximos valores de una expresión aritmética

Las expresiones aritméticas generales se pueden definir usando el siguiente tipo de datos

Por ejemplo, la expresión

se puede definir por

Definir la función

tal que maximo e xs es el par formado por el máximo valor de la expresión e para los puntos de xs y en qué puntos alcanza el máximo. Por ejemplo,

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell


Soluciones en Python