Parse XML Tree

에는 이제 Tokenizer가 있으며 반환된 토큰은 XML 태그 또는 콘텐츠입니다. 예를 들어 (open, html)(inner, hello)(close, html)는 <html>hello</html>를 의미하며, 각 괄호와 그 콘텐츠는 토큰입니다. 이 XML 파일을 표현하는 방법입니다.

스택 방식

복잡성

시간 O(N) 공간 O(N)

생각

이 질문은 가장 먼저 명확하게 생각해야 할 것은 XML을 표현하는 방법입니다. XML은 일반적인 단일 부모 다중 자식 모델이므로 이를 표현하기 위해 트리를 사용하는 것이 좋습니다. 그런 다음 Tokenizer 사용 방법을 분석합니다. Tokenizer를 사용하여 토큰을 얻을 때마다 Open Token인 경우 이 새 노드 아래에 새 노드가 있을 수도 있습니다. 내부 토큰인 경우 새 노드도 만들어야 하지만 이 노드 아래에는 새 노드가 없습니다. Close Token인 경우 새 노드가 필요하지 않으며 이전 Open 노드가 더 이상 새 노드를 허용하지 않도록 해야 하며 새 노드는 이전 레이어의 노드에 연결되어야 합니다. 여기서는 스택을 사용하여 이전 레이어의 노드 정보를 유지하여 트리를 구축하는 데 도움을 줍니다. 이것이 오픈 토큰인 경우 새 노드를 생성하여 이전 노드 뒤에 추가하고 스택에 추가해야 합니다. 내부 토큰인 경우 새 노드를 생성하여 이전 노드 뒤에 추가해야 하지만 스택에 추가해서는 안 됩니다. 닫기 토큰인 경우 스택에서 이전 노드를 팝합니다.