解析文本以创建树数据结构 [英] Parsing Text to Make a Tree Data Structure
问题描述
假设我正在从文件中读取一行:
Let's say I'm reading a line from a file:
{Parent{{ChildA}{ChildB}}}
更复杂的示例:
{Parent{{ChildA{ChildC}{ChildD}}{ChildB{ChildE}{ChildF}}}}
这是用于构建树的语法。
Which is the grammar used to construct a tree.
{}
括号是一个节点,如果在那个括号中有其他节点(括号),那些节点是子节点。
Any name inside {}
brackets is a node, and if within that bracket there are other nodes (brackets), those nodes are children.
我能够解析第一个具体示例使用计数器,但只能找到节点的文本名称。我如何解析这个,以便我可以确定什么节点是彼此的孩子?我似乎无法围绕我将使用的代码。我有一个感觉,我会使用递归。
I'm able to parse the first specific example using a counter, but only to find the text names of the nodes. How can I parse this so that I can determine what nodes are children of one another? I can't seem to wrap my mind around the code I would use. I have a feeling I would use recursion.
任何帮助或建议将不胜感激。
Any help or advice would be appreciated.
非常感谢。
推荐答案
使用Boost Spirit Qi的最小实现:
A minimal implementation with 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);
}
这篇关于解析文本以创建树数据结构的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!