TAD de las pilas: Pertenencia a una pila
Utilizando el tipo abstracto de datos de las pilas, definir la función
|
1 |
pertenecePila :: Eq a => a -> Pila a -> Bool |
tal que pertenecePila x p se verifica si x es un elemento de la pila p. Por ejemplo,
|
1 2 |
pertenecePila 2 (apila 5 (apila 2 (apila 3 vacia))) == True pertenecePila 4 (apila 5 (apila 2 (apila 3 vacia))) == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila) import Transformaciones_pilas_listas (pilaAlista) import Test.QuickCheck -- 1ª solución -- =========== pertenecePila :: Eq a => a -> Pila a -> Bool pertenecePila x p | esVacia p = False | otherwise = x == cp || pertenecePila x dp where cp = cima p dp = desapila p -- 2ª solución -- =========== -- Se usará la función pilaAlista del ejercicio -- "Transformaciones entre pilas y listas" que se encuentra en -- https://bit.ly/3ZHewQ8 pertenecePila2 :: Eq a => a -> Pila a -> Bool pertenecePila2 x p = x `elem` pilaAlista p -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_pertenecePila :: Int -> Pila Int -> Bool prop_pertenecePila x p = pertenecePila x p == pertenecePila2 x p -- La comprobación es -- λ> quickCheck prop_pertenecePila -- +++ OK, passed 100 tests. |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
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) from src.transformaciones_pilas_listas import pilaAlista A = TypeVar('A') # 1ª solución # =========== def pertenecePila(x: A, p: Pila[A]) -> bool: if esVacia(p): return False cp = cima(p) dp = desapila(p) return x == cp or pertenecePila(x, dp) # 2ª solución # =========== # Se usará la función pilaAlista del ejercicio # "Transformaciones entre pilas y listas" que se encuentra en # https://bit.ly/3ZHewQ8 def pertenecePila2(x: A, p: Pila[A]) -> bool: return x in pilaAlista(p) # 3ª solución # =========== def pertenecePila3Aux(x: A, p: Pila[A]) -> bool: if p.esVacia(): return False cp = p.cima() p.desapila() return x == cp or pertenecePila3Aux(x, p) def pertenecePila3(x: A, p: Pila[A]) -> bool: p1 = deepcopy(p) return pertenecePila3Aux(x, p1) # 4ª solución # =========== def pertenecePila4Aux(x: A, p: Pila[A]) -> bool: while not p.esVacia(): cp = p.cima() p.desapila() if x == cp: return True return False def pertenecePila4(x: A, p: Pila[A]) -> bool: p1 = deepcopy(p) return pertenecePila4Aux(x, p1) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(x=st.integers(), p=pilaAleatoria()) def test_pertenecePila(x: int, p: Pila[int]) -> None: r = pertenecePila(x, p) assert pertenecePila2(x, p) == r assert pertenecePila3(x, p) == r assert pertenecePila4(x, p) == r # La comprobación es # src> poetry run pytest -q pertenecePila.py # 1 passed in 0.37s |
La función pertenecePila puede ser definida de la siguiente manera:
La función comienza verificando si la pila está vacía, en cuyo caso devuelve False, ya que el elemento no puede estar en una pila vacía. Luego, se verifica si el elemento en la cima de la pila es igual al elemento buscado, en cuyo caso devuelve True. Si ninguna de estas condiciones se cumple, se llama recursivamente a pertenecePila con la pila desapilada y el mismo elemento buscado.