解析文本以创建树数据结构

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.

Answer 2

如果是家庭作业，你无论如何都无法使用答案，从而破坏了乐趣：

Boost Spirit Qi 的最小实现：

#include <boost/spirit/include/qi.hpp>
namespace qi = boost::spirit::qi;

typedef boost::make_recursive_variant<
    std::vector<boost::recursive_variant_>, 
    std::string>::type ast_t;

void dump(const ast_t&);

// adhoc parser rule:
static const qi::rule<std::string::iterator, ast_t()> node = 
    '{' >> *node >> '}' | +~qi::char_("{}");

int main()
{
     std::string input = "{Parent{{ChildA{ChildC}{ChildD}}{ChildB{ChildE}{ChildF}}}}";
     std::string::iterator f(input.begin()), l(input.end());

     ast_t tree;
     if (qi::parse(f, l, node, tree))
         dump(tree);
     else
         std::cerr << "Unparsed: " << std::string(f, l) << std::endl;
}

遗憾的是，实现的dump代码量几乎相同:)

它将打印：

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

_{这是 的定义dump(const ast_t&)：}

struct dump_visitor : boost::static_visitor<>
{
    dump_visitor(int indent=0) : _indent(indent) {}

    void operator()(const std::string& s) const { print(s); }

    template <class V>
        void operator()(const V& vec) const
    {
        print("{");
        for(typename V::const_iterator it=vec.begin(); it!=vec.end(); it++)
            boost::apply_visitor(dump_visitor(_indent+1), *it);
        print("}");
    }

  private:
    template <typename T> void print(const T& v) const 
      { std::cout << std::string(_indent*4, ' ') << v << std::endl; }
    int _indent;
};

void dump(const ast_t& tree)
{
    boost::apply_visitor(dump_visitor(), tree);
}