這個例子很好的展示了面向對象編程的三個要素：數據抽象、繼承和動態綁定。
問題：算術表達式的表達式樹， 如(-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 <iostream>
#include <string>
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 <iostream>
#include <string>
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)
delete p;
}
};
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:
//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 << ")";
}
};
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 << ")";
}
};
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;
}
五 總結
這個例子很好的展示了面向對象的三個要素，這樣設計出的類具有很好的擴展性，比如再增加有多個子節點的節點，只要添加個新類，然後在Expr中添加個新構造函數就行了。用戶完全不必知道底層的代碼是怎麼實現的。以後面對問題的時候要好好的借鑒這種思想！
作者 yucan1001
