C++

Forum

 
 
Need Root of Tree

vtee2014 (16)
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
};

class NodeAdd : public NodeOperator
{
public:
NodeAdd::NodeAdd( NodeExpression* lt, NodeExpression* rt );
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;
}

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

double NodeAdd::evaluate()
{
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;

exp = new NodeAdd(
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;
}
jonnin (11333)
... typically the root of a tree is known as the entry point, you should have stored it somewhere as you built the tree?
JLBorges (13770)
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
http://www.informit.com/store/ruminations-on-c-plus-plus-a-decade-of-programming-9780201423396 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
 
#include <iostream>
#include <memory>

/////////////////// begin interpreter ////////////////////////
struct abstract_expression
{
    using pointer = std::shared_ptr<abstract_expression> ;
    
    // 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<number>(dbl) ) {}

    double evaluate() const { return expr->evaluate() ; }

    friend expression operator+ ( const expression& a, const expression& b )
    { return expression( std::make_shared<plus>( a.expr, b.expr ) ) ; }

    friend expression operator- ( const expression& a, const expression& b )
    { return expression( std::make_shared<minus>( a.expr, b.expr ) ) ; }

    friend expression operator* ( const expression& a, const expression& b )
    { return expression( std::make_shared<multiply>( a.expr, b.expr ) ) ; }

    friend expression operator/ ( const expression& a, const expression& b )
    { return expression( std::make_shared<divide>( 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
jonnin (11333)
I don't disagree with that example but in the OP code, isnt EXP the root, or at least a handle to it?
vtee2014 (16)
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.
vtee2014 (16)
JL, thankd for the alternative approach and the solution using the facade pattern.
vtee2014 (16)
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?
JLBorges (13770)
> 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. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
#include <iostream>
#include <memory>

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

    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<number>(*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<DERIVED>( 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<plus>(*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<minus>(*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<multiply>(*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<divide>(*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<number>(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<plus>( std::move(a.expr), std::move(b.expr) ) ) ; }

    friend expression operator- ( expression a, expression b )
    { return expression( std::make_unique<minus>( std::move(a.expr), std::move(b.expr) ) ) ; }

    friend expression operator* ( expression a, expression b )
    { return expression( std::make_unique<multiply>( std::move(a.expr), std::move(b.expr) ) ) ; }

    friend expression operator/ ( expression a, expression b )
    { return expression( std::make_unique<divide>( 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
Topic archived. No new replies allowed.