如何填充'Tree'结构'Declaratively'

Question

我想定义一个"node"类/结构，然后在代码中声明这些节点的树，使代码的格式反映树结构，并且没有"太多"的样板。

请注意，这不是关于数据结构的问题，而是关于我可以使用哪些C++功能来获得与以下示例类似的声明性代码样式的问题。

可能使用 C++0X 会更容易，因为它在构造对象和集合方面具有更多功能，但我使用的是 Visual Studio 2008。

示例树节点类型：

struct node
{ 
  string name;
  node* children;
  node(const char* name, node* children);
  node(const char* name);
};

我想做什么：

声明树，使其结构反映在源代码中

node root =
  node("foo",
  [
    node("child1"),
    node("child2", 
    [
      node("grand_child1"),
      node("grand_child2"),
      node("grand_child3"
    ]),
    node("child3")
  ]);

注意：我不想做的：

声明一大堆临时对象/集合并"向后"构造树

node grandkids[] = node[3] 
{
  node("grand_child1"),
  node("grand_child2"),
  node("grand_child3"
};
node kids[] = node[3]
{
  node("child1"),
  node("child2", grandkids) 
  node("child3")
};
node root = node("foo", kids);

Answer 1

如果您不介意过度复制节点并使用括号()而不是方括号[]那么这应该可以工作。

实际上，您可以通过在node_group中存储指针而不是副本来避免复制，但是由于这是星期五下午，而且我很懒，所以我会把它留给你。

struct node
{
    std::string name;
    std::vector<node> children;
    node(const char* n)
        :   name (n)
    {
    }
    node(const char* n, const class node_group& group);
};
struct node_group
{
    std::vector<node> children;
};
node::node(const char* n, const class node_group& group)
    :   name (n)
    ,   children (group.children)
{
}
node_group operator ,(const node& n1, const node& n2)
{
    node_group group;
    group.children.push_back (n1);
    group.children.push_back (n2);
    return group;
}
node_group operator ,(const node_group& gr, const node& n2)
{
    node_group group (gr);
    group.children.push_back (n2);
    return group;
}

int main ()
{
    node root ("foo",
                (node("child1"),
                node("child2",
                    (node("grand_child1"),
                    node("grand_child2"),
                    node("grand_child3"))
                    ),
                node("child3"))
              );
}

Answer 2

> http://en.wikipedia.org/wiki/Expression_templates

使用此技术，您可以获得如下语法：

Node root("bob") =
  (node("child1")
    <<(
      node("grandkid"),
      node("grandkid2")
    )
  ),
  node("child2");

重载operator,并operator<<构建用于构造根节点的表达式树。

Answer 3

为要使用的语法编写解析器并不难。这是一个简单但有效的代码。我让自己稍微更改一下您的node对象，它不使用指针数组来存储子对象，而是std::vector

这种方法的优点是您可以从运行时提供的文本构造树，例如从配置文件中读取。另请注意，ostream& operator<<(ostream&, const node&)以相同的格式打印树，这对于序列化树（将它们写入文件或通过网络发送）或单元测试非常方便。

    #include <stdio.h>
    #include <stdlib.h>
    #include <ctype.h>
    #include <string>
    #include <vector>
    #include <iostream>

    using namespace std;
    struct node
    { 
      string name;
      vector<node*> children;
      node(const string& name, const vector<node*> children);
      node(const string& name);
    };
    ostream& operator<<(ostream& o, const node& n) {
        o << "node('" << n.name << "'";
        if (n.children.size()) {
            o << ", [";
            for (size_t i = 0; i < n.children.size(); ++i)
                o << (i ? "," : "") << *(n.children[i]);
            o << "]";
        }
        o << ")";
        return o;
    }
    node::node(const string& s, const vector<node*> children)
    : name(s), children(children) {}
    char* parseNode(node** n, const char *ss);
    char *skipSpace(const char *ss) {
        char *s = (char *) ss;
        while (isspace(*s))
            ++s;
        return s;
    }
    void expected_error(const char* s) { 
        fprintf(stderr, "Error: expected '%s'n", s);
        exit(1);
    }
    char *expect(const char *expected, char *s) {
        char *ex = skipSpace(expected);
        s = skipSpace(s);
        for ( ; *ex && *s; ++ex, ++s)
            if (*ex != *s) expected_error(expected);
        if (*ex) expected_error(expected);
        return s;
    }
    char *expectString(string& str, const char *ss)
    {
        char *s = skipSpace(ss);
        s = expect("'", s);
        char *start = s++;
        while (*s != ''')
            ++s;
        str = string(start, s - start);
        return ++s;
    }
    char * parseChildren(vector<node*>& children, char *s) {
        s = expect("[", s);
        s = skipSpace(s);
        while (*s != ']') {
            node *n = 0;
            s = parseNode(&n, s);
            children.push_back(n);
            s = skipSpace(s);
            if (*s == ',')
                ++s;
            else break;
        }
        s = expect("]", s);
        return s;
    }
    char* parseNode(node** n, const char *ss) {
        char *s = (char *) ss;
        s = expect("node", s);
        s = expect("(", s);
        string name;
        s = expectString(name, s);
        vector<node*> children;
        s = skipSpace(s);
        if (*s == ',') 
            s = parseChildren(children, ++s);
        *n = new node(name, children);
        s = expect(")", s);
        return s;
    }
    int main()
    {
        node * n = 0;
        parseNode(&n,
    " node('foo',"
    "  ["
    "    node('child1'),"
    "    node('child2', "
    "    ["
    "     node('grand_child1'),"
    "     node('grand_child2'),"
    "     node('grand_child3')"
    "    ]),"
    "   node('child3')"
    " ])"
    );
        cout << *n;
        return 0;
    }