From: schmidt@rz.uni-passau.de (SCHMIDT GUIDO)
Newsgroups: comp.lang.c++
Subject: Generic Expression Tree: Is this good code?
Date: Wed, 27 Jan 1993 19:39:07 GMT
Organization: University of Passau - Germany
NNTP-Posting-Host: hiwi170.rz.uni-passau.de
Keywords: templates, container, LEDA

Hello!
 
I'm a beginner with C++ and recently trying to develop a project
that is a little more complex: 
 
I would like to have an expression tree that can hold:
	* leafs of any data type
	* leafs that hold identifiers for any data type;
	  these identifiers are elements of a current environment
	* unary expression trees that hold a unary operation on any
	  data type and an expression tree
	* binary expression trees that hold a binary operation on any
	  data type and a left and a right expression tree
 
For a given grammar I could then parse the input and build up an
expression tree which I simply evaluate by calling a function eval().

E.g.: empl.name = "Smith" AND empl.salary >= 100000 OR empl.age < 21

After parsing this I would get an expression tree as follows:
 
                 OpTree<Boolean>                        // the expression tree
                         |
          BOpTree<BoolBFunc, Boolean, Boolean>          // BoolBFunc = AND
             |                             |
BOpTree<StringCmpFunc, Boolean, String>    |            // StringCmpFunc = "="
        |                       |          |
IdLeaf<String>("empl.name")   Leaf<String> |
                                           |
                  BOpTree<BoolBFunc, Boolean, Boolean>  // BoolBFunc = OR
                    |                             |
       BOpTree<IntegerCmpFunc, Boolean, Integer>  |     // IntegerCmpFunc = ">="
             |                        |           |
IdLeaf<Integer>("empl.salary")    Leaf<Integer>   |
                                                  |
              BOpTree<IntegerCmpFunc, Boolean, Integer> // IntegerCmpFunc = "<"
                       |                        |
            IdLeaf<Integer>("empl.age")    Leaf<Integer>
 
As from the notation already perceptible I've tried to implement this
using templates. 
For the current environment I've used the container class DICTIONARY
taken from the class library LEDA 3.0. I use it with Borland BC 3.0.
The environment holds identifiers and the corresponding data. This data
so far can be of type Integer, Numeric and String. Naturally, I've run 
into the common problem of holding objects of different types in one
container. I've tried to solve this by deriving all classes that can be
in an environment from an abstract base class called AObject. Is this
good practice? 
 
Below you find some fragments of my source code, i.e. the template
declarations of all the used data types (cf. classdef.h), the template
declarations of the expression tree (class OpTree and derived classes)
(cf. optree.h), and some examples of how an expression tree is built
by parsing (cf. sparse.h). Is this good code? There are a few things
I'm not very happy with:
	* the function: OpTree<T>& copy() const
	  is it avoidable
	* the function: T lookup() const { return *(T*)(env->access(id)); }
	  here a pointer to AObject is retrieved from the environment and
	  then cast to type T
	* the usage of the pointer OpTree<Boolean> * tmp: I think I could
	  do without, but then the compiler skips the lines:
	    OpTree<Boolean> * res = new BOpTree<BBinaryFunc, Boolean, 
Boolean>(BOr, *a, *b);
 	    delete a; 
	    delete b; 
	  in function expression() (cf. sparse.cpp)

Any comments or recommendations for improvement are appreciated.
 
Guido
 
 
/-----------------------------------------------------------------/
/                            source                               /
/-----------------------------------------------------------------/
 
// classdef.h 
 
#ifndef __CLASSDEF_H 
#define __CLASSDEF_H 
 
#include <LEDA\basic.h> 
 
const int ClassInteger = 0; 
const int ClassNumeric = 1; 
const int ClassBoolean = 2; 
const int ClassString = 3; 
 
const int False = 0; 
const int True = !0; 
 
class AObject { 
public: 
   virtual int ofClass() const = 0; 
   virtual char * ClassName() const = 0; 
}; 
 
template< class T, int Number, char * Name > 
class Derived : public AObject { 
public: 
   Derived() {} 
   Derived( T d ) : data(d) {} 
   virtual int ofClass() const { return Number; } 
   virtual char * ClassName() const { return Name; } 
   operator T() const { return data; } 
   friend ostream& operator<<( ostream& o, const Derived<T, Number, Name>& d ) { return o << d.data; } 
private: 
   T data; 
}; 
 
class Boolean : public AObject { 
   public: 
      Boolean() : value(False) {} 
      Boolean( int v ) : value(v) {} 
      virtual int ofClass() const { return ClassBoolean; } 
      virtual char * ClassName() const { return "Boolean"; } 
      operator int() const { return value; } 
      friend ostream& operator<<( ostream& o, const Boolean& b ) { return o << (b.value ? "True" : "False"); } 
   private: 
      int value; 
}; 
 
typedef Derived<int, ClassInteger, "Integer"> Integer; 
typedef Derived<double, ClassNumeric, "Numeric"> Numeric; 
typedef Derived<string, ClassString, "String"> String; 
 
#endif 
 
//eof 
 
 
// optree.h 
 
#ifndef __OPTREE_H 
#define __OPTREE_H 
 
#include <LEDA\dictiona.h> 
#include "classdef.h" 
 
typedef dictionary<string, AObject*> Environment; 
 
template< class T > 
class OpTree { 
public: 
   virtual ~OpTree() {} 
   virtual OpTree<T>& copy() const = 0; 
   virtual T eval() const = 0; 
   virtual void print( ostream& o = cout ) const = 0; 
   friend ostream& operator<<( ostream& o, const OpTree<T>& a ) { a.print(o); return o; } 
}; 
 
