home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / lang / cplus / 19989 < prev    next >
Encoding:
Text File  |  1993-01-28  |  10.2 KB  |  324 lines
  1. Path: sparky!uunet!math.fu-berlin.de!fauern!rz.uni-passau.de!hiwi170.rz.uni-passau.de!schmidt
  2. From: schmidt@rz.uni-passau.de (SCHMIDT GUIDO)
  3. Newsgroups: comp.lang.c++
  4. Subject: Generic Expression Tree: Is this good code?
  5. Date: Wed, 27 Jan 1993 19:39:07 GMT
  6. Organization: University of Passau - Germany
  7. Lines: 312
  8. Message-ID: <schmidt.37@rz.uni-passau.de>
  9. NNTP-Posting-Host: hiwi170.rz.uni-passau.de
  10. Keywords: templates, container, LEDA
  11.  
  12. Hello!
  13.  
  14. I'm a beginner with C++ and recently trying to develop a project
  15. that is a little more complex: 
  16.  
  17. I would like to have an expression tree that can hold:
  18.     * leafs of any data type
  19.     * leafs that hold identifiers for any data type;
  20.       these identifiers are elements of a current environment
  21.     * unary expression trees that hold a unary operation on any
  22.       data type and an expression tree
  23.     * binary expression trees that hold a binary operation on any
  24.       data type and a left and a right expression tree
  25.  
  26. For a given grammar I could then parse the input and build up an
  27. expression tree which I simply evaluate by calling a function eval().
  28.  
  29. E.g.: empl.name = "Smith" AND empl.salary >= 100000 OR empl.age < 21
  30.  
  31. After parsing this I would get an expression tree as follows:
  32.  
  33.                  OpTree<Boolean>                        // the expression tree
  34.                          |
  35.           BOpTree<BoolBFunc, Boolean, Boolean>          // BoolBFunc = AND
  36.              |                             |
  37. BOpTree<StringCmpFunc, Boolean, String>    |            // StringCmpFunc = "="
  38.         |                       |          |
  39. IdLeaf<String>("empl.name")   Leaf<String> |
  40.                                            |
  41.                   BOpTree<BoolBFunc, Boolean, Boolean>  // BoolBFunc = OR
  42.                     |                             |
  43.        BOpTree<IntegerCmpFunc, Boolean, Integer>  |     // IntegerCmpFunc = ">="
  44.              |                        |           |
  45. IdLeaf<Integer>("empl.salary")    Leaf<Integer>   |
  46.                                                   |
  47.               BOpTree<IntegerCmpFunc, Boolean, Integer> // IntegerCmpFunc = "<"
  48.                        |                        |
  49.             IdLeaf<Integer>("empl.age")    Leaf<Integer>
  50.  
  51. As from the notation already perceptible I've tried to implement this
  52. using templates. 
  53. For the current environment I've used the container class DICTIONARY
  54. taken from the class library LEDA 3.0. I use it with Borland BC 3.0.
  55. The environment holds identifiers and the corresponding data. This data
  56. so far can be of type Integer, Numeric and String. Naturally, I've run 
  57. into the common problem of holding objects of different types in one
  58. container. I've tried to solve this by deriving all classes that can be
  59. in an environment from an abstract base class called AObject. Is this
  60. good practice? 
  61.  
  62. Below you find some fragments of my source code, i.e. the template
  63. declarations of all the used data types (cf. classdef.h), the template
  64. declarations of the expression tree (class OpTree and derived classes)
  65. (cf. optree.h), and some examples of how an expression tree is built
  66. by parsing (cf. sparse.h). Is this good code? There are a few things
  67. I'm not very happy with:
  68.     * the function: OpTree<T>& copy() const
  69.       is it avoidable
  70.     * the function: T lookup() const { return *(T*)(env->access(id)); }
  71.       here a pointer to AObject is retrieved from the environment and
  72.       then cast to type T
  73.     * the usage of the pointer OpTree<Boolean> * tmp: I think I could
  74.       do without, but then the compiler skips the lines:
  75.         OpTree<Boolean> * res = new BOpTree<BBinaryFunc, Boolean, 
  76. Boolean>(BOr, *a, *b);
  77.          delete a; 
  78.         delete b; 
  79.       in function expression() (cf. sparse.cpp)
  80.  
  81. Any comments or recommendations for improvement are appreciated.
  82.  
  83. Guido
  84.  
  85.  
  86. /-----------------------------------------------------------------/
  87. /                            source                               /
  88. /-----------------------------------------------------------------/
  89.  
  90. // classdef.h 
  91.  
  92. #ifndef __CLASSDEF_H 
  93. #define __CLASSDEF_H 
  94.  
  95. #include <LEDA\basic.h> 
  96.  
  97. const int ClassInteger = 0; 
  98. const int ClassNumeric = 1; 
  99. const int ClassBoolean = 2; 
  100. const int ClassString = 3; 
  101.  
  102. const int False = 0; 
  103. const int True = !0; 
  104.  
  105. class AObject { 
  106. public: 
  107.    virtual int ofClass() const = 0; 
  108.    virtual char * ClassName() const = 0; 
  109. }; 
  110.  
  111. template< class T, int Number, char * Name > 
  112. class Derived : public AObject { 
  113. public: 
  114.    Derived() {} 
  115.    Derived( T d ) : data(d) {} 
  116.    virtual int ofClass() const { return Number; } 
  117.    virtual char * ClassName() const { return Name; } 
  118.    operator T() const { return data; } 
  119.    friend ostream& operator<<( ostream& o, const Derived<T, Number, Name>& d ) { return o << d.data; } 
  120. private: 
  121.    T data; 
  122. }; 
  123.  
  124. class Boolean : public AObject { 
  125.    public: 
  126.       Boolean() : value(False) {} 
  127.       Boolean( int v ) : value(v) {} 
  128.       virtual int ofClass() const { return ClassBoolean; } 
  129.       virtual char * ClassName() const { return "Boolean"; } 
  130.       operator int() const { return value; } 
  131.       friend ostream& operator<<( ostream& o, const Boolean& b ) { return o << (b.value ? "True" : "False"); } 
  132.    private: 
  133.       int value; 
  134. }; 
  135.  
  136. typedef Derived<int, ClassInteger, "Integer"> Integer; 
  137. typedef Derived<double, ClassNumeric, "Numeric"> Numeric; 
  138. typedef Derived<string, ClassString, "String"> String; 
  139.  
  140. #endif 
  141.  
  142. //eof 
  143.  
  144.  
  145. // optree.h 
  146.  
  147. #ifndef __OPTREE_H 
  148. #define __OPTREE_H 
  149.  
  150. #include <LEDA\dictiona.h> 
  151. #include "classdef.h" 
  152.  
  153. typedef dictionary<string, AObject*> Environment; 
  154.  
  155. template< class T > 
  156. class OpTree { 
  157. public: 
  158.    virtual ~OpTree() {} 
  159.    virtual OpTree<T>& copy() const = 0; 
  160.    virtual T eval() const = 0; 
  161.    virtual void print( ostream& o = cout ) const = 0; 
  162.    friend ostream& operator<<( ostream& o, const OpTree<T>& a ) { a.print(o); return o; } 
  163. }; 
  164.  
  165. template< class T > 
  166. class Leaf : public OpTree<T> { 
  167. public: 
  168.    Leaf() {} 
  169.    Leaf( const T& d ) : data(d) {} 
  170.    Leaf( const Leaf<T>& copyLeaf ) : data(copyLeaf.data) {} 
  171.    virtual ~Leaf() {} 
  172.    virtual OpTree<T>& copy() const { return *new Leaf<T>(data); } 
  173.    virtual T eval() const { return data; } 
  174.    virtual void print( ostream& o = cout ) const { o << "Leaf<" << data.ClassName() << ">(" << data << ")"; } 
  175. private: 
  176.    T data; 
  177. }; 
  178.  
  179. template< class T > 
  180. class IdLeaf : public OpTree<T> { 
  181. public: 
  182.    IdLeaf( const string& name, Environment* e ) : id(name), env(e) {} 
  183.    IdLeaf( const IdLeaf<T>& copyIL ) : id(copyIL.id), env(copyIL.env) {} 
  184.    virtual ~IdLeaf() {} 
  185.    virtual OpTree<T>& copy() const { return *new IdLeaf<T>(id, env); } 
  186.    virtual T eval() const { return lookup(); } 
  187.    virtual void print( ostream& o = cout ) const { 
  188.       o << "IdLeaf<" << T().ClassName() << ">(\"" << id << "\", " << lookup() << ")"; 
  189.    } 
  190. private: 
  191.    string id; 
  192.    Environment * env; 
  193.    T lookup() const { return *(T*)(env->access(id)); } 
  194. }; 
  195.  
  196. template< class UOperationT , class T, class OperandT > 
  197. class UOpTree : public OpTree<T> { 
  198. public: 
  199.    UOpTree( UOperationT _op, const OpTree<OperandT>& _unary ) 
  200.       : op(_op), unary(_unary.copy()) {} 
  201.    UOpTree( const UOpTree<UOperationT, T, OperandT>& copyUOT ) 
  202.       : op(copyUOT.op), unary(copyUOT.unary.copy()) {} 
  203.    virtual ~UOpTree() { delete &unary; } 
  204.    virtual OpTree<T>& copy() const { 
  205.       return *new UOpTree<UOperationT, T, OperandT>(op, unary); 
  206.    } 
  207.    virtual T eval() const { return op(unary.eval()); } 
  208.    virtual void print( ostream& o = cout ) const { 
  209.       o << "UOpTree<" << T().ClassName() << ">(\n" << unary << "\n)"; 
  210.    } 
  211. private: 
  212.    UOperationT op; 
  213.    OpTree<T>& unary; 
  214. }; 
  215.  
  216. template< class BOperationT, class T, class OperandT > 
  217. class BOpTree : public OpTree<T> { 
  218. public: 
  219.    BOpTree( BOperationT _op, const OpTree<OperandT>& _left, const OpTree<OperandT>& _right ) 
  220.       : op(_op), left(_left.copy()), right(_right.copy()) {} 
  221.    BOpTree( BOpTree<BOperationT, T, OperandT>& copyBOT ) 
  222.       : op(copyBOT.op), left(copyBOT.left.copy()), right(copyBOT.right.copy()) {} 
  223.    virtual ~BOpTree() { delete &left; delete &right; } 
  224.    virtual OpTree<T>& copy() const { 
  225.       return *new BOpTree<BOperationT, T, OperandT>(op, left, right); 
  226.    } 
  227.    virtual T eval() const { return op(left.eval(), right.eval()); } 
  228.    virtual void print( ostream& o = cout ) const { 
  229.       o << "BOpTree<" << T().ClassName() << ">(\n" << left << ", " << right << "\n)"; 
  230.    } 
  231. private: 
  232.    BOperationT op; 
  233.    OpTree<OperandT>& left; 
  234.    OpTree<OperandT>& right; 
  235. }; 
  236.  
  237. #endif 
  238.  
  239.  
  240. // sparse.cpp 
  241.  
  242. [...] 
  243.  
  244. OpTree<Boolean> * block(); 
  245. OpTree<Boolean> * expression(); 
  246. OpTree<Boolean> * andexpression(); 
  247. OpTree<Boolean> * subexpression(); 
  248. OpTree<Boolean> * complement(); 
  249. OpTree<Boolean> * I_comparison(); 
  250. OpTree<Integer> * I_factor(); 
  251. void parseerror( PError error ); 
  252.  
  253.  
  254. [...] 
  255.  
  256. OpTree<Boolean> * expression() { 
  257.    OpTree<Boolean> * tmp = andexpression(); 
  258.    if (noerror) { 
  259.       while (token == tokenOr) { 
  260.          gettoken(); 
  261.          OpTree<Boolean> * a = tmp; 
  262.          OpTree<Boolean> * b = andexpression(); 
  263.          if (noerror) { 
  264.             OpTree<Boolean> * res = new BOpTree<BBinaryFunc, Boolean, Boolean>(BOr, *a, *b); 
  265.             delete a; 
  266.             delete b; 
  267.             tmp = res; 
  268.          } 
  269.          else { 
  270.             delete a; 
  271.             return 0; 
  272.          } 
  273.       } 
  274.       return tmp; 
  275.    } 
  276.    else 
  277.       return 0; 
  278. } 
  279.  
  280. [...] 
  281.  
  282. OpTree<Integer> * I_factor() { 
  283.    if (token == tokenInteger) { 
  284.       gettoken(); 
  285.       return new Leaf<Integer>(valueI); 
  286.    } 
  287.    else if (token == tokenIntegerId) { 
  288.       gettoken(); 
  289.       return new IdLeaf<Integer>(ident, env); 
  290.    } 
  291.    else { 
  292.       parseerror(errIntegerExpected); 
  293.       return 0; 
  294.    } 
  295. } 
  296.  
  297. [...] 
  298.  
  299. void parse( Environment * e ) {
  300.    noerror = True;
  301.    env = e;
  302.    gettoken();
  303.    OpTree<Boolean> * res = block();    // the expression tree
  304.    if (token != tokenEOF)
  305.       parseerror(errEOFExpected);
  306.    if (noerror) {
  307.       cout << *res << endl             // print the tree  
  308.            << res->eval() << endl;     // print the tree's result
  309.    }
  310.    delete res;
  311. }
  312.  
  313. [...]
  314.  
  315. // eof 
  316.  
  317. end of code
  318. --------------------------------------------------------------------
  319. - Guido Schmidt                                                    -
  320. - schmidt@rz.uni-passau.de                                         -
  321. - Universitaet Passau, Germany                                     -
  322. --------------------------------------------------------------------
  323.  
  324.