TAD de las pilas: Reconocimiento de subpilas
Utilizando el tipo abstracto de datos de las pilas, definir la función
|
1 |
subPila :: Eq a => Pila a -> Pila a -> Bool |
tal que subPila p1 p2 se verifica si p1 es una subpila de p2. Por ejemplo,
|
1 2 3 4 5 6 7 |
λ> ej1 = apila 2 (apila 3 vacia) λ> ej2 = apila 7 (apila 2 (apila 3 (apila 5 vacia))) λ> ej3 = apila 2 (apila 7 (apila 3 (apila 5 vacia))) λ> subPila ej1 ej2 True λ> subPila ej1 ej3 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 45 46 47 48 49 50 51 52 53 54 55 |
import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila) import Transformaciones_pilas_listas (pilaAlista) import PrefijoPila (prefijoPila) import Data.List (isPrefixOf, tails) import Test.QuickCheck -- 1ª solución -- =========== -- Se usará la función PrefijoPila del ejercicio -- "Reconocimiento de prefijos de pilas" que se encuentra en -- https://bit.ly/3Xqu7lo subPila1 :: Eq a => Pila a -> Pila a -> Bool subPila1 p1 p2 | esVacia p1 = True | esVacia p2 = False | cp1 == cp2 = prefijoPila dp1 dp2 || subPila1 p1 dp2 | otherwise = subPila1 p1 dp2 where cp1 = cima p1 dp1 = desapila p1 cp2 = cima p2 dp2 = desapila p2 -- 2ª solución -- =========== -- Se usará la función pilaAlista del ejercicio -- "Transformaciones entre pilas y listas" que se encuentra en -- https://bit.ly/3ZHewQ8 subPila2 :: Eq a => Pila a -> Pila a -> Bool subPila2 p1 p2 = sublista (pilaAlista p1) (pilaAlista p2) -- (sublista xs ys) se verifica si xs es una sublista de ys. Por -- ejemplo, -- sublista [3,2] [5,3,2,7] == True -- sublista [3,2] [5,3,7,2] == False sublista :: Eq a => [a] -> [a] -> Bool sublista xs ys = any (xs `isPrefixOf`) (tails ys) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_subPila :: Pila Int -> Pila Int -> Bool prop_subPila p1 p2 = subPila1 p1 p2 == subPila2 p1 p2 -- La comprobación es -- λ> quickCheck prop_subPila -- +++ 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 |
from copy import deepcopy from typing import TypeVar from hypothesis import given from src.prefijoPila import prefijoPila 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 # =========== # Se usará la función PrefijoPila del ejercicio # "Reconocimiento de prefijos de pilas" que se encuentra en # https://bit.ly/3Xqu7lo def subPila1(p1: Pila[A], p2: Pila[A]) -> bool: if esVacia(p1): return True if esVacia(p2): return False cp1 = cima(p1) dp1 = desapila(p1) cp2 = cima(p2) dp2 = desapila(p2) if cp1 == cp2: return prefijoPila(dp1, dp2) or subPila1(p1, dp2) return subPila1(p1, dp2) # 2ª solución # =========== # Se usará la función pilaAlista del ejercicio # "Transformaciones entre pilas y listas" que se encuentra en # https://bit.ly/3ZHewQ8 # sublista(xs, ys) se verifica si xs es una sublista de ys. Por # ejemplo, # >>> sublista([3,2], [5,3,2,7]) # True # >>> sublista([3,2], [5,3,7,2]) # False def sublista(xs: list[A], ys: list[A]) -> bool: return any(xs == ys[i:i+len(xs)] for i in range(len(ys) - len(xs) + 1)) def subPila2(p1: Pila[A], p2: Pila[A]) -> bool: return sublista(pilaAlista(p1), pilaAlista(p2)) # 3ª solución # =========== def subPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool: if p1.esVacia(): return True if p2.esVacia(): return False if p1.cima() != p2.cima(): p2.desapila() return subPila3Aux(p1, p2) q1 = deepcopy(p1) p1.desapila() p2.desapila() return prefijoPila(p1, p2) or subPila3Aux(q1, p2) def subPila3(p1: Pila[A], p2: Pila[A]) -> bool: q1 = deepcopy(p1) q2 = deepcopy(p2) return subPila3Aux(q1, q2) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(p1=pilaAleatoria(), p2=pilaAleatoria()) def test_subPila(p1: Pila[int], p2: Pila[int]) -> None: r = subPila1(p1, p2) assert subPila2(p1, p2) == r assert subPila3(p1, p2) == r # La comprobación es # src> poetry run pytest -q subPila.py # 1 passed in 0.32s |
La función subPila puede ser implementada utilizando recursión y las funciones exportadas del TAD de las pilas. La idea es ir comparando los elementos de la cima de ambas pilas hasta que una de ellas sea vacía o se encuentre un elemento que no coincide: