El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Aplicaciones de las Pilas

Siguiente ►
►

Ya tienes la pila implementada y medida. Esta lección la pone a trabajar en cuatro aplicaciones reales, desarrolladas con código completo: el deshacer/rehacer definitivo de TaskFlow (con dos pilas cooperando), la validación de paréntesis y corchetes balanceados (que usaremos para los filtros de búsqueda de TaskFlow), la evaluación de expresiones postfijas con su conversión desde notación infija (una calculadora de estimaciones), y la pila de llamadas de Python, que explica por qué una recursión demasiado profunda revienta con RecursionError. Son los cuatro usos clásicos de las pilas, los que encontrarás en entrevistas técnicas y en código de producción, y todos comparten un mismo patrón mental: "lo pendiente más reciente se resuelve primero". Usaremos la clase Pila de la lección anterior en todos los ejemplos.

Contenido

  1. Deshacer/rehacer completo con dos pilas
  2. Paréntesis balanceados: validar los filtros de TaskFlow
  3. Expresiones postfijas: evaluación y conversión desde infija
  4. La pila de llamadas y la recursión

Deshacer/rehacer completo con dos pilas

HistorialAcciones (lección 03-03) deshace, pero no perdona: si el usuario deshace por error, la acción se pierde. Todo software serio ofrece rehacer (Ctrl+Y / Ctrl+Mayús+Z). La solución clásica usa dos pilas cooperando:

  • Pila deshacer: las acciones realizadas y vigentes.
  • Pila rehacer: las acciones que el usuario ha deshecho (y podría querer recuperar).

Las reglas del baile son tres:

El usuario... Pila deshacer Pila rehacer
Hace una acción nueva push(accion) Se vacía
Pulsa Deshacer pop() → se revierte push(accion)
Pulsa Rehacer push(accion) pop() → se reaplica

Deshacer y rehacer se pasan acciones la una a la otra, como dos manos. La regla sutil —y la que más se olvida— es la primera: una acción nueva invalida el rehacer. Si tras deshacer "cambiar prioridad" el usuario edita el título, ya no tiene sentido "rehacer el cambio de prioridad" sobre un estado que ha divergido: el rehacer debe vaciarse.

flowchart LR
    U["Acción nueva"] -->|push| D["Pila DESHACER"]
    U -.->|vacía| R["Pila REHACER"]
    D -->|"Deshacer: pop"| R
    R -->|"Rehacer: pop"| D

La implementación, sobre la Pila de 03-03 y las acciones {"tipo", "tarea", "datos_previos"}. La novedad es que cada acción guarda ahora también datos_nuevos, porque rehacer necesita reaplicar el valor nuevo (deshacer restaura lo previo; rehacer restaura lo nuevo):

class GestorDeshacerRehacer:
    """Deshacer/rehacer de TaskFlow con dos pilas cooperando."""

    def __init__(self, tareas):
        self._tareas = tareas            # el tablero: dict de tareas por id
        self._deshacer = Pila()
        self._rehacer = Pila()

    def ejecutar(self, tipo, tarea_id, datos_nuevos):
        """Registra y aplica una acción nueva del usuario."""
        tarea = self._tareas[tarea_id]
        # 1. Capturar los valores previos ANTES de modificar (patrón de 03-03)
        datos_previos = {campo: tarea[campo] for campo in datos_nuevos}
        # 2. Aplicar el cambio
        tarea.update(datos_nuevos)
        # 3. Registrar la acción completa (con lo previo Y lo nuevo)
        self._deshacer.push({"tipo": tipo, "tarea": tarea_id,
                             "datos_previos": datos_previos,
                             "datos_nuevos": datos_nuevos})
        # 4. Una acción nueva invalida todo el rehacer
        self._rehacer = Pila()

    def deshacer(self):
        if self._deshacer.esta_vacia():
            return "Nada que deshacer"
        accion = self._deshacer.pop()
        self._tareas[accion["tarea"]].update(accion["datos_previos"])
        self._rehacer.push(accion)       # la acción pasa a la otra pila
        return f"Deshecho: {accion['tipo']} (tarea {accion['tarea']})"

    def rehacer(self):
        if self._rehacer.esta_vacia():
            return "Nada que rehacer"
        accion = self._rehacer.pop()
        self._tareas[accion["tarea"]].update(accion["datos_nuevos"])
        self._deshacer.push(accion)      # y vuelve a la pila de deshacer
        return f"Rehecho: {accion['tipo']} (tarea {accion['tarea']})"

Sesión completa sobre la tarea 7:

tareas = {7: {"id": 7, "titulo": "Revisar presupuesto", "prioridad": 2,
              "estado": "pendiente"}}
gestor = GestorDeshacerRehacer(tareas)

gestor.ejecutar("cambiar_prioridad", 7, {"prioridad": 1})
gestor.ejecutar("cambiar_estado", 7, {"estado": "en_curso"})
print(tareas[7]["prioridad"], tareas[7]["estado"])   # 1 en_curso

print(gestor.deshacer())          # Deshecho: cambiar_estado (tarea 7)
print(tareas[7]["estado"])        # pendiente

print(gestor.rehacer())           # Rehecho: cambiar_estado (tarea 7)
print(tareas[7]["estado"])        # en_curso

gestor.deshacer()                 # deshace el estado otra vez
gestor.ejecutar("asignar", 7, {"asignada_a": "ana"})   # ¡acción nueva!
print(gestor.rehacer())           # Nada que rehacer  <- el rehacer se invalidó

Observa la última línea: había una acción esperando en rehacer, pero la asignación a Ana la invalidó. Esa es la regla 1 en acción, y es exactamente como se comporta tu editor de texto.

¿Te recuerda a algo? En el módulo 2, HistorialTareas resolvía "atrás/adelante" con una lista doblemente enlazada y un cursor. Son dos soluciones al mismo problema de navegación bidireccional: la lista doble mantiene todo el historial y mueve un cursor (ideal cuando avanzar no invalida nada, como visitar tareas); las dos pilas descartan el futuro cuando el presente cambia (ideal para editar, donde las ramas muertas no deben sobrevivir). Elegir entre ambas es elegir la semántica correcta, no la estructura "mejor".

Paréntesis balanceados: validar los filtros de TaskFlow

TaskFlow quiere permitir filtros de búsqueda avanzados escritos por el usuario:

(prioridad:1 OR prioridad:2) AND [estado:pendiente OR {asignada_a:ana}]

Antes de interpretar un filtro hay que validar que sus paréntesis (), corchetes [] y llaves {} están balanceados: cada apertura tiene su cierre, del tipo correcto y en el orden correcto. (a[b)c] está mal aunque haya tantos cierres como aperturas: se cruzan.

¿Por qué una pila? Porque al encontrar un cierre, debe casar con la apertura pendiente más reciente: LIFO puro.

El algoritmo:

  1. Recorre la cadena carácter a carácter.
  2. Si es una apertura ((, [, {) → push.
  3. Si es un cierre (), ], }) → la pila no puede estar vacía y su cima debe ser la apertura pareja; pop y comprueba.
  4. Al terminar, la pila debe quedar vacía (sin aperturas huérfanas).
PAREJAS = {")": "(", "]": "[", "}": "{"}

def filtro_balanceado(filtro):
    """Comprueba que (), [] y {} del filtro están correctamente balanceados."""
    pila = Pila()
    for caracter in filtro:
        if caracter in "([{":
            pila.push(caracter)                  # apertura: queda pendiente
        elif caracter in ")]}":
            if pila.esta_vacia():
                return False                     # cierre sin apertura pendiente
            if pila.pop() != PAREJAS[caracter]:
                return False                     # cierre de tipo equivocado
        # cualquier otro carácter (letras, espacios, ':') no afecta al balance
    return pila.esta_vacia()                     # sin aperturas sin cerrar

Explicación de los tres modos de fallo, con la traza del ejemplo cruzado (a[b)c]:

