使用std :: initializer_list创建树？

Question

我所拥有的是:

struct ExprTreeNode {
   char c;
   std::vector< int > i;
};

ExprTreeNode tn { '+', { 1, 2, 3, 4 } };

我想写的是:

MyTree t1 { '+', { 1, 2, { '*', { 3, 4, 5 } } } };
MyTree t2 { '*', { { '+', { 77, 88, 99, 111 } }, { '-', { 44, 33 } } } };

我可以自由地定义MyTree类(以及可能的帮助程序类) - 但它应该是tree-ish - 类似于TreeNode内容的运算符和包含子节点的容器(例如std :: vector).

在C++中是否可以使用这样的initializer_list来初始化树状结构？(如果可能的话,提示如何做到这一点会很好.)

Answer 1

以下可能适合您:

struct ExprTreeNode {
    bool is_value;
    int i;
    char c;
    std::vector< ExprTreeNode > v;

    ExprTreeNode( int i_ ) : is_value( true ), i( i_ ) {}
    ExprTreeNode( char c_, std::initializer_list< ExprTreeNode > v_ )
      : is_value( false ), c( c_ ), v( v_ ) {}
};

ExprTreeNode tn { '+', { 1, 2, { '*', { 3, 4 } } } };

(实际上,你可能要合并i和c)

这是一个实例.

更新:正如在我使用类似技术的另一个Q/A中指出的那样,上面是未定义的行为,因为我std::vector<ExprTreeNode>作为成员使用,此时,ExprTreeNode它不是一个完整的类型.以下应该解决它:

struct ExprTreeNode {
    int value_;
    char op_;
    std::shared_ptr< void > subnodes_;

    ExprTreeNode( int v ) : value_( v ) {}
    ExprTreeNode( char op, std::initializer_list< ExprTreeNode > subnodes );

    void print() const;
};

typedef std::vector< ExprTreeNode > Nodes;

ExprTreeNode::ExprTreeNode( char op, std::initializer_list< ExprTreeNode > l )
  : op_(op), subnodes_(std::make_shared<Nodes>(l))
{}

这shared_ptr也使用了作为leaf/non-leaf的标志,如果你想使用它,你需要先抛出它:

void ExprTreeNode::print() const
{
   if( !subnodes_ ) {
      std::cout << value_;
   }
   else {
      std::cout << op_ << " ( ";
      for( const auto& e : *std::static_pointer_cast<Nodes>(subnodes_) ) {
         e.print(); std::cout << " ";
      }
      std::cout << ")";
   }
}

这是更新的实例.