### Need Root of Tree

This code works, but I need a function to locate the root of the tree (exp).
Any help would be greatly appreciated.

NodeExpression.h

#ifndef NODEEXPRESSION_H
#define NODEEXPRESSION_H

class NodeExpression
{
public:
// Pure virtual method declaration
virtual double evaluate() = 0; // Must provide concrete version
NodeExpression();
};

class NodeOperand : public NodeExpression
{
public:
NodeOperand( double );
double evaluate();

private:
double value;
};

class NodeOperator : public NodeExpression
{
public:

protected:
NodeExpression* left; // left subtree
NodeExpression* right; // right subtree
};

{
public:
double evaluate();
};

class NodeSubtract : public NodeOperator
{
public:
NodeSubtract::NodeSubtract( NodeExpression* lt, NodeExpression* rt );
double evaluate();
};

class NodeMultiply : public NodeOperator
{
public:
NodeMultiply::NodeMultiply( NodeExpression* lt, NodeExpression* rt );
double evaluate();
};

class NodeDivide : public NodeOperator
{
public:
NodeDivide::NodeDivide( NodeExpression* lt, NodeExpression* rt );
double evaluate();
};

#endif

NodeExpression.cpp

// NodeExpression class
#include <iostream>
#include "NodeExpression.h"

using namespace std;

NodeExpression::NodeExpression()
{
}

double NodeExpression::evaluate()
{
throw logic_error( "NodeExpression::evaluate() must be overridden." );
}

NodeOperand::NodeOperand( double d )
{
value = d;
}

double NodeOperand::evaluate()
{
return value;
}

{
left = lt;
right = rt;
}

{
return ( left->evaluate() + right->evaluate() );
}

NodeSubtract::NodeSubtract( NodeExpression* lt, NodeExpression* rt )
{
left = lt;
right = rt;
}

double NodeSubtract::evaluate()
{
return ( left->evaluate() - right->evaluate() );
}

NodeMultiply::NodeMultiply( NodeExpression* lt, NodeExpression* rt )
{
left = lt;
right = rt;
}

double NodeMultiply::evaluate()
{
return ( left->evaluate() * right->evaluate() );
}

NodeDivide::NodeDivide( NodeExpression* lt, NodeExpression* rt )
{
// Define the left and right nodes
left = lt;
right = rt;
}

double NodeDivide::evaluate()
{
return ( left->evaluate() / right->evaluate() );
}

#include <iostream>
#include "NodeExpression.h"

using namespace std;

// TestTree.cpp
int main()
{
NodeExpression* exp;
NodeOperand* nodeA = new NodeOperand( 2 );
NodeOperand* nodeB = new NodeOperand( -8 );

exp = new NodeAdd( nodeA, nodeB );

cout << exp->evaluate() << endl;

new NodeMultiply(
new NodeOperand( 3.0 ),
new NodeOperand( 2.0 )
),
new NodeMultiply(
new NodeOperand( 2.0 ),
new NodeSubtract(
new NodeOperand( 5.0 ),
new NodeOperand( 2.0 )
)
)
);

cout << exp->evaluate() << endl;
}
... typically the root of a tree is known as the entry point, you should have stored it somewhere as you built the tree?
It may be a good idea to provide a surrogate class with which expressions can be used like simple value types.
(Users need not be aware of a hierarchy of classes, dynamically allocated objects, building the expression tree etc.)

This example is adapted from: Chapter 5 5. Surrogate Classes
'Ruminations on C++: A Decade of Programming Insight and Experience' by Koenig and Moo

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107`` ``````#include #include /////////////////// begin interpreter //////////////////////// struct abstract_expression { using pointer = std::shared_ptr ; // optional, since all objects in this hierarchy are accessed via shared pointers virtual ~abstract_expression() = default ; virtual double evaluate() const = 0 ; }; struct number : abstract_expression { explicit number( double value ) : value(value) {} virtual double evaluate() const override { return value ; } const double value ; }; struct binary_expression : abstract_expression { binary_expression( const pointer& first, const pointer& second ) : first(first), second(second) { /* if( first == nullptr || second == nullptr ) thoow .... */ } protected: pointer first ; protected: pointer second ; }; struct plus : binary_expression { using binary_expression::binary_expression ; virtual double evaluate() const override { return first->evaluate() + second->evaluate() ; } }; struct minus : binary_expression { using binary_expression::binary_expression ; virtual double evaluate() const override { return first->evaluate() - second->evaluate() ; } }; struct multiply : binary_expression { using binary_expression::binary_expression ; virtual double evaluate() const override { return first->evaluate() * second->evaluate() ; } }; struct divide : binary_expression { using binary_expression::binary_expression ; virtual double evaluate() const override { // note: may result in Nan or +- inf return first->evaluate() / second->evaluate() ; } }; /////////////////// end interpreter //////////////////////// ////////////////// begin facade /////////////////////////////// // collapses the entire hierarchy into a single surrogate type // users do not need to deal with pointers or worry about dynamic storage duration // expressions can be created by using overloaded operators on values // could use pure value semantics (clone instead of sharing with shared pointer); // however this could be somewhat expensive, particularly for common sub-expressions struct expression { expression( double dbl ) : expr( std::make_shared(dbl) ) {} double evaluate() const { return expr->evaluate() ; } friend expression operator+ ( const expression& a, const expression& b ) { return expression( std::make_shared( a.expr, b.expr ) ) ; } friend expression operator- ( const expression& a, const expression& b ) { return expression( std::make_shared( a.expr, b.expr ) ) ; } friend expression operator* ( const expression& a, const expression& b ) { return expression( std::make_shared( a.expr, b.expr ) ) ; } friend expression operator/ ( const expression& a, const expression& b ) { return expression( std::make_shared( a.expr, b.expr ) ) ; } friend std::ostream& operator<< ( std::ostream& stm, const expression& expr ) { return stm << expr.evaluate() ; } private: abstract_expression::pointer expr ; expression( abstract_expression::pointer expr ) : expr(expr) {} }; // and for good measure, provide a user defined literal expression operator "" _X( long double v ) { return expression(v) ; } ////////////////// end facade /////////////////////////////// int main() { const expression e1 = 138.5_X * 4.7 + 99.8 ; std::cout << std::fixed << e1 << '\n' ; const expression e2 = e1 / ( 4.2_X + 5.8 ) - 50 ; std::cout << e2 << '\n' ; std::cout << (e1+e2) * (e1-e2) << ' ' << e1*e1 - e2*e2 << '\n' ; }``````

http://coliru.stacked-crooked.com/a/8c7ff8981de3318b
I don't disagree with that example but in the OP code, isnt EXP the root, or at least a handle to it?
Thanks jonnin. You're right. I was worried I wouldn't be able to find root if needed, so I asked early. exp is a ref to root.
JL, thankd for the alternative approach and the solution using the facade pattern.
JL, if this code had to provide simple derivatives of the polynomials. This might involve cloning the tree for certain derivatives. It seems this code is readily extensible to provide a derivate() method similar to evaluate(). What about cloning or deep cloning? What do you think?
> What about cloning or deep cloning? What do you think?

Implementing deep cloning is straight forward; however it may be quite expensive.
For instance the earlier code, modified for pure value semantics (deep clone everything except for rvalues)
creates 69 clones of various expression tree nodes.

Perhaps, cloning the tree only when creating derivatives or when required (at programmer discretion),
may be a more tenable approach.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135`` ``````#include #include namespace { #ifndef NDEBUG static unsigned long long nclones = 0 ; static unsigned long long record_clone() { return ++nclones ; } static unsigned long long num_clones() { return nclones ; } #else static unsigned long long record_clone() {} static unsigned long long num_clones() { return 0 ; } #endif // NDEBUG } /////////////////// begin interpreter //////////////////////// struct abstract_expression { using pointer = std::unique_ptr ; virtual ~abstract_expression() = default ; // required for unique pointers virtual double evaluate() const = 0 ; virtual pointer clone() const = 0 ; }; struct number : abstract_expression { explicit number( double value ) : value(value) {} virtual double evaluate() const override { return value ; } virtual pointer clone() const override { record_clone() ; return std::make_unique(*this) ; } const double value ; }; struct binary_expression : abstract_expression { binary_expression( const pointer& first, const pointer& second ) : first( first->clone() ), second( second->clone() ) {} binary_expression( pointer&& first, pointer&& second ) : first( std::move(first) ), second( std::move(second) ) {} protected: template < typename DERIVED > static pointer minimal_clone( const DERIVED& d ) { record_clone() ; return std::make_unique( d.first->clone(), d.second->clone() ) ; } protected: pointer first ; protected: pointer second ; }; struct plus : binary_expression { using binary_expression::binary_expression ; virtual double evaluate() const override { return first->evaluate() + second->evaluate() ; } virtual pointer clone() const override { return minimal_clone(*this) ; } }; struct minus : binary_expression { using binary_expression::binary_expression ; virtual double evaluate() const override { return first->evaluate() - second->evaluate() ; } virtual pointer clone() const override { return minimal_clone(*this) ; } }; struct multiply : binary_expression { using binary_expression::binary_expression ; virtual double evaluate() const override { return first->evaluate() * second->evaluate() ; } virtual pointer clone() const override { return minimal_clone(*this) ; } }; struct divide : binary_expression { using binary_expression::binary_expression ; virtual double evaluate() const override { return first->evaluate() / second->evaluate() ; } virtual pointer clone() const override { return minimal_clone(*this) ; } }; /////////////////// end interpreter //////////////////////// ////////////////// begin facade /////////////////////////////// // collapses the entire hierarchy into a single surrogate type // users do not need to deal with pointers or worry about dynamic storage duration // expressions can be created by using overloaded operators on values // could use pure value semantics (clone instead of sharing with shared pointer); // however this could be somewhat expensive, particularly for common sub-expressions struct expression { expression( double dbl ) : expr( std::make_unique(dbl) ) {} expression( const expression& that ) : expr( that.expr->clone() ) {} expression( expression&& that ) : expr( std::move(that.expr) ) {} expression& operator= ( expression that ) { expr = std::move(that.expr) ; return *this ; } ~expression() = default ; double evaluate() const { return expr->evaluate() ; } friend expression operator+ ( expression a, expression b ) { return expression( std::make_unique( std::move(a.expr), std::move(b.expr) ) ) ; } friend expression operator- ( expression a, expression b ) { return expression( std::make_unique( std::move(a.expr), std::move(b.expr) ) ) ; } friend expression operator* ( expression a, expression b ) { return expression( std::make_unique( std::move(a.expr), std::move(b.expr) ) ) ; } friend expression operator/ ( expression a, expression b ) { return expression( std::make_unique( std::move(a.expr), std::move(b.expr) ) ) ; } friend std::ostream& operator<< ( std::ostream& stm, const expression& expr ) { return stm << expr.evaluate() ; } private: abstract_expression::pointer expr ; expression( abstract_expression::pointer&& expr ) : expr( std::move(expr) ) {} }; // and for good measure, provide a user defined literal expression operator "" _X( long double v ) { return expression( double(v) ) ; } ////////////////// end facade /////////////////////////////// int main() { const expression e1 = 138.5_X * 4.7 + 99.8 ; std::cout << std::fixed << e1 << '\n' ; const expression e2 = e1 / ( 4.2_X + 5.8 ) - 50 ; std::cout << e2 << '\n' ; std::cout << (e1+e2) * (e1-e2) << ' ' << e1*e1 - e2*e2 << '\n' ; std::cout << num_clones() << " clones were made!\n" ; }``````

http://coliru.stacked-crooked.com/a/479bf53c0c3496de
http://rextester.com/CIFQG19815