Carácter Acción Pila (cima a la derecha) Resultado
( push (
a ignorar (
[ push (, [
b ignorar (, [
) pop → sale [, esperaba ( False: cierre equivocado
  • Cierre con pila vacía ("tarea)"): un ) sin ningún ( pendiente.
  • Cierre de tipo equivocado ("(a[b)c]"): el más interesante — hay aperturas pendientes, pero la más reciente no es la pareja.
  • Pila no vacía al final ("(pendiente"): aperturas que nunca se cerraron.
print(filtro_balanceado("(prioridad:1 OR prioridad:2) AND [estado:pendiente]"))  # True
print(filtro_balanceado("(a[b)c]"))       # False
print(filtro_balanceado("(pendiente"))    # False
print(filtro_balanceado(""))              # True (nada que balancear)

Coste: O(n) en tiempo (un pase por la cadena, operaciones de pila O(1)) y O(n) en espacio en el peor caso (todo aperturas). Este algoritmo, tal cual, es el que usan editores e IDEs para pintarte el paréntesis sin pareja en rojo.

Expresiones postfijas: evaluación y conversión desde infija

TaskFlow quiere una mini-calculadora de estimaciones: el usuario escribe (3 + 5) * 2 (horas de tres subtareas...) y la aplicación lo evalúa. Evaluar notación infija (el operador entre operandos) es incómodo: exige prioridades (* antes que +) y paréntesis. Los compiladores lo resuelven en dos fases, ambas con pilas:

  1. Convertir la expresión infija a postfija (notación polaca inversa: el operador después de sus operandos): (3 + 5) * 2 → 3 5 + 2 *.
  2. Evaluar la postfija, que ya no necesita ni prioridades ni paréntesis.

Evaluar postfija (una pila de operandos)

Regla: recorre los tokens; si es número, push; si es operador, pop dos operandos, opera y push el resultado. Al final queda exactamente un valor: el resultado.

def evaluar_postfija(expresion):
    """Evalúa una expresión postfija con tokens separados por espacios."""
    pila = Pila()
    for token in expresion.split():
        if token in "+-*/":
            b = pila.pop()                   # ¡ojo al orden!
            a = pila.pop()                   # a llegó antes 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))          # operando: a la pila
    return pila.pop()                        # el único valor restante

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

Traza de 3 5 + 2 *:

Token Acción Pila (cima a la derecha)
3 push 3 3
5 push 5 3, 5
+ pop 5 y 3 → push 8 8
2 push 2 8, 2
* pop 2 y 8 → push 16 16

El detalle que causa el 90 % de los bugs: el orden de los pops. El primer pop devuelve el operando derecho (b), el segundo el izquierdo (a). Con + y * da igual (conmutativas); con - y / te cambia el resultado: 6 2 / debe ser 6 / 2 = 3, no 2 / 6.

Convertir infija → postfija (una pila de operadores)

El algoritmo shunting-yard de Dijkstra, en su versión esencial. Los números salen directamente a la salida; los operadores esperan en una pila hasta que llega uno de menor o igual prioridad (o un cierre de paréntesis) que los obliga a salir:

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

def infija_a_postfija(expresion):
    salida = []
    pila = Pila()                            # pila de operadores en espera
    for token in expresion.split():
        if token in PRIORIDAD:               # es un operador
            # Desalojar operadores de prioridad mayor o igual: van antes
            while (not pila.esta_vacia() and pila.peek() != "("
                   and PRIORIDAD.get(pila.peek(), 0) >= PRIORIDAD[token]):
                salida.append(pila.pop())
            pila.push(token)
        elif token == "(":
            pila.push(token)                 # marca el inicio de un grupo
        elif token == ")":
            while pila.peek() != "(":        # desalojar hasta la apertura
                salida.append(pila.pop())
            pila.pop()                       # descartar el '(' (no sale)
        else:
            salida.append(token)             # operando: directo a la salida
    while not pila.esta_vacia():
        salida.append(pila.pop())            # desalojar lo pendiente
    return " ".join(salida)

print(infija_a_postfija("( 3 + 5 ) * 2"))   # 3 5 + 2 *
print(infija_a_postfija("3 + 5 * 2"))       # 3 5 2 * +
print(evaluar_postfija(infija_a_postfija("( 3 + 5 ) * 2")))  # 16.0

Fíjate en el uso de peek que anunciamos en 03-02: el while de desalojo consulta la cima para decidir si desapilar — mirar antes de actuar. Y en el segundo ejemplo, observa cómo la pila retiene el + mientras procesa 5 * 2: la prioridad de los operadores se resuelve sola gracias al orden LIFO. (Nuestra versión exige tokens separados por espacios y no maneja operadores unarios ni potencias: suficiente para las estimaciones de TaskFlow; el algoritmo completo es una extensión directa.)

La pila de llamadas y la recursión

La pila más importante de todas es una que no has creado tú: la pila de llamadas (call stack). Cada vez que Python entra en una función, apila un marco (frame) con sus variables locales y el punto de retorno; cuando la función devuelve, lo desapila. Obsérvala en vivo:

def a():
    print("entro en a")
    b()
    print("salgo de a")     # se ejecuta DESPUÉS de que b termine

def b():
    print("  entro en b")
    c()
    print("  salgo de b")

def c():
    print("    entro en c")
    print("    salgo de c")

a()
entro en a
  entro en b
    entro en c
    salgo de c
  salgo de b
salgo de a

Las entradas ocurren en orden a→b→c, pero las salidas en orden inverso c→b→a: la última función en entrar es la primera en salir. LIFO puro; por eso la estructura que lo sostiene es una pila. Cuando un error no se captura, Python te imprime esa pila — el traceback es, literalmente, un volcado de la pila de llamadas, del fondo (a) a la cima (c).

Por qué una recursión profunda revienta

Una función recursiva se apila a sí misma una vez por nivel. Sumar los ids de una cadena de tareas enlazadas, recursivamente:

def sumar_ids(nodo):
    if nodo is None:                 # caso base: cadena agotada
        return 0
    return nodo.dato["id"] + sumar_ids(nodo.siguiente)   # un marco por nodo

Con 100 tareas, perfecto: 100 marcos apilados y desapilados. Con 100 000 tareas:

RecursionError: maximum recursion depth exceeded

La pila de llamadas tiene un límite (por defecto, unos 1000 marcos en CPython — consúltalo con sys.getrecursionlimit()): protege la memoria del proceso de recursiones desbocadas. La conclusión práctica:

  • Recursión: elegante para profundidades pequeñas o acotadas (árboles equilibrados, divide y vencerás).
  • Iteración con pila explícita: cuando la profundidad puede ser grande, sustituye la pila de llamadas (limitada, implícita) por una Pila tuya (tan grande como tu memoria, explícita). Toda recursión puede reescribirse así, y es un ejercicio central de la próxima lección.

Este dúo recursión/pila explícita reaparecerá con fuerza: los recorridos de árboles (módulo 6) y la búsqueda en profundidad (DFS) de grafos (módulo 7) son exactamente esto — de hecho, "DFS iterativo" no es más que cambiar la pila de llamadas por una pila explícita. Aquí lo dejamos anunciado.

Errores Comunes y Consejos

  • Olvidar vaciar la pila de rehacer al ejecutar una acción nueva: el bug clásico del deshacer/rehacer; produce "rehaceres" que aplican cambios sobre un estado que ya no existe, corrompiendo datos. La regla es innegociable.
  • Guardar solo datos_previos cuando hay rehacer: deshacer necesita lo previo, rehacer necesita lo nuevo. Sin datos_nuevos, el rehacer no sabe qué reaplicar.
  • En el balanceo, comprobar solo el recuento: "tres aperturas y tres cierres" no basta ()a( o (a[b)c] fallan). Hay que casar tipo y orden: por eso hace falta la pila y no un contador.
  • Olvidar el esta_vacia() final o inicial en el balanceo: sin la comprobación final, "(pendiente" pasaría; sin la inicial ante un cierre, ")" lanzaría IndexError en vez de devolver False.
  • Invertir los operandos en - y /: el primer pop es el operando derecho. Grábatelo: b = pop(); a = pop(); a - b.
  • "Arreglar" un RecursionError subiendo el límite con sys.setrecursionlimit: casi siempre es esconder el problema (y arriesgarte a tirar el proceso entero). La solución robusta es iterar con pila explícita.

Ejercicios

Ejercicio 1: deshacer múltiple

Añade a GestorDeshacerRehacer un método deshacer_varias(n) que deshaga hasta n acciones de golpe (la interfaz de TaskFlow tendrá un menú "deshacer las últimas 5"). Debe devolver la lista de mensajes de cada deshacer efectivo y detenerse sin error si el historial se agota antes. Pregunta extra: tras deshacer_varias(3), ¿qué debe contener la pila de rehacer y en qué orden, para que tres rehacer() seguidos restauren todo correctamente?

Ejercicio 2: balanceo con posición del error

Mejora filtro_balanceado para que, en lugar de False, devuelva la posición (índice) del carácter que rompe el balance, o -1 si el filtro es válido. Para aperturas sin cerrar, devuelve la posición de la apertura huérfana más interna (pista: apila tuplas (caracter, indice)).

Ejercicio 3: evaluar una estimación infija completa

Combina las dos funciones de la sección 3 en estimar(expresion_infija) que valide primero el balanceo de paréntesis (con filtro_balanceado), lance ValueError("expresión mal balanceada") si falla, y si no, convierta y evalúe. Pruébala con "( 3 + 5 ) * 2" y "( 3 + 5 * 2".

Soluciones

Solución 1:

def deshacer_varias(self, n):
    mensajes = []
    for _ in range(n):
        if self._deshacer.esta_vacia():      # historial agotado: parar sin error
            break
        mensajes.append(self.deshacer())     # reutiliza toda la lógica existente
    return mensajes

Reutilizar self.deshacer() garantiza que cada paso mueve la acción a la pila de rehacer. Pregunta extra: si se deshacen las acciones A3, A2, A1 (en ese orden, de la más reciente a la más antigua), la pila de rehacer queda con A1 en la cima y A3 al fondo. Así, el primer rehacer() reaplica A1, luego A2, luego A3: exactamente el orden cronológico original. Las dos pilas invierten el orden dos veces, y dos inversiones restauran el orden — un patrón que reaparece en el ejercicio de invertir de 03-05.

Solución 2:

def filtro_balanceado_pos(filtro):
    pila = Pila()                            # apilamos (caracter, indice)
    for i, caracter in enumerate(filtro):
        if caracter in "([{":
            pila.push((caracter, i))
        elif caracter in ")]}":
            if pila.esta_vacia():
                return i                     # cierre sin apertura: culpable aquí
            apertura, _ = pila.pop()
            if apertura != PAREJAS[caracter]:
                return i                     # cierre de tipo equivocado
    if not pila.esta_vacia():
        _, indice = pila.pop()               # la apertura huérfana más interna
        return indice
    return -1

print(filtro_balanceado_pos("(a[b)c]"))     # 4  (el ')' que no casa)
print(filtro_balanceado_pos("(pendiente"))  # 0  (el '(' nunca cerrado)
print(filtro_balanceado_pos("(ok)[si]"))    # -1

La clave es enriquecer lo que se apila: en vez del carácter solo, una tupla con su índice. La estructura del algoritmo no cambia — otra ventaja de razonar con el contrato: la pila no exige que sus elementos sean de ningún tipo concreto.

Solución 3:

def estimar(expresion_infija):
    if not filtro_balanceado(expresion_infija):
        raise ValueError("expresión mal balanceada")
    postfija = infija_a_postfija(expresion_infija)
    return evaluar_postfija(postfija)

print(estimar("( 3 + 5 ) * 2"))   # 16.0
print(estimar("( 3 + 5 * 2"))     # ValueError: expresión mal balanceada

Validar antes de convertir evita que infija_a_postfija falle con un IndexError críptico al buscar un ( que no existe: el usuario de TaskFlow recibe un error de dominio comprensible, no un traceback de estructura interna. Tres algoritmos de pila encadenados en cinco líneas.

Conclusión

Has visto la pila desplegada en sus cuatro papeles estelares: dos pilas cooperando dan a TaskFlow un deshacer/rehacer profesional (con la regla de oro de invalidar el rehacer ante acciones nuevas, y su contraste con el HistorialTareas de lista doble del módulo 2); una pila de aperturas pendientes valida el balanceo de los filtros de búsqueda casando cada cierre con la apertura más reciente; una pila de operandos y otra de operadores evalúan y traducen expresiones aritméticas resolviendo las prioridades por puro orden LIFO; y la pila de llamadas de Python sostiene cada función que ejecutas, con su límite de profundidad como causa del RecursionError — y la pila explícita como cura, que en los módulos 6 y 7 se convertirá en recorridos de árboles y DFS. El patrón común: lo pendiente más reciente se resuelve primero. Solo queda consolidar: la próxima lección es íntegramente de ejercicios, donde invertirás secuencias, construirás una pila con mínimo en O(1), validarás secuencias de operaciones y convertirás recursiones en iteraciones. Sin teoría nueva: pura práctica.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados