TAD de las pilas: Reconocimiento de ordenación de pilas
Utilizando el tipo abstracto de datos de las pilas, definir la función
|
1 |
ordenadaPila :: Ord a => Pila a -> Bool |
tal que ordenadaPila p se verifica si los elementos de la pila p están ordenados en orden creciente. Por ejemplo,
|
1 2 |
ordenadaPila (apila 1 (apila 5 (apila 6 vacia))) == True ordenadaPila (apila 1 (apila 0 (apila 6 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 37 38 39 40 41 42 43 44 |
import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila) import Transformaciones_pilas_listas (pilaAlista) import Test.QuickCheck -- 1ª solución -- =========== ordenadaPila :: Ord a => Pila a -> Bool ordenadaPila p | esVacia p = True | esVacia dp = True | otherwise = cp <= cdp && ordenadaPila dp where cp = cima p dp = desapila p cdp = cima dp -- 2ª solución -- =========== ordenadaPila2 :: Ord a => Pila a -> Bool ordenadaPila2 = ordenadaLista . reverse . pilaAlista -- (ordenadaLista xs) se verifica si la lista xs está ordenada de menor -- a mayor. Por ejemplo, ordenadaLista :: Ord a => [a] -> Bool ordenadaLista xs = and [x <= y | (x,y) <- zip xs (tail xs)] -- Se usará la función pilaAlista del ejercicio -- "Transformaciones entre pilas y listas" que se encuentra en -- https://bit.ly/3ZHewQ8 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_ordenadaPila :: Pila Int -> Bool prop_ordenadaPila p = ordenadaPila p == ordenadaPila2 p -- La comprobación es -- λ> quickCheck prop_ordenadaPila -- +++ 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 76 77 78 79 80 81 82 83 84 85 86 87 88 |
from copy import deepcopy from typing import TypeVar from hypothesis import given from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria, vacia) from src.transformaciones_pilas_listas import pilaAlista A = TypeVar('A', int, float, str) # 1ª solución # =========== def ordenadaPila(p: Pila[A]) -> bool: if esVacia(p): return True cp = cima(p) dp = desapila(p) if esVacia(dp): return True cdp = cima(dp) return cp <= cdp and ordenadaPila(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 # ordenadaLista(xs, ys) se verifica si xs es una lista ordenada. Por # ejemplo, # >>> ordenadaLista([2, 5, 8]) # True # >>> ordenadalista([2, 8, 5]) # False def ordenadaLista(xs: list[A]) -> bool: return all((x <= y for (x, y) in zip(xs, xs[1:]))) def ordenadaPila2(p: Pila[A]) -> bool: return ordenadaLista(list(reversed(pilaAlista(p)))) # 3ª solución # =========== def ordenadaPila3Aux(p: Pila[A]) -> bool: if p.esVacia(): return True cp = p.cima() p.desapila() if p.esVacia(): return True return cp <= p.cima() and ordenadaPila3Aux(p) def ordenadaPila3(p: Pila[A]) -> bool: q = deepcopy(p) return ordenadaPila3Aux(q) # 4ª solución # =========== def ordenadaPila4Aux(p: Pila[A]) -> bool: while not p.esVacia(): cp = p.cima() p.desapila() if not p.esVacia() and cp > p.cima(): return False return True def ordenadaPila4(p: Pila[A]) -> bool: q = deepcopy(p) return ordenadaPila4Aux(q) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(p=pilaAleatoria()) def test_ordenadaPila(p: Pila[int]) -> None: r = ordenadaPila(p) assert ordenadaPila2(p) == r assert ordenadaPila3(p) == r assert ordenadaPila4(p) == r # La comprobación es # src> poetry run pytest -q ordenadaPila.py # 1 passed in 0.31s |
Puedes implementar la función ordenadaPila siguiendo estos pasos:
La implementación sería: