C++ Notes: Expression Tree using Inheritance

  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

  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

  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