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 |