template< class T > 
class Leaf : public OpTree<T> { 
public: 
   Leaf() {} 
   Leaf( const T& d ) : data(d) {} 
   Leaf( const Leaf<T>& copyLeaf ) : data(copyLeaf.data) {} 
   virtual ~Leaf() {} 
   virtual OpTree<T>& copy() const { return *new Leaf<T>(data); } 
   virtual T eval() const { return data; } 
   virtual void print( ostream& o = cout ) const { o << "Leaf<" << data.ClassName() << ">(" << data << ")"; } 
private: 
   T data; 
}; 
 
template< class T > 
class IdLeaf : public OpTree<T> { 
public: 
   IdLeaf( const string& name, Environment* e ) : id(name), env(e) {} 
   IdLeaf( const IdLeaf<T>& copyIL ) : id(copyIL.id), env(copyIL.env) {} 
   virtual ~IdLeaf() {} 
   virtual OpTree<T>& copy() const { return *new IdLeaf<T>(id, env); } 
   virtual T eval() const { return lookup(); } 
   virtual void print( ostream& o = cout ) const { 
      o << "IdLeaf<" << T().ClassName() << ">(\"" << id << "\", " << lookup() << ")"; 
   } 
private: 
   string id; 
   Environment * env; 
   T lookup() const { return *(T*)(env->access(id)); } 
}; 
 
template< class UOperationT , class T, class OperandT > 
class UOpTree : public OpTree<T> { 
public: 
   UOpTree( UOperationT _op, const OpTree<OperandT>& _unary ) 
      : op(_op), unary(_unary.copy()) {} 
   UOpTree( const UOpTree<UOperationT, T, OperandT>& copyUOT ) 
      : op(copyUOT.op), unary(copyUOT.unary.copy()) {} 
   virtual ~UOpTree() { delete &unary; } 
   virtual OpTree<T>& copy() const { 
      return *new UOpTree<UOperationT, T, OperandT>(op, unary); 
   } 
   virtual T eval() const { return op(unary.eval()); } 
   virtual void print( ostream& o = cout ) const { 
      o << "UOpTree<" << T().ClassName() << ">(\n" << unary << "\n)"; 
   } 
private: 
   UOperationT op; 
   OpTree<T>& unary; 
}; 
 
template< class BOperationT, class T, class OperandT > 
class BOpTree : public OpTree<T> { 
public: 
   BOpTree( BOperationT _op, const OpTree<OperandT>& _left, const OpTree<OperandT>& _right ) 
      : op(_op), left(_left.copy()), right(_right.copy()) {} 
   BOpTree( BOpTree<BOperationT, T, OperandT>& copyBOT ) 
      : op(copyBOT.op), left(copyBOT.left.copy()), right(copyBOT.right.copy()) {} 
   virtual ~BOpTree() { delete &left; delete &right; } 
   virtual OpTree<T>& copy() const { 
      return *new BOpTree<BOperationT, T, OperandT>(op, left, right); 
   } 
   virtual T eval() const { return op(left.eval(), right.eval()); } 
   virtual void print( ostream& o = cout ) const { 
      o << "BOpTree<" << T().ClassName() << ">(\n" << left << ", " << right << "\n)"; 
   } 
private: 
   BOperationT op; 
   OpTree<OperandT>& left; 
   OpTree<OperandT>& right; 
}; 
 
#endif 
 
 
// sparse.cpp 
 
[...] 
 
OpTree<Boolean> * block(); 
OpTree<Boolean> * expression(); 
OpTree<Boolean> * andexpression(); 
OpTree<Boolean> * subexpression(); 
OpTree<Boolean> * complement(); 
OpTree<Boolean> * I_comparison(); 
OpTree<Integer> * I_factor(); 
void parseerror( PError error ); 
 
 
[...] 
 
OpTree<Boolean> * expression() { 
   OpTree<Boolean> * tmp = andexpression(); 
   if (noerror) { 
      while (token == tokenOr) { 
         gettoken(); 
         OpTree<Boolean> * a = tmp; 
         OpTree<Boolean> * b = andexpression(); 
         if (noerror) { 
            OpTree<Boolean> * res = new BOpTree<BBinaryFunc, Boolean, Boolean>(BOr, *a, *b); 
            delete a; 
            delete b; 
            tmp = res; 
         } 
         else { 
            delete a; 
            return 0; 
         } 
      } 
      return tmp; 
   } 
   else 
      return 0; 
} 
 
[...] 
 
OpTree<Integer> * I_factor() { 
   if (token == tokenInteger) { 
      gettoken(); 
      return new Leaf<Integer>(valueI); 
   } 
   else if (token == tokenIntegerId) { 
      gettoken(); 
      return new IdLeaf<Integer>(ident, env); 
   } 
   else { 
      parseerror(errIntegerExpected); 
      return 0; 
   } 
} 
 
[...] 
 
void parse( Environment * e ) {
   noerror = True;
   env = e;
   gettoken();
   OpTree<Boolean> * res = block();    // the expression tree
   if (token != tokenEOF)
      parseerror(errEOFExpected);
   if (noerror) {
      cout << *res << endl             // print the tree  
           << res->eval() << endl;     // print the tree's result
   }
   delete res;
}

[...]

// eof 

end of code
--------------------------------------------------------------------
- Guido Schmidt                                                    -
- schmidt@rz.uni-passau.de                                         -
- Universitaet Passau, Germany                                     -
--------------------------------------------------------------------

Newsgroups: comp.lang.c++