Menu Close

TAD de las pilas: Transformaciones entre pilas y listas

José A. Alonso,

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

   listaApila :: [a] -> Pila a
   pilaAlista :: Pila a -> [a]

tales que

  • listaApila xs es la pila formada por los elementos de xs. Por ejemplo,
     λ> listaApila [3, 2, 5]
     5 | 2 | 3
  • pilaAlista p es la lista formada por los elementos de la pila p. Por ejemplo,
     λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia)))
     [3, 2, 5]

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

   pilaAlista (listaApila xs) == xs
   listaApila (pilaAlista p)  == p

Soluciones

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


Soluciones en Haskell

module Transformaciones_pilas_listas where
 
import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)
import Test.QuickCheck
 
-- 1ª definición de listaApila
-- ===========================
 
listaApila :: [a] -> Pila a
listaApila ys = aux (reverse ys)
  where aux []     = vacia
        aux (x:xs) = apila x (aux xs)
 
-- 2ª definición de listaApila
-- ===========================
 
listaApila2 :: [a] -> Pila a
listaApila2 = aux . reverse
  where aux [] = vacia
        aux (x:xs) = apila x (aux xs)
 
-- 3ª definición de listaApila
-- ===========================
 
listaApila3 :: [a] -> Pila a
listaApila3 = aux . reverse
  where aux = foldr apila vacia
 
-- 4ª definición de listaApila
-- ===========================
 
listaApila4 :: [a] -> Pila a
listaApila4 xs = foldr apila vacia (reverse xs)
 
-- 5ª definición de listaApila
-- ===========================
 
listaApila5 :: [a] -> Pila a
listaApila5 = foldr apila vacia . reverse
 
-- Comprobación de equivalencia de las definiciones de listaApila
-- ==============================================================
 
-- La propiedad es
prop_listaApila :: [Int] -> Bool
prop_listaApila xs =
  all (== listaApila xs)
      [listaApila2 xs,
       listaApila3 xs,
       listaApila4 xs,
       listaApila5 xs]
 
-- La comprobación es
--    λ> quickCheck prop_listaApila
--    +++ OK, passed 100 tests.
 
-- 1ª definición de pilaAlista
-- ===========================
 
pilaAlista :: Pila a -> [a]
pilaAlista p
  | esVacia p = []
  | otherwise = pilaAlista dp ++ [cp]
  where cp = cima p
        dp = desapila p
 
-- 2ª definición de pilaAlista
-- ===========================
 
pilaAlista2 :: Pila a -> [a]
pilaAlista2 = reverse . aux
  where aux p | esVacia p = []
              | otherwise = cp : aux dp
          where cp = cima p
                dp = desapila p
 
-- Comprobación de equivalencia de las definiciones de pilaAlista
-- ==============================================================
 
-- La propiedad es
prop_pilaAlista :: Pila Int -> Bool
prop_pilaAlista p =
  pilaAlista p == pilaAlista2 p
 
-- La comprobación es
--    λ> quickCheck prop_pilaAlista
--    +++ OK, passed 100 tests.
 
-- Comprobación de las propiedades
-- ===============================
 
-- La primera propiedad es
prop_1_listaApila :: [Int] -> Bool
prop_1_listaApila xs =
  pilaAlista (listaApila xs) == xs
 
-- La comprobación es
--    λ> quickCheck prop_1_listaApila
--    +++ OK, passed 100 tests.
 
-- La segunda propiedad es
prop_2_listaApila :: Pila Int -> Bool
prop_2_listaApila p =
  listaApila (pilaAlista p) == p
 
-- La comprobación es
--    λ> quickCheck prop_2_listaApila
--    +++ OK, passed 100 tests.


Soluciones en Python

from copy import deepcopy
from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,
                          vacia)
 
A = TypeVar('A')
 
# 1ª definición de listaApila
# ===========================
 
def listaApila(ys: list[A]) -> Pila[A]:
    def aux(xs: list[A]) -> Pila[A]:
        if not xs:
            return vacia()
        return apila(xs[0], aux(xs[1:]))
 
    return aux(list(reversed(ys)))
 
# 2ª solución de listaApila
# =========================
 
def listaApila2(xs: list[A]) -> Pila[A]:
    p: Pila[A] = Pila()
    for x in xs:
        p.apila(x)
    return p
 
# Comprobación de equivalencia de las definiciones de listaApila
# ==============================================================
 
# La propiedad es
@given(st.lists(st.integers()))
def test_listaApila(xs: list[int]) -> None:
    assert listaApila(xs) == listaApila2(xs)
 
# 1ª definición de pilaAlista
# ===========================
 
def pilaAlista(p: Pila[A]) -> list[A]:
    if esVacia(p):
        return []
    cp = cima(p)
    dp = desapila(p)
    return pilaAlista(dp) + [cp]
 
# 2ª definición de pilaAlista
# ===========================
 
def pilaAlista2Aux(p: Pila[A]) -> list[A]:
    if p.esVacia():
        return []
    cp = p.cima()
    p.desapila()
    return pilaAlista2Aux(p) + [cp]
 
def pilaAlista2(p: Pila[A]) -> list[A]:
    p1 = deepcopy(p)
    return pilaAlista2Aux(p1)
 
# 3ª definición de pilaAlista
# ===========================
 
def pilaAlista3Aux(p: Pila[A]) -> list[A]:
    r = []
    while not p.esVacia():
        r.append(p.cima())
        p.desapila()
    return r[::-1]
 
def pilaAlista3(p: Pila[A]) -> list[A]:
    p1 = deepcopy(p)
    return pilaAlista3Aux(p1)
 
# Comprobación de equivalencia de las definiciones de pilaAlista
# ==============================================================
 
@given(p=pilaAleatoria())
def test_pilaAlista(p: Pila[int]) -> None:
    assert pilaAlista(p) == pilaAlista2(p)
    assert pilaAlista(p) == pilaAlista3(p)
 
# Comprobación de las propiedades
# ===============================
 
# La primera propiedad es
@given(st.lists(st.integers()))
def test_1_listaApila(xs: list[int]) -> None:
    assert pilaAlista(listaApila(xs)) == xs
 
# La segunda propiedad es
@given(p=pilaAleatoria())
def test_2_listaApila(p: Pila[int]) -> None:
    assert listaApila(pilaAlista(p)) == p
 
# La comprobación es
#      src> poetry run pytest -v transformaciones_pilas_listas.py
#      test_listaApila PASSED
#      test_pilaAlista PASSED
#      test_1_listaApila PASSED
#      test_2_listaApila PASSED
Haskell y Python
,

Una solución de “TAD de las pilas: Transformaciones entre pilas y listas”

  1. Responder
    chatGPT

    Aquí hay una implementación para las dos funciones que ha definido:

    listaApila :: [a] -> Pila a
listaApila xs = foldr apila vacia xs
 
pilaAlista :: Pila a -> [a]
pilaAlista p
    | esVacia p = []
    | otherwise = cima p : pilaAlista (desapila p)

    listaApila está implementada usando la función foldr, que aplica la función apila a cada elemento de la lista de entrada y la pila actual, comenzando con la pila vacía. Esto efectivamente agrega cada elemento de la lista a la pila, en orden inverso.

    pilaAlista está implementado mediante recursión. Verifica si la pila está vacía, y si es así, devuelve una lista vacía. Si la pila no está vacía, toma el elemento superior de la pila con cima y lo conecta con el resultado de llamar a pilaAlista en la pila restante obtenida por desapila la pila original. Esto efectivamente saca cada elemento de la pila y lo agrega a la lista en el orden correcto.

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.