这个例子很好的展示了面向对象编程的三个要素：数据抽象、继承和动态绑定。
问题：算术表达式的表达式树， 如(-5)*(3+4)对应的表达式树为：
我们希望通过调用合适的函数来创建这样的树，然后打印该树完整的括号化形式。例如：
Expr t = Expr("*", Expr("-",5), Expr("+", 3, 4));
cout << t << endl;
输出结果为：((-5)*(3+4))
面向对象的解决方案：
一 节点如何表示？
仔细观察上图，根据子节点的个数可以抽象出三种节点，分别有0，1，2个子节点的节点。如果让我来设计的话我很可能会这样描述节点：
class Node
{
private:
string value; //节点值
int num; //子节点个数
Node* son[2]; //储存子节点指针
public:
Node();
Node(string&, int); //0 个子节点
Node(string&, int, Node*); //1 个子节点
Node(string&, int, Node*, Node*); //2 个子节点
~Node();
};
这种表示方法需要设置专门的字段类指示子节点的个数。然而书中用继承解决了这个问题，让人拍案叫绝！
（1）考虑三种节点类的共同点与不同点：都具有节点值，都需要打印节点，但节点值类型不同，打印节点方式不同，子节点个数不同。
（2）考虑三种节点之间的关系： 每一种节点都与其他节点相互独立，一个没有子节点的节点不是“一种”有一个子节点的节点，反之亦然。
（3）综合上面两点，定义一个抽象基类，动态绑定在这里就有用武之地了。
二 几种节点类的具体定义：
#include
#include
using namespace std;
class Expr_node
{
friend ostream& operator<<(ostream&, const Expr_node&);
protected:
virtual void print(ostream&) const = 0;//动态绑定
virtual ~Expr_node(){}
};
ostream& operator<<(ostream& o, const Expr_node& e)
{
e.print(o);
return o;
}
class Int_node: public Expr_node //0 个子节点
{
private:
int n;
friend ostream& operator<<(ostream&, const Expr_node&);
public:
Int_node(int k) : n(k) {}
void print(ostream &o) const {o << n;}
};
class Unary_node:public Expr_node //1 个子节点
{
private:
string op;
Expr_node *opnd;
friend ostream& operator<<(ostream&, const Expr_node&);
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 //2 个子节点
{
private:
string op;
Expr_node *left;
Expr_node *right;
friend ostream& operator<<(ostream&, const Expr_node&);
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<< ")";}
};
void main()
{
Binary_node * t = new Binary_node("*",
new Unary_node("-", new Int_node(5)),
new Binary_node("+",new Int_node(3), new Int_node(4)));
cout << *t;
//节点未删除
}
三 类定义的缺陷
上面方案已经基本上解决问题了，但是创建表达式树的方式还有待改进。按照上面的方案，我们只能这样定义表达式：
Binary_node *t = new Binary_node("*",
new Unary_node("-", new Int_node(5)),
new Binary_node("+",new Int_node(3),new Int_node(4)));
cout << *t << endl;
这个改进离我们理想的表达方式还有差距，并且我们不再拥有指向内层new的对象的指针，因此上述代码的情形会造成内存泄露，如果我们通过定义好析构函数来解决这个问题，则又可能会多次删除对象，因为理想情况下可能有多个Expr_node指向同一个下层表达式对象，这种形式把内存管理的事情都交给了用户。
四 用句柄类改进。
既然用户关心的只是树，而不是树中的单个节点，就可以用Expr来隐藏Expr_node的继承层次。这里又回到了前面讨论的句柄类的内容，用户可见的只有Expr了，内存管理的事情就完全由Expr掌控！改进后代码如下：
#include
#include
using namespace std;
class Expr_node
{
friend class Expr; //友元类可以被继承
int use; //引用计数
public:
virtual void print(ostream&) 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&);
~Expr()
{
if(--p->use == 0)
del