Previous Table of Contents Next


7.5.3. An Extended Object-Oriented Programming Example

To give a clearer idea of the point of data abstraction and object-oriented programming, here is a complete program that uses data abstraction, inheritance, and dynamic binding. This example first appeared in the Journal of Object-Oriented Programming, and a somewhat different version appears in Ruminations on C++ (Koenig A. & Moo, 1997). This program shows a lot of ideas, despite its small size, and will repay careful study.

The program deals with trees that represent arithmetic expressions. For example, the expression (-5)*(3+4) corresponds to the following tree:

An expression tree contains nodes that represent constants, unary operators, and binary operators. Such a tree might be used in a compiler or a calculator program. Inheritance captures the similarities between the types of nodes. Dynamic binding allows nodes to “know” what type they are, making it unnecessary to incorporate this knowledge in every program that uses these trees. Together, inheritance and dynamic binding make it possible to add new kinds of nodes without incorporating this knowledge in every program that accesses a node. Data abstraction allows programmers to create and use these trees without worrying about their internal representation, and allows the people who implement the trees to change their representation without breaking the programs that use them.

The goal is to be able to write:

   main()
   {
       Tree t = Tree (“*”, Tree (“-”, 5), Tree (“+”, 3, 4));
       cout << t << “\n”;
       t = Tree (“*”, t, t);
       cout << t << “\n”;
   }

and get

   ((-5)*(3+4))
   (((-5)*(3+4))*((-5)*(3+4)))

as output, without having to worry about how a Tree is represented or about when or how to allocate and free memory for parts of a Tree.

This toy program does things that are typical of many larger programs such as compilers, editors, CAD/CAM systems, and others that deal with complicated input. Much of the effort in such programs is in manipulating trees, graphs, and similar data structures. Authors of such programs perennially face problems of memory allocation, flexibility, and efficiency. Object-oriented techniques allow the solutions of these problems to be localized so that each subsequent change does not require parallel changes all over the program.

7.5.3.1. The Node Class

The diagram contains two distinct kinds of objects: nodes (represented by circles) and edges (represented by arrows). Each node contains either an operand or an operator. Each edge can be thought of as representing the entire tree at the end of its arrow. Thus the natural way to represent a tree involves two classes: one, called Node, to represent nodes and the other, called Tree, to represent trees (or, equivalently, edges).

Here is the declaration of the Node class:

   class Node {
       friend class Tree;
       friend ostream& operator<< (ostream&, const Tree&);
   private:
       int use;
   protected:
       Node() { use = 1; }
       virtual void print (ostream&) const = 0;
       virtual ~Node() { }
   };

The Node constructor is declared as protected so that only members or friends of the Node class, or classes derived from Node, can create Nodes. The Node and Tree classes are interrelated, so the Node class definition nominates the Tree class as a friend. Recall that friends have the same privileges as members, but are not members. If two classes depend on each other’s implementations, the right way to handle this in C++ is to use friend declarations.

The Node class definition also includes a declaration of the << output operator for Tree objects so that the Tree output routine can access the private data of the associated Node. This operator should not be a member of Node because it acts on an ostream, not a Node. The ostream class has been defined elsewhere and this program cannot (and should not) change that definition! However, the program that prints a Node needs to know how a Node is represented and is therefore declared as a friend. This is another example of using a friend declaration to link two classes.

The print function is a pure virtual function. We are not ever actually going to have any objects of class Node, but only of classes derived from Node. Therefore, although we need to define print in the Node base class (because although there are no Node objects, we will nevertheless have pointers to Node and use those pointers to call the virtual print function), we do not need to say what it does. There are no objects of class Node, so we will always be executing the print function in a class derived from Node. Later declarations will derive several different kinds of nodes and the appropriate actions will be selected automatically during execution to print and deallocate them.


Previous Table of Contents Next