c++ - 「ツリー」構造を「宣言的に」生成する方法

Question

「ノード」クラス/構造体を定義し、コードがフォーマットされる方法がツリー構造を反映するように、これらのノードのツリーをコードで宣言し、「多すぎる」定型句がないようにしたい。

これはデータ構造に関する質問ではなく、以下の例と同様のスタイルの宣言型コードに到達するために使用できる 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")
  ]);

注意：やりたくないこと：

一連の一時オブジェクト/coll を宣言し、ツリーを「後方」に構築します

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);

score 2 · Accepted Answer

()ノードを過度にコピーし、角かっこではなく括弧を使用してもかまわない場合は[]、これでうまくいくはずです。

実際には、コピーではなくポインタを格納することでコピーを回避できます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"))
              );
}

score 0 · Accepted Answer

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

この手法を使用すると、次のような構文を取得できます。

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

ここで、オーバーロードoperator,しoperator<<て、ルートノードの構築に使用される式ツリーを構築します。

score 0 · Accepted Answer

使用したい構文のパーサーを作成することは難しくありません。これは単純ですが機能するコードです。オブジェクトを少し変更します。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;
    }

c++ - 「ツリー」構造を「宣言的に」生成する方法

3 に答える 3

Related

Reference