# C++ Notes: Expression Tree using Inheritance

Here is a basic framework for creating an expression tree using inheritance. There are many parts to be filled in, but it gives the general idea. It consists of three files.

- ExprNode.h
- ExprNode.cpp
- ExprNodeTest.cpp

## ExprNode.h

      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
    // ExprNode.h - Demonstrates inheritance.
    //    Incomplete: Needs everything that goes with
    //      deep copies (copy constructor, assignment,
    //      destructors, ==, ...)
    //    -- Fred Swartz 2002-10-06
    // Class hierarchy
    // ExprNode // for a node of an expression tree
    //     OperandNode   // for a single integer value.
    //     OperatorNode  // instantiate only subclasses
    //         AddNode   // for addition
    //         SubtractNode // for subtraction
    #ifndef EXPRNODE_H
    #define EXPRNODE_H

    ////////////////////////////////////////////////// class ExprNode
    class ExprNode {
      public:
        virtual int eval() = 0;  // pure virtual function
                                 // must be overridden in subclass
        ExprNode();
    };//end class ExprNode

    /////////////////////////////////////////////// class OperandNode
    class OperandNode : public ExprNode {
      public:
        OperandNode(int v);
        int eval();
      private:
        int value;
    };//end class OperandNode

    ////////////////////////////////////////////// class OperatorNode
    class OperatorNode : public ExprNode {
      public:
                   // Should define all functions common to
                   // subclasses here.
      protected:   // protected allows subclasses to use these
        ExprNode* left;   // left operand subtree
        ExprNode* right;  // right operand subtree
    };//end class OperatorNode

    /////////////////////////////////////////////////// class AddNode
    class AddNode : public OperatorNode {
      public:
        AddNode::AddNode(ExprNode* lft, ExprNode* rt);
        int eval(); // provide real version of ExprNode pure virtual.
    };//end class AddNode

    ////////////////////////////////////////////// class SubtractNode
    class SubtractNode : public OperatorNode {
      public:
        SubtractNode::SubtractNode(ExprNode* lft, ExprNode* rt);
        int eval(); // provide real version of pure virtual fcn.
    };//end class SubtractNode

    #endif

## ExprNode.cpp

      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
    // ExprNode class -- Fred Swartz 2002-10-06

    #include <stdexcept>
    using namespace std;

    #include "ExprNode.h"

    /////////////////////////////////////////////// ExprNode implementation
    //================================================ ExprNode constructor
    ExprNode::ExprNode() {
        cerr << "ExprNode::ExprNode" << endl;
    }//end constructor

    //====================================================== ExprNode::eval
    int ExprNode::eval() {
        throw logic_error("ExprNode::eval() must be overridden");
    }//end eval

    ///////////////////////////////////////////// OperandNode implementation

    //============================================== OperandNode constructor
    OperandNode::OperandNode(int val) {
        cerr << "OperandNode::OperandNode" << endl;
        value = val;
    }//end constructor OperandNode

    //==================================================== OperandNode::eval
    int OperandNode::eval() {
        cerr << "OperandNode::eval " << value << endl;
        return value;
    }//end OperandNode::eval

    ///////////////////////////////////////////////// AddNode implementation

    //=================================================== AddNode constructor
    AddNode::AddNode(ExprNode* lft, ExprNode* rt) {
        cerr << "AddNode::AddNode" << endl;
        left  = lft;
        right = rt;
    }//end constructor AddNode

    //======================================= AddNode::eval
       // Override ExprNode::eval
    int AddNode::eval() {
        cerr << "AddNode::eval" << endl;
        return left->eval() + right->eval();
    }//end AddNode::eval

    //////////////////////////////////////////// SubtractNode implementation

    //============================================== SubtractNode constructor
    SubtractNode::SubtractNode(ExprNode* lft, ExprNode* rt) {
        cerr << "SubtractNode::SubtractNode" << endl;
        left  = lft;
        right = rt;
    }//end constructor SubtractNode

    //==================================================== SubtractNode::eval
       // Override ExprNode::eval
    int SubtractNode::eval() {
        cerr << "SubtractNode::eval" << endl;
        return left->eval() - right->eval();
    }//end SubtractNode::eval

## ExprNodeTest.cpp

      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
    // ExprNodeTest.cpp - Demos use of ExprNode
    //   Fred Swartz - 2002-10-06

    #include <iostream>
    using namespace std;

    #include "ExprNode.h"

    //======================================== main
    int main() {
       ExprNode* x;
       OperandNode* a = new OperandNode(3);
       OperandNode* b = new OperandNode(-6);

       x = new AddNode(a, b);
       cout << x->eval() << endl;

       x = new SubtractNode(
                            new AddNode(
                                        new OperandNode(19),
                                        new OperandNode(-11)),
                            new SubtractNode(
                                        new OperandNode(5),
                                        new OperandNode(-5))
                            );
       cout << x->eval() << endl;

       return 0;
    }//end main

Correction: Bob Remeika noted that there is a memory leak in this program, and that a `delete` is needed to reclaim the memory which is assigned to `x`. When `main` returns, all of this program's memory is reclaimed, so the undeleted memory wouldn't be a big problem in this particular case. However, he's right, and when I get back to editing these notes, I'll insert the `delete`s along with some other improvements. Or I could just leave it as an "exercise for the student" :-}.