c++ - 解析文本以创建树状数据结构

Question

假设我正在从文件中读取一行:

{Parent{{ChildA}{ChildB}}}

更复杂的例子:

{Parent{{ChildA{ChildC}{ChildD}}{ChildB{ChildE}{ChildF}}}}

这是用来构造树的语法。

{} 括号内的任何名称都是一个节点，如果该括号内还有其他节点(括号)，则这些节点是子节点。

我能够使用计数器解析第一个具体示例，但只能找到节点的文本名称。我如何解析它以便确定哪些节点是彼此的子节点？我似乎无法全神贯注于我将使用的代码。我感觉我会使用递归。

如有任何帮助或建议，我们将不胜感激。

首选 C++。

非常感谢。

Answer 1

您必须跟踪当前的嵌套。为此，您可以使用堆栈。

每次遇到{(后跟节点名)，就知道这是一个新节点的开始。这个新节点是当前节点的子节点。

每次你遇到，你就知道当前节点现在已经完成了，这意味着你必须告诉你的程序当前节点现在已经变成了当前节点的父节点。

例子:

{A{B{C}{D}{E}}{F{G}{H}}}  Stack:
^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A // A is root
 ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B // B is child of A
   ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, C // C is child of B
     ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, // C has no child, C done
      ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, D // D is child of B
        ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, 
         ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, E // E child of B
           ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, 
            ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, // B has no more children, B done
             ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, F // F child of A
               ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, F, G // G child of F
                 ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, F, 
                  ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, F, H
                    ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, F, 
                     ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, 
                      ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: 
                       ^

DONE.