面向对象编程的三要素：数据抽象、继承以及动态绑定。

这里讨论一个算术表达式树问题，如(-5)*(3+4)对应的表达式树为：

我们希望通过调用合适的函数来创建这样的树，然后打印该树完整的括号化形式。例如：

Expr t = Expr("*", Expr("-",5), Expr("+", 3, 4));cout << t << endl;

输出结果为：((-5)*(3+4))

此外我们不想为这些表达式的表示形式操心，也不想关心它们内存分配和回收的事宜。

 

从上面图我们可以看出，图中有两种对象节点和箭头。每个节点包含一个值——一个操作数或者一个操作符——并且每个结点又具有零个、一个或者两个子节点。

这些节点既是相同的又是不同的，我们该如何抽象节点的数据结构呢？

 

这些节点首先有一个共同的特点：每个类都要存储一个值以及一些子节点。同时也可以很容易看出这些节点的一些不同点，比如它们存储的值的种类，子节点的数目。

 

在设计类的时候继承使得我们可以不中这些类的共同点，而动态绑定又可以帮助各个节点确定身份（从而才去不同的操作）。

 

仔细分析我们可以把节点分为三种类型：一种表示整数表达式，包含一个整数值，无子节点。另外两种分别表示一元表达式和二元表达式（包含一个操作符，分别有一个或者两个子节点）。因为这些节点的不同，我们在打印的时候也要采取不同的操作，这时候就可以使用动态绑定了：我们可以定义一个virtual 函数来指明应当如何打印各种节点。

注意到这三种节点都成为节点，我们可以先定义一个共同的基类：

class Expr_node{     friend     ostream & operator << ( ostream &, const Expr_node &);          protected:               virtual void print(ostream &) const = 0;               virtual ~Expr_node() { }}; 

由于Expr_node 类是一个虚基类，不能实例化对象，只有从其中派生类来实例化对象。Expr_node 类的存在只是为了获得公共的接口。

 

接着我们先来定义输出操作符，它要调用“对应”的print函数：

ostream & operator << ( ostream & o, const Expr_node & e){     e.print(o);     return 0;} 

按照前面对三种节点的分析，可以很快定义出第一种节点：

class Int_node : public Expr_node{     private:          int n;     public:          Int_node( int k) : n(k) {}          void print(ostream & o) const { o << n; }};

 

对于一元表达式或者二元表达式，因为其中包含有子节点，这时候我们并不知道子节点的类型会是什么，因此不能按值存储子节点，必须存储指针。

class Unary_node : public Expr_node{     private:          string op;          Expr_node *opnd;     public:          Unary_node( const string &a, Expr_node *b) : op(a), opnd(b) { }          void print(ostream & o) const { o << "(" << op << *opnd << ")"; }}; class Binary_node : public Expr_node{     private:          string op;          Expr_node *left;          Expr_node *right;     public:          Binary_node( const string &a, Expr_node *b, Expr_node *c) : op(a),left(b),right(c) { }          void print( ostream & o) const { o << "(" << *left << op << *right << ")"; } };

 

从现有的定义来看，如果我们要创建下面的表达式树：

Expr t = Expr( "*", Expr("-",5), Expr("+",3,4) );

 

则需要像下面一样来实现：（创建一元和二元表达式树的构造函数期望获得指针，而不是对象）

Binary_node *t = new Binary_node("*", new Unary_node("-",new Int_node(5), new Binary_node("+", new Int_node(3), new Int_node(4) );

     这个改进离我们理想的表达方式还有差距，并且我们不再拥有指向内层new的对象的指针，因此上述代码的情形会造成内存泄露，如果我们通过定义好析构函数来解决这个问题，则又可能会多次删除对象，因为理想情况下可能有多个Expr_node指向同一个下层表达式对象，这种形式把内存管理的事情都交给了用户。

 

     既然用户关心的只是树，而不是树中的单个节点，就可以用Expr来隐藏Expr_node的继承层次。这里又回到了前面讨论的句柄类的内容，用户可见的只有Expr。既然用户要乘船的是Expr 而不是Expr_node, 我们就希望Expr的构造函数能代表所有3种Expr_node。每个Expr构造函数豆浆创建Expr_node的派生类的一个合适对象，并且将这个对象的地址存储在正在创建的Expr对象中。Expr 类的用户不会直接看到Expr_node 对象。

 

class Expr{     private:          Expr_node *p;          friend ostream & operator <<( ostream &, const Expr &);     public:          Expr(int );          Expr(const string &, Expr);          Expr(const string &, Expr, Expr );          Expr(const Expr &);          Expr & operator = (const Expr &);          ~Expr() { delete p; }};

 

一系列的构造函数创建适当的Expr_node，并将其地址存储在p中：

Expr :: Expr(int n){     p = new Int_node(n);}Expr :: Expr(const string& op, Expr t){     p = new Unary_node(op, t);}Expr :: Expr(const string &op, Expr left, Expr right){     p = new Binary_node(op, left, right);}

 

现在使用Expr 为 Expr_node 分配内存，我i类避免不必要的复制，我们依然维护一个引用计数，但这里引用计数包含在Expr_node 里面，Expr 类和 Expr_node 类系统管理引用计数，因此Expr 需要作为Expr_node的友元出现。

 

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

当Expr 类“复制”一个Expr_node 时，该Expr 将其引用计数增1，当引用为0的时候删除底层的Expr_node:

Expr 类需要增加复制构造函数，析构函数和赋值函数：

class Expr{     // 和前面一样     public:          Expr (const Expr & t) { p = t.p; ++p->use; }          ~Expr() { if( --p->use == 0) delete p; }          Expr & operator = (const Expr & t);};Expr & Expr :: operator = (const Expr &rhs){     rhs.p->use++;     if(--p->use == 0)          delete p;     p = rhs.p;     return *this;} 

针对Expr 我们还需要定义输出操作符：

ostream & operator << (ostream & o, const Expr & t){     t.p->print(o);     return o;}

 

最后需要更改每个派生自Expr_node的类，令其操作为私有，将Expr 类声明为友元，存储Expr而不是Expr_node的指针，例如：

class Binary_node : public Expr_node{     friend class Expr;     string op;     Expr left;     Expr right;     Binary_node};

 

如果我们需要对表达式求值，在现在的构架下也很容易实现，可以在 Expr 类中增加 eval 成员方法，eval 可以将实际的求值工作委托为做出Expr 的结点来完成。

 

class Expr{     private:          // 和前面一样     public：          // 和前面一样          int eval() const { return p->eval() ; } // 新添加的};这样 Expr_node 类就需要添加另一个纯虚函数：class Expr_node{     protected:          virtual int eval() const = 0;          // 和前面一样};

 

针对Expr_node 派生的每一个类添加一个函数来实现求值运算。（这里就不单独列出）

 

将全部代码列出：

/*既然用户关心的只是树，而不是树中的单个节点，就可以用Expr来隐藏Expr_node的继承层次。这里又回到了前面讨论的句柄类的内容，用户可见的只有Expr了，内存管理的事情就完全由Expr掌控！改进后代码如下：*/#include 
        
         #include 
         
          using namespace std; class Expr_node{friend class Expr; //友元类可以被继承,句柄类Expr还要操作这里的use，所以是必须的int use;            //引用计数public:virtual void print(ostream&) const = 0;virtual int eval() const = 0;public:Expr_node():use(1) {}virtual ~Expr_node() {}}; class Expr                     //句柄类{friend ostream& operator<<(ostream &o, const Expr &e);private:Expr_node *p;       //指向基类的指针public:Expr(int n);Expr(const string &op, Expr t);Expr(const string &op, Expr left, Expr right);Expr(const Expr &t);Expr& operator=(const Expr&);int eval() const { return p->eval();};~Expr(){ if(--p->use == 0)delete p;}}; class Int_node: public Expr_node{private:friend class Expr;int n;//public:Int_node(int k):n(k) {}void print(ostream &o) const{o << n;}int eval() const { return n;}};  class Unary_node: public Expr_node{private:friend class Expr;string op;Expr opnd;//public:Unary_node(const string &a, Expr b):op(a), opnd(b) {}void print(ostream &o) const{o << "(" << op << opnd << ")";}int eval() const { if(op == "-")return -opnd.eval();throw "error, bad op" + op + "int UnaryNode";}}; class Binary_node: public Expr_node{private:friend class Expr;string op;Expr left;Expr right;//public:Binary_node(const string &a, Expr b, Expr c):op(a), left(b), right(c) {}void print(ostream &o) const{o << "(" << left << op << right << ")";}int eval() const{int op1 = left.eval();int op2 = right.eval(); if(op == "-") return op1 - op2;if(op == "+") return op1 + op2;if(op == "*") return op1 * op2;if(op == "/" && op2 != 0) return op1 / op2;}}; Expr::Expr(int n) { p = new Int_node(n); }Expr::Expr(const string& op, Expr t) { p = new Unary_node(op,t); }Expr::Expr(const string &op, Expr left, Expr right) { p = new Binary_node(op, left, right); }Expr::Expr(const Expr& t) { p = t.p; ++p->use; } Expr& Expr::operator=(const Expr& rhs){rhs.p->use++;if(--p->use == 0)delete p;p = rhs.p;return *this;} ostream& operator<<(ostream &o, const Expr &e){e.p->print(o);return o;} void main(){Expr t = Expr("*",Expr("-", Expr(5)),Expr("+", Expr(3), Expr(4)));cout << t << endl;cout << t.eval()<
         
        

运行结果：

C:\Windows\system32\cmd.exe /c  chap8_Expr2.exe

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

-35

Hit any key to close this window...