Menu Close

Etiqueta: TDA

TAD de las pilas: Máximo elemento de una pila

José A. Alonso, ,

Utilizando el tipo abstracto de datos de las pilas, definir la función

   maxPila :: Ord a => Pila a -> a

tal que maxPila p sea el mayor de los elementos de la pila p. Por ejemplo,

   λ> maxPila (apila 3 (apila 5 (apila 1 vacia)))
   5

Soluciones

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


Soluciones en Haskell

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)
import Transformaciones_pilas_listas (pilaAlista)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
maxPila1 :: Ord a => Pila a -> a
maxPila1 p
  | esVacia dp = cp
  | otherwise  = max cp (maxPila1 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
 
maxPila2 :: Ord a => Pila a -> a
maxPila2 =
  maximum . pilaAlista
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_maxPila :: Pila Int -> Property
prop_maxPila p =
  not (esVacia p) ==> maxPila1 p == maxPila2 p
 
-- La comprobación es
--    λ> quickCheck prop_maxPila
--    +++ OK, passed 100 tests; 17 discarded.


Soluciones en Python

from copy import deepcopy
from typing import TypeVar
 
from hypothesis import assume, 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 maxPila1(p: Pila[A]) -> A:
    cp = cima(p)
    dp = desapila(p)
    if esVacia(dp):
        return cp
    return max(cp, maxPila1(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 maxPila2(p: Pila[A]) -> A:
    return max(pilaAlista(p))
 
# 3ª solución
# ===========
 
def maxPila3Aux(p: Pila[A]) -> A:
    cp = p.cima()
    p.desapila()
    if esVacia(p):
        return cp
    return max(cp, maxPila3Aux(p))
 
def maxPila3(p: Pila[A]) -> A:
    q = deepcopy(p)
    return maxPila3Aux(q)
 
# 4ª solución
# ===========
 
def maxPila4Aux(p: Pila[A]) -> A:
    r = p.cima()
    while not esVacia(p):
        cp = p.cima()
        if cp > r:
            r = cp
        p.desapila()
    return r
 
def maxPila4(p: Pila[A]) -> A:
    q = deepcopy(p)
    return maxPila4Aux(q)
 
# Comprobación de equivalencia de las definiciones
# ================================================
 
# La propiedad es
@given(p=pilaAleatoria())
def test_maxPila(p: Pila[int]) -> None:
    assume(not esVacia(p))
    r = maxPila1(p)
    assert maxPila2(p) == r
    assert maxPila3(p) == r
    assert maxPila4(p) == r
 
# La comprobación es
#    src> poetry run pytest -q maxPila.py
#    1 passed in 0.25s
Leer más →

TAD de las pilas: Pertenencia a una pila

José A. Alonso, ,

Utilizando el tipo abstracto de datos de las pilas, definir la función

   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,

   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.


Soluciones en Haskell

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.


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)
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
Leer más →