BlueClue's Blog

《算术表达式的初级构造》中的测试代码：

Binary_Node* t = new Binary_Node("*",
                     new Unary_Node("-", new Int_Node(5)),
                     new Binary_Node("+", new Int_Node(3), new Int_Node(4)))

对于这样的表达式，显而易见的问题是创建的节点无法释放，当然，用户可以逐一创建再逐一释放，但是原书作者认为不应该把内存管理这类烦心事推给用户，作者认为面向对象的抽象不够彻底，我们只是抽象出了表达式树的圆圈节点，没有对箭头建模，使得用户不得不亲自操作指针，这样，第7章的“句柄类”我们便可以拿来管理节点之间的指针。

把原来的Expr构造成句柄类，就解决了内存释放的问题，然后，添加显示计算结果的函数eval()，具体改造代码如下：

#include <iostream>
#include <conio.h>
#include <stdio.h>
#include <string>
using namespace std;
class Expr_Node;
//句柄类
class Expr
{
        friend ostream& operator<<(ostream&, const Expr&amp  ;
        Expr_Node* p;                               //节点指针
public:
        Expr(int);                                  //创建一个Int_Node
        Expr(const string&, Expr);                  //创建一个Unary_Node
        Expr(const string&,Expr,Expr);              //创建一个Binary_Node
        Expr(const Expr& t);
        Expr& operator=(const Expr&amp  ;
        int eval() const;
        void print(ostream&amp   const;
        ~Expr();
};
//节点
class Expr_Node{
        friend class Expr;
        int use;
protected:
        Expr_Node(): use(1){};
        virtual void print(ostream&amp   const = 0;
        virtual ~Expr_Node(){};
        virtual int eval() const = 0;
};
ostream&
operator << (ostream& o, const Expr& e)
{
        e.print(o);
        return o;
}
//无子节点的节点
class Int_Node: public Expr_Node{
        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{
        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 Unary_Node";
        };
};
//二元节点
class Binary_Node: public Expr_Node{
        friend   class Expr;
        string op;
        Expr left;
        Expr right;
public:
        Binary_Node(const string& a, Expr b,Expr c)
                  p(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;
                throw "error,bad op "+op+" Int Binary_Node";
        }
};
Expr::Expr(int n)
{
        p = new Int_Node(n);
};
Expr::Expr(const Expr& t)
{
        p = t.p; ++p->use;
};
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:  perator =(const Expr& rhs)
{
        rhs.p->use++;
        if(--p->use == 0)
                delete p;
        p = rhs.p;
        return *this;
}
int Expr::eval() const
{
        return p->eval();
};
void Expr::print(ostream& o) const
{
        p->print(o);
};
Expr::~Expr()
{
        if(--p->use == 0)
                delete p;
}

类图如下：

测试代码：

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