재귀를 반복하기

Source: Dev.to

축소된 HTML을 구문 트리와 함께 Markdown으로 변환

내 사이드 프로젝트(또는 “펫” 프로젝트) 중 하나에서, 메모 애플리케이션을 위해 설계된 축소된 HTML용 작은 parser를 작성했습니다.
목표는 사용자가 작은 워드 프로세서처럼 글을 작성하고 그 결과가 Markdown으로 저장되도록 하는 것입니다.

이 모든 것을 지원하는 것은 JEditorPane이며, 앱은 Swing 기반 Java로 작성되었습니다 (C#를 매우 좋아하지만, 전체 애플리케이션을 하나의 .jar 파일로 배포할 수 있다는 점이 큰 장점입니다).

---

예시 HTML 입력

A realizar:

    - Recoger la bici del taller.

    - Dar de comer a las tortugas.

    - Pedir cita para colonoscopia.

예상 Markdown 출력

# Tareas cotidianas

A realizar:

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

직접 번역(아마도 사전 처리기 사용)처럼 보일 수 있지만, parser를 사용하지 않으면 즉시 문제가 발생합니다: 입력 HTML을 구문 트리로 변환해야 합니다.

예시 구문 트리

Root
|________________________|
p                        ol
|                        |______________________________|________|
"실행할 작업"            li                             li       li
                         |                              |        |
                         "바이크를 정비소에서 가져오기." "거북이에게 먹이 주기." "대장내시경 예약하기."

Markdown 생성을 위한 트리 순회

트리를 순회하는 한 방법은 재귀와 디자인 패턴 Visitor를 활용하는 것입니다.

Tree 클래스 (재귀적)

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);
        }
    }
}

이 메서드를 사용하면 트리를 관리하는 코드와 트리 위에서 다양한 작업을 수행하는 코드를 분리할 수 있습니다.
runOver(v, element)는 깊이 우선(DFS) 전략을 사용하여 모든 요소를 순회합니다.

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();
    }
}

실행 (호출 스택 표시)

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)

얻은 출력

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

재귀의 단점

1. 이해 – 처음에는 자신을 호출하는 코드를 생각하고 이해하는 것이 어렵다.
2. 성능 – 각 재귀 호출은 호출 스택에 하나의 위치를 차지한다.
   예를 들어 트리의 깊이가 100레벨이라면 스택에 100개의 엔트리가 예약되어 StackOverflowError가 발생할 수 있다.

---

반복적 접근 (큐 사용)

이전 문제들을 피하기 위해, 암시적인 호출 스택을 명시적인 컬렉션으로 대체할 수 있습니다.
스택 대신 (하위 요소들을 역순으로 삽입해야 하는) 큐(ArrayDeque)를 사용하면 노드의 자연스러운 순서를 유지할 수 있습니다.

Tree 클래스 (반복형)

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);
            }
        }
    }
}

이 while 루프를 사용하면 애플리케이션이 재귀 호출 없이 너비 우선(BFS) 방식으로 트리를 순회하므로 스택 오버플로 위험을 없앨 수 있습니다.

요약

• Parser → 축소된 HTML → 구문 트리.
• Visitor → 트리를 순회하고 Markdown 텍스트를 생성합니다.
• 재귀 → 간단하지만 스택 오버플로우가 발생할 수 있습니다.
• 반복 (큐) → 오버플로우를 방지하고 노드의 자연스러운 순서를 유지합니다.

이 접근법을 사용하면 메모 앱이 간단한 HTML을 받아 내부 트리로 변환하고 안전하고 효율적으로 Markdown을 생성할 수 있습니다.

t = elements.peek();

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

v.visit(element);
}

단계별 예시 (작업 노트)

1. 첫 번째 순환 – 루트를 삽입하고, 제거한 뒤 그 하위 요소들을 삽입합니다.

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

2. 두 번째 단계 – p를 처리합니다. 그 유일한 하위 노드는 텍스트 **“A realizar.”**입니다.

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

3. 다음 단계 – ol의 자식들을 추가합니다.

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

4. 첫 번째 요소를 가져오기 – 텍스트가 포함되어 있어 StringBuilder에 추가됩니다.

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

5. 하위 요소 추가 – 첫 번째 li를 처리합니다.

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

6. 반복 – 다음 li를 처리합니다.

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

7. 다시 한 번 – 마지막 li를 처리합니다.

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

8. 남은 텍스트 추가 – 텍스트에 더 이상 하위 요소가 없으므로 바로 추가합니다.

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

9. 계속 진행 –

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

10. 마무리 – 큐가 비게 됩니다.

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

만세! 우리 코드는 트리 복잡도가 스택 오버플로우를 일으킬지 여부를 신경 쓸 필요 없이 실행됩니다. 또한 함수 호출을 줄여 더 빠르게 동작합니다.

그 대신, 우리는 더 많은 메모리(큐 elementos의 메모리)를 사용합니다. 성능과 메모리는 언제나 트레이드오프 관계입니다!