Iterando lo recursivo

Source: Dev.to

Conversión de HTML reducido a Markdown con un árbol sintáctico

En uno de mis proyectos laterales (o “mascota”) escribí un pequeño parser para un HTML reducido, pensado para una aplicación de notas.
El objetivo es que el usuario pueda escribir como en un pequeño procesador de textos y que el resultado se guarde en Markdown.

El soporte de todo esto es JEditorPane, ya que la app está escrita en Java sobre Swing (me gusta mucho C#, pero poder distribuir toda la aplicación en un solo archivo .jar es un puntazo).

---

Entrada HTML de ejemplo

A realizar:

    - Recoger la bici del taller.

    - Dar de comer a las tortugas.

    - Pedir cita para colonoscopia.

Salida Markdown esperada

# Tareas cotidianas

A realizar:

1. Recoger la bici del taller.
2. Dar de comer a las tortugas.
3. Pedir cita para colonoscopia.

Aunque parezca una traducción directa (quizá mediante algún pre‑procesador), los problemas aparecen enseguida si no usamos un parser: necesitamos convertir la entrada HTML en un árbol sintáctico.

---

Árbol sintáctico del ejemplo

Root
|________________________|
p                        ol
|                        |______________________________|________|
"A realizar"             li                             li       li
                         |                              |        |
                         "Recoger la bici del taller." "Dar de comer a las tortugas." "Pedir cita para colonoscopia."

---

Recorrido del árbol para generar Markdown

Una forma de recorrer el árbol es apoyándonos en la recursividad y en el patrón de diseño Visitor.

Clase Tree (recursiva)

class Tree {
    // ...

    public void run(Visitor v) {
        this.runOver(v, this.root);
    }

    private void runOver(Visitor v, Element element) {
        v.visit(element);

        for (Element subElement : element.getSubElements()) {
            this.runOver(v, subElement);
        }
    }
}

Con este método se separa el código que maneja el árbol del que realiza las distintas tareas sobre él.
runOver(v, element) recorre todos los elementos usando una estrategia en profundidad (DFS).

Clase Visitor

class Visitor {
    // ...

    private final StringBuilder text = new StringBuilder();

    public void visit(Element element) {
        String elementText = element.toString();

        if (!elementText.isEmpty()) {
            text.append(elementText);
            text.append('\n');
        }
    }

    public String getResult() {
        return text.toString();
    }
}

Ejecución (representación de la pila de llamadas)

runOver(root, v)
 ├─ runOver(p, v)
 │   └─ runOver(p.get(0), v)
 ├─ runOver(ol, v)
 │   ├─ runOver(ol.get(0), v)
 │   │   └─ runOver(li.get(0), v)
 │   ├─ runOver(ol.get(1), v)
 │   │   └─ runOver(li.get(0), v)
 │   └─ runOver(ol.get(2), v)
 │       └─ runOver(li.get(0), v)

Salida obtenida

A realizar:
Recoger la bici del taller.
Dar de comer a las tortugas.
Pedir cita para colonoscopia.

---

Desventajas de la recursividad

1. Comprensión – Al principio cuesta pensar y entender código que se llama a sí mismo.
2. Rendimiento – Cada llamada recursiva ocupa una posición en la pila de llamadas.
   Si el árbol tiene, por ejemplo, 100 niveles de profundidad, se reservarán 100 entradas en el stack, lo que puede provocar un StackOverflowError.

---

Enfoque iterativo (uso de una cola)

Para evitar los problemas anteriores, podemos sustituir la pila de llamadas implícita por una colección explícita.
En lugar de una pila (que requeriría insertar los sub‑elementos en orden inverso), utilizaremos una cola (ArrayDeque), que mantiene el orden natural de los nodos.

Clase Tree (iterativa)

class Tree {
    // ...

    public void run(Visitor v) {
        Deque<Element> elements = new ArrayDeque<>();
        elements.add(this.getRoot());          // se inserta la raíz

        while (!elements.isEmpty()) {
            Element element = elements.removeFirst(); // se saca del frente
            v.visit(element);                         // se procesa

            // se añaden los sub‑elementos al final de la cola
            for (Element sub : element.getSubElements()) {
                elements.addLast(sub);
            }
        }
    }
}

Con este bucle while la aplicación recorre el árbol en anchura (BFS) sin necesidad de llamadas recursivas, eliminando el riesgo de desbordar la pila.

---

Resumen

• Parser → HTML reducido → árbol sintáctico.
• Visitor → recorre el árbol y genera texto Markdown.
• Recursivo → sencillo pero puede desbordar la pila.
• Iterativo (cola) → evita el desbordamiento y mantiene el orden natural de los nodos.

Con este enfoque la aplicación de notas puede aceptar HTML sencillo, convertirlo a un árbol interno y producir Markdown de forma segura y eficiente.

t = elements.peek();

elements.remove();
elements.addAll(element.getSubElements());

v.visit(element);
}

Ejemplo paso a paso (nota de tareas)

1. Primera vuelta – introducimos la raíz, se elimina y se introducen sus sub‑elementos.

   • elementos → [ p, ol ]
   • text → ""

2. Segundo paso – se procesa p, cuyo único subnodo es el texto “A realizar.”.

   • elementos → [ ol, "A realizar." ]
   • text → ""

3. Siguiente paso – se añaden los hijos de ol.

   • elementos → [ "A realizar.", li, li, li ]
   • text → ""

4. Toma del primer elemento – contiene texto, se añade al StringBuilder.

   • elementos → [ li, li, li ]
   • text → "A realizar.\n"

5. Añadir sub‑elementos – se procesa el primer li.

   • elementos → [ li, li, "Recoger la bici del taller." ]
   • text → "A realizar.\n"

6. Repetir – se procesa el siguiente li.

   • elementos → [ li, "Recoger la bici del taller.", "Dar de comer a las tortugas." ]
   • text → "A realizar.\n"

7. Una vez más – se procesa el último li.

   • elementos → [ "Recoger la bici del taller.", "Dar de comer a las tortugas.", "Pedir cita para colonoscopia." ]
   • text → "A realizar.\n"

8. Añadir los textos restantes – los textos ya no tienen sub‑elementos, se añaden directamente.

   • elementos → [ "Dar de comer a las tortugas.", "Pedir cita para colonoscopia." ]
   • text → "A realizar.\nRecoger la bici del taller.\n"

9. Continuamos –

   • elementos → [ "Pedir cita para colonoscopia." ]
   • text → "A realizar.\nRecoger la bici del taller.\nDar de comer a las tortugas.\n"

10. Finalizamos – la cola queda vacía.

    • elementos → []
    • text → "A realizar.\nRecoger la bici del taller.\nDar de comer a las tortugas.\nPedir cita para colonoscopia.\n"

¡Hurra! Nuestro código se ejecuta sin necesidad de preocuparnos de si la complejidad de nuestro árbol puede o no desbordar el stack. Además, al efectuar menos llamadas a funciones, será más rápido.

A cambio, eso sí, empleamos más memoria (la de la cola elementos). ¡Siempre tendremos que cambiar rendimiento por memoria y viceversa!