El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Exercicis amb Piles

Següent ►
►

En aquesta secció, posarem en pràctica els conceptes apresos sobre les piles. Els exercicis estan dissenyats per reforçar la comprensió de les operacions bàsiques, la implementació i les aplicacions de les piles.

Exercici 1: Implementació Bàsica d'una Pila

Descripció

Implementa una pila utilitzant una llista en Python. La pila ha de tenir les operacions bàsiques: push, pop, peek i is_empty.

Requisits

  1. La funció push ha d'afegir un element al cim de la pila.
  2. La funció pop ha d'eliminar i retornar l'element del cim de la pila.
  3. La funció peek ha de retornar l'element del cim de la pila sense eliminar-lo.
  4. La funció is_empty ha de retornar True si la pila està buida i False en cas contrari.

Solució

class Pila:
    def __init__(self):
        self.elements = []

    def push(self, element):
        self.elements.append(element)

    def pop(self):
        if not self.is_empty():
            return self.elements.pop()
        else:
            return None

    def peek(self):
        if not self.is_empty():
            return self.elements[-1]
        else:
            return None

    def is_empty(self):
        return len(self.elements) == 0

# Exemple d'ús
pila = Pila()
pila.push(10)
pila.push(20)
print(pila.peek())  # Output: 20
print(pila.pop())   # Output: 20
print(pila.is_empty())  # Output: False
print(pila.pop())   # Output: 10
print(pila.is_empty())  # Output: True

Explicació

  • __init__: Inicialitza una llista buida per emmagatzemar els elements de la pila.
  • push: Afegeix un element al final de la llista.
  • pop: Elimina i retorna l'últim element de la llista si la pila no està buida.
  • peek: Retorna l'últim element de la llista sense eliminar-lo.
  • is_empty: Comprova si la llista està buida.

Exercici 2: Verificació de Parentesis

Descripció

Escriu una funció que verifiqui si els parèntesis en una expressió estan ben equilibrats. Utilitza una pila per resoldre aquest problema.

Requisits

  1. La funció ha de rebre una cadena que conté parèntesis (), claudàtors [] i claus {}.
  2. La funció ha de retornar True si els parèntesis estan ben equilibrats i False en cas contrari.

Solució

def estan_equilibrats(expressio):
    pila = Pila()
    parells = {')': '(', ']': '[', '}': '{'}
    
    for char in expressio:
        if char in parells.values():
            pila.push(char)
        elif char in parells.keys():
            if pila.is_empty() or pila.pop() != parells[char]:
                return False
    
    return pila.is_empty()

# Exemple d'ús
print(estan_equilibrats("()[]{}"))  # Output: True
print(estan_equilibrats("([{}])"))  # Output: True
print(estan_equilibrats("([)]"))    # Output: False
print(estan_equilibrats("((()))"))  # Output: True

Explicació

  • estan_equilibrats: La funció recorre cada caràcter de l'expressió.
    • Si el caràcter és un parèntesi obert, es posa a la pila.
    • Si és un parèntesi tancat, es comprova si la pila està buida o si el parèntesi obert corresponent no coincideix amb el parèntesi tancat actual.
    • Finalment, es comprova si la pila està buida per assegurar-se que tots els parèntesis estan equilibrats.

Exercici 3: Inversió d'una Cadena

Descripció

Escriu una funció que inverteixi una cadena utilitzant una pila.

Requisits

  1. La funció ha de rebre una cadena com a entrada.
  2. La funció ha de retornar la cadena invertida.

Solució

def invertir_cadena(cadena):
    pila = Pila()
    
    for char in cadena:
        pila.push(char)
    
    cadena_invertida = ""
    while not pila.is_empty():
        cadena_invertida += pila.pop()
    
    return cadena_invertida

# Exemple d'ús
print(invertir_cadena("Hola, món!"))  # Output: "!nóm ,aloH"

Explicació

  • invertir_cadena: La funció posa cada caràcter de la cadena a la pila.
    • Després, es treuen els caràcters de la pila un per un i es concatenen per formar la cadena invertida.

Conclusió

Aquests exercicis han demostrat com utilitzar les piles per resoldre problemes comuns en programació. Hem implementat una pila bàsica, verificat l'equilibri de parèntesis en una expressió i invertit una cadena. Practicar aquests exercicis ajudarà a consolidar la comprensió de les piles i les seves aplicacions.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats