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

Aplicacions de les Piles

Següent ►
►

Ja tens la pila implementada i mesurada. Aquesta lliçó la posa a treballar en quatre aplicacions reals, desenvolupades amb codi complet: el desfer/refer definitiu de TaskFlow (amb dues piles cooperant), la validació de parèntesis i claudàtors balancejats (que farem servir per als filtres de cerca de TaskFlow), l'avaluació d'expressions postfixes amb la seva conversió des de notació infixa (una calculadora d'estimacions), i la pila de crides de Python, que explica per què una recursió massa profunda rebenta amb RecursionError. Són els quatre usos clàssics de les piles, els que trobaràs en entrevistes tècniques i en codi de producció, i tots comparteixen un mateix patró mental: "el pendent més recent es resol primer". Farem servir la classe Pila de la lliçó anterior en tots els exemples.

Contingut

  1. Desfer/refer complet amb dues piles
  2. Parèntesis balancejats: validar els filtres de TaskFlow
  3. Expressions postfixes: avaluació i conversió des d'infixa
  4. La pila de crides i la recursió

Desfer/refer complet amb dues piles

HistorialAccions (lliçó 03-03) desfà, però no perdona: si l'usuari desfà per error, l'acció es perd. Tot programari seriós ofereix refer (Ctrl+Y / Ctrl+Maj+Z). La solució clàssica fa servir dues piles cooperant:

  • Pila desfer: les accions realitzades i vigents.
  • Pila refer: les accions que l'usuari ha desfet (i podria voler recuperar).

Les regles del ball són tres:

L'usuari... Pila desfer Pila refer
Fa una acció nova push(accio) Es buida
Prem Desfer pop() → es reverteix push(accio)
Prem Refer push(accio) pop() → es reaplica

Desfer i refer es passen accions l'una a l'altra, com dues mans. La regla subtil —i la que més s'oblida— és la primera: una acció nova invalida el refer. Si després de desfer "canviar prioritat" l'usuari edita el títol, ja no té sentit "refer el canvi de prioritat" sobre un estat que ha divergit: el refer s'ha de buidar.

flowchart LR
    U["Accio nova"] -->|push| D["Pila DESFER"]
    U -.->|buida| R["Pila REFER"]
    D -->|"Desfer: pop"| R
    R -->|"Refer: pop"| D

La implementació, sobre la Pila de 03-03 i les accions {"tipus", "tasca", "dades_previes"}. La novetat és que cada acció guarda ara també dades_noves, perquè refer necessita reaplicar el valor nou (desfer restaura el previ; refer restaura el nou):

class GestorDesferRefer:
    """Desfer/refer de TaskFlow amb dues piles cooperant."""

    def __init__(self, tasques):
        self._tasques = tasques          # el tauler: dict de tasques per id
        self._desfer = Pila()
        self._refer = Pila()

    def executar(self, tipus, tasca_id, dades_noves):
        """Registra i aplica una accio nova de l'usuari."""
        tasca = self._tasques[tasca_id]
        # 1. Capturar els valors previs ABANS de modificar (patro de 03-03)
        dades_previes = {camp: tasca[camp] for camp in dades_noves}
        # 2. Aplicar el canvi
        tasca.update(dades_noves)
        # 3. Registrar l'accio completa (amb el previ I el nou)
        self._desfer.push({"tipus": tipus, "tasca": tasca_id,
                           "dades_previes": dades_previes,
                           "dades_noves": dades_noves})
        # 4. Una accio nova invalida tot el refer
        self._refer = Pila()

    def desfer(self):
        if self._desfer.esta_buida():
            return "Res a desfer"
        accio = self._desfer.pop()
        self._tasques[accio["tasca"]].update(accio["dades_previes"])
        self._refer.push(accio)          # l'accio passa a l'altra pila
        return f"Desfet: {accio['tipus']} (tasca {accio['tasca']})"

    def refer(self):
        if self._refer.esta_buida():
            return "Res a refer"
        accio = self._refer.pop()
        self._tasques[accio["tasca"]].update(accio["dades_noves"])
        self._desfer.push(accio)         # i torna a la pila de desfer
        return f"Refet: {accio['tipus']} (tasca {accio['tasca']})"

Sessió completa sobre la tasca 7:

tasques = {7: {"id": 7, "titol": "Revisar el pressupost", "prioritat": 2,
               "estat": "pendent"}}
gestor = GestorDesferRefer(tasques)

gestor.executar("canviar_prioritat", 7, {"prioritat": 1})
gestor.executar("canviar_estat", 7, {"estat": "en curs"})
print(tasques[7]["prioritat"], tasques[7]["estat"])   # 1 en curs

print(gestor.desfer())            # Desfet: canviar_estat (tasca 7)
print(tasques[7]["estat"])        # pendent

print(gestor.refer())             # Refet: canviar_estat (tasca 7)
print(tasques[7]["estat"])        # en curs

gestor.desfer()                   # desfa l'estat una altra vegada
gestor.executar("assignar", 7, {"assignada_a": "anna"})   # accio nova!
print(gestor.refer())             # Res a refer  <- el refer s'ha invalidat

Observa l'última línia: hi havia una acció esperant a refer, però l'assignació a l'Anna la va invalidar. Aquesta és la regla 1 en acció, i és exactament com es comporta el teu editor de text.

Et recorda alguna cosa? Al mòdul 2, HistorialTasques resolia "enrere/endavant" amb una llista doblement enllaçada i un cursor. Són dues solucions al mateix problema de navegació bidireccional: la llista doble manté tot l'historial i mou un cursor (ideal quan avançar no invalida res, com visitar tasques); les dues piles descarten el futur quan el present canvia (ideal per editar, on les branques mortes no han de sobreviure). Triar entre totes dues és triar la semàntica correcta, no l'estructura "millor".

Parèntesis balancejats: validar els filtres de TaskFlow

TaskFlow vol permetre filtres de cerca avançats escrits per l'usuari:

(prioritat:1 OR prioritat:2) AND [estat:pendent OR {assignada_a:anna}]

Abans d'interpretar un filtre cal validar que els seus parèntesis (), claudàtors [] i claus {} estan balancejats: cada obertura té el seu tancament, del tipus correcte i en l'ordre correcte. (a[b)c] està malament encara que hi hagi tants tancaments com obertures: es creuen.

Per què una pila? Perquè en trobar un tancament, ha de casar amb l'obertura pendent més recent: LIFO pur.

L'algorisme:

  1. Recorre la cadena caràcter a caràcter.
  2. Si és una obertura ((, [, {) → push.
  3. Si és un tancament (), ], }) → la pila no pot estar buida i el seu cim ha de ser l'obertura parella; pop i comprova.
  4. En acabar, la pila ha de quedar buida (sense obertures òrfenes).
PARELLES = {")": "(", "]": "[", "}": "{"}

def filtre_balancejat(filtre):
    """Comprova que (), [] i {} del filtre estan correctament balancejats."""
    pila = Pila()
    for caracter in filtre:
        if caracter in "([{":
            pila.push(caracter)                  # obertura: queda pendent
        elif caracter in ")]}":
            if pila.esta_buida():
                return False                     # tancament sense obertura pendent
            if pila.pop() != PARELLES[caracter]:
                return False                     # tancament de tipus equivocat
        # qualsevol altre caracter (lletres, espais, ':') no afecta el balanc
    return pila.esta_buida()                     # sense obertures sense tancar

Explicació dels tres modes de fallada, amb la traça de l'exemple creuat (a[b)c]:

Caràcter Acció Pila (cim a la dreta) Resultat
( push (
a ignorar (
[ push (, [
b ignorar (, [
) pop → surt [, esperava ( False: tancament equivocat
  • Tancament amb pila buida ("tasca)"): un ) sense cap ( pendent.
  • Tancament de tipus equivocat ("(a[b)c]"): el més interessant — hi ha obertures pendents, però la més recent no és la parella.
  • Pila no buida al final ("(pendent"): obertures que mai no es van tancar.
print(filtre_balancejat("(prioritat:1 OR prioritat:2) AND [estat:pendent]"))  # True
print(filtre_balancejat("(a[b)c]"))     # False
print(filtre_balancejat("(pendent"))    # False
print(filtre_balancejat(""))            # True (res a balancejar)

Cost: O(n) en temps (una passada per la cadena, operacions de pila O(1)) i O(n) en espai en el pitjor cas (tot obertures). Aquest algorisme, tal qual, és el que fan servir editors i IDE per pintar-te el parèntesi sense parella en vermell.

Expressions postfixes: avaluació i conversió des d'infixa

TaskFlow vol una minicalculadora d'estimacions: l'usuari escriu (3 + 5) * 2 (hores de tres subtasques...) i l'aplicació ho avalua. Avaluar notació infixa (l'operador entre operands) és incòmode: exigeix prioritats (* abans que +) i parèntesis. Els compiladors ho resolen en dues fases, totes dues amb piles:

  1. Convertir l'expressió infixa a postfixa (notació polonesa inversa: l'operador després dels seus operands): (3 + 5) * 2 → 3 5 + 2 *.
  2. Avaluar la postfixa, que ja no necessita ni prioritats ni parèntesis.

Avaluar postfixa (una pila d'operands)

Regla: recorre els tokens; si és un número, push; si és un operador, pop dos operands, opera i push el resultat. Al final queda exactament un valor: el resultat.

def avaluar_postfixa(expressio):
    """Avalua una expressio postfixa amb tokens separats per espais."""
    pila = Pila()
    for token in expressio.split():
        if token in "+-*/":
            b = pila.pop()                   # compte amb l'ordre!
            a = pila.pop()                   # a va arribar abans que b
            if token == "+":   pila.push(a + b)
            elif token == "-": pila.push(a - b)
            elif token == "*": pila.push(a * b)
            elif token == "/": pila.push(a / b)
        else:
            pila.push(float(token))          # operand: a la pila
    return pila.pop()                        # l'unic valor restant

print(avaluar_postfixa("3 5 + 2 *"))    # 16.0  ==  (3 + 5) * 2
print(avaluar_postfixa("3 5 2 * +"))    # 13.0  ==  3 + 5 * 2

Traça de 3 5 + 2 *:

Token Acció Pila (cim a la dreta)
3 push 3 3
5 push 5 3, 5
+ pop 5 i 3 → push 8 8
2 push 2 8, 2
* pop 2 i 8 → push 16 16

El detall que causa el 90 % dels bugs: l'ordre dels pops. El primer pop retorna l'operand dret (b), el segon l'esquerre (a). Amb + i * tant se val (commutatives); amb - i / et canvia el resultat: 6 2 / ha de ser 6 / 2 = 3, no 2 / 6.

Convertir infixa → postfixa (una pila d'operadors)

L'algorisme shunting-yard de Dijkstra, en la seva versió essencial. Els números surten directament a la sortida; els operadors esperen en una pila fins que n'arriba un de prioritat menor o igual (o un tancament de parèntesi) que els obliga a sortir:

PRIORITAT = {"+": 1, "-": 1, "*": 2, "/": 2}

def infixa_a_postfixa(expressio):
    sortida = []
    pila = Pila()                            # pila d'operadors en espera
    for token in expressio.split():
        if token in PRIORITAT:               # es un operador
            # Desallotjar operadors de prioritat major o igual: van abans
            while (not pila.esta_buida() and pila.peek() != "("
                   and PRIORITAT.get(pila.peek(), 0) >= PRIORITAT[token]):
                sortida.append(pila.pop())
            pila.push(token)
        elif token == "(":
            pila.push(token)                 # marca l'inici d'un grup
        elif token == ")":
            while pila.peek() != "(":        # desallotjar fins a l'obertura
                sortida.append(pila.pop())
            pila.pop()                       # descartar el '(' (no surt)
        else:
            sortida.append(token)            # operand: directe a la sortida
    while not pila.esta_buida():
        sortida.append(pila.pop())           # desallotjar el que queda pendent
    return " ".join(sortida)

print(infixa_a_postfixa("( 3 + 5 ) * 2"))   # 3 5 + 2 *
print(infixa_a_postfixa("3 + 5 * 2"))       # 3 5 2 * +
print(avaluar_postfixa(infixa_a_postfixa("( 3 + 5 ) * 2")))  # 16.0

Fixa't en l'ús de peek que vam anunciar a 03-02: el while de desallotjament consulta el cim per decidir si desapilar — mirar abans d'actuar. I al segon exemple, observa com la pila reté el + mentre processa 5 * 2: la prioritat dels operadors es resol sola gràcies a l'ordre LIFO. (La nostra versió exigeix tokens separats per espais i no gestiona operadors unaris ni potències: suficient per a les estimacions de TaskFlow; l'algorisme complet és una extensió directa.)

La pila de crides i la recursió

La pila més important de totes és una que no has creat tu: la pila de crides (call stack). Cada vegada que Python entra en una funció, apila un marc (frame) amb les seves variables locals i el punt de retorn; quan la funció retorna, el desapila. Observa-la en viu:

def a():
    print("entro dins de a")
    b()
    print("surto de a")     # s'executa DESPRES que b acabi

def b():
    print("  entro dins de b")
    c()
    print("  surto de b")

def c():
    print("    entro dins de c")
    print("    surto de c")

a()
entro dins de a
  entro dins de b
    entro dins de c
    surto de c
  surto de b
surto de a

Les entrades passen en ordre a→b→c, però les sortides en ordre invers c→b→a: l'última funció a entrar és la primera a sortir. LIFO pur; per això l'estructura que ho sosté és una pila. Quan un error no es captura, Python t'imprimeix aquesta pila — el traceback és, literalment, un bolcat de la pila de crides, del fons (a) al cim (c).

Per què una recursió profunda rebenta

Una funció recursiva s'apila a si mateixa una vegada per nivell. Sumar els ids d'una cadena de tasques enllaçades, recursivament:

def sumar_ids(node):
    if node is None:                 # cas base: cadena esgotada
        return 0
    return node.dada["id"] + sumar_ids(node.seguent)   # un marc per node

Amb 100 tasques, perfecte: 100 marcs apilats i desapilats. Amb 100 000 tasques:

RecursionError: maximum recursion depth exceeded

La pila de crides té un límit (per defecte, uns 1000 marcs a CPython — consulta'l amb sys.getrecursionlimit()): protegeix la memòria del procés de recursions desbocades. La conclusió pràctica:

  • Recursió: elegant per a profunditats petites o acotades (arbres equilibrats, dividir i vèncer).
  • Iteració amb pila explícita: quan la profunditat pot ser gran, substitueix la pila de crides (limitada, implícita) per una Pila teva (tan gran com la teva memòria, explícita). Tota recursió es pot reescriure així, i és un exercici central de la propera lliçó.

Aquest duet recursió/pila explícita reapareixerà amb força: els recorreguts d'arbres (mòdul 6) i la cerca en profunditat (DFS) de grafs (mòdul 7) són exactament això — de fet, "DFS iteratiu" no és res més que canviar la pila de crides per una pila explícita. Aquí ho deixem anunciat.

Errors Comuns i Consells

  • Oblidar buidar la pila de refer en executar una acció nova: el bug clàssic del desfer/refer; produeix "refers" que apliquen canvis sobre un estat que ja no existeix, corrompent dades. La regla és innegociable.
  • Guardar només dades_previes quan hi ha refer: desfer necessita el previ, refer necessita el nou. Sense dades_noves, el refer no sap què reaplicar.
  • En el balanceig, comprovar només el recompte: "tres obertures i tres tancaments" no n'hi ha prou ()a( o (a[b)c] fallen). Cal casar tipus i ordre: per això cal la pila i no un comptador.
  • Oblidar l'esta_buida() final o inicial en el balanceig: sense la comprovació final, "(pendent" passaria; sense la inicial davant d'un tancament, ")" llançaria IndexError en comptes de retornar False.
  • Invertir els operands en - i /: el primer pop és l'operand dret. Grava-t'ho: b = pop(); a = pop(); a - b.
  • "Arreglar" un RecursionError pujant el límit amb sys.setrecursionlimit: gairebé sempre és amagar el problema (i arriscar-te a tombar el procés sencer). La solució robusta és iterar amb pila explícita.

Exercicis

Exercici 1: desfer múltiple

Afegeix a GestorDesferRefer un mètode desfer_diverses(n) que desfaci fins a n accions de cop (la interfície de TaskFlow tindrà un menú "desfer les últimes 5"). Ha de retornar la llista de missatges de cada desfer efectiu i aturar-se sense error si l'historial s'esgota abans. Pregunta extra: després de desfer_diverses(3), què ha de contenir la pila de refer i en quin ordre, perquè tres refer() seguits ho restaurin tot correctament?

Exercici 2: balanceig amb posició de l'error

Millora filtre_balancejat perquè, en comptes de False, retorni la posició (índex) del caràcter que trenca el balanç, o -1 si el filtre és vàlid. Per a obertures sense tancar, retorna la posició de l'obertura òrfena més interna (pista: apila tuples (caracter, index)).

Exercici 3: avaluar una estimació infixa completa

Combina les dues funcions de la secció 3 en estimar(expressio_infixa) que validi primer el balanceig de parèntesis (amb filtre_balancejat), llanci ValueError("expressio mal balancejada") si falla, i si no, converteixi i avaluï. Prova-la amb "( 3 + 5 ) * 2" i "( 3 + 5 * 2".

Solucions

Solució 1:

def desfer_diverses(self, n):
    missatges = []
    for _ in range(n):
        if self._desfer.esta_buida():        # historial esgotat: parar sense error
            break
        missatges.append(self.desfer())      # reutilitza tota la logica existent
    return missatges

Reutilitzar self.desfer() garanteix que cada pas mou l'acció a la pila de refer. Pregunta extra: si es desfan les accions A3, A2, A1 (en aquest ordre, de la més recent a la més antiga), la pila de refer queda amb A1 al cim i A3 al fons. Així, el primer refer() reaplica A1, després A2, després A3: exactament l'ordre cronològic original. Les dues piles inverteixen l'ordre dues vegades, i dues inversions restauren l'ordre — un patró que reapareix a l'exercici d'invertir de 03-05.

Solució 2:

def filtre_balancejat_pos(filtre):
    pila = Pila()                            # apilem (caracter, index)
    for i, caracter in enumerate(filtre):
        if caracter in "([{":
            pila.push((caracter, i))
        elif caracter in ")]}":
            if pila.esta_buida():
                return i                     # tancament sense obertura: culpable aqui
            obertura, _ = pila.pop()
            if obertura != PARELLES[caracter]:
                return i                     # tancament de tipus equivocat
    if not pila.esta_buida():
        _, index = pila.pop()                # l'obertura orfena mes interna
        return index
    return -1

print(filtre_balancejat_pos("(a[b)c]"))     # 4  (el ')' que no casa)
print(filtre_balancejat_pos("(pendent"))    # 0  (el '(' mai tancat)
print(filtre_balancejat_pos("(ok)[si]"))    # -1

La clau és enriquir el que s'apila: en comptes del caràcter sol, una tupla amb el seu índex. L'estructura de l'algorisme no canvia — un altre avantatge de raonar amb el contracte: la pila no exigeix que els seus elements siguin de cap tipus concret.

Solució 3:

def estimar(expressio_infixa):
    if not filtre_balancejat(expressio_infixa):
        raise ValueError("expressio mal balancejada")
    postfixa = infixa_a_postfixa(expressio_infixa)
    return avaluar_postfixa(postfixa)

print(estimar("( 3 + 5 ) * 2"))   # 16.0
print(estimar("( 3 + 5 * 2"))     # ValueError: expressio mal balancejada

Validar abans de convertir evita que infixa_a_postfixa falli amb un IndexError críptic en buscar un ( que no existeix: l'usuari de TaskFlow rep un error de domini comprensible, no un traceback d'estructura interna. Tres algorismes de pila encadenats en cinc línies.

Conclusió

Has vist la pila desplegada en els seus quatre papers estel·lars: dues piles cooperant donen a TaskFlow un desfer/refer professional (amb la regla d'or d'invalidar el refer davant d'accions noves, i el seu contrast amb l'HistorialTasques de llista doble del mòdul 2); una pila d'obertures pendents valida el balanceig dels filtres de cerca casant cada tancament amb l'obertura més recent; una pila d'operands i una altra d'operadors avaluen i tradueixen expressions aritmètiques resolent les prioritats per pur ordre LIFO; i la pila de crides de Python sosté cada funció que executes, amb el seu límit de profunditat com a causa del RecursionError — i la pila explícita com a cura, que als mòduls 6 i 7 es convertirà en recorreguts d'arbres i DFS. El patró comú: el pendent més recent es resol primer. Només queda consolidar: la propera lliçó és íntegrament d'exercicis, on invertiràs seqüències, construiràs una pila amb mínim en O(1), validaràs seqüències d'operacions i convertiràs recursions en iteracions. Sense teoria nova: pura pràctica.

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