算术表达式树

93 阅读 0 评论 62 点赞

我是靠谱客的博主忧伤菠萝，最近开发中收集的这篇文章主要介绍算术表达式树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一个面向对象范例（算术表达式树）

1. 问题描述

用程序来表示算术表达式。例如表达式（-5）*（3+4）对应的树如下：

该表达式树包括常数、一元运算符和二元运算符的节点。编写合适的函数来创建这样的树，然后打印该树的完整括号形式。

2. 分析

考虑定义一系列的类，用继承组织起来。这些类有一些共同的点：每个类都要存储一个值以及一些子节点。图中有三种节点：一种表示整数表达式，包含一个整数值，无子节点。另外两种分别表示一元表达式和二元表达式，包含一个操作符，分别有一个或两个子节点。各个节点之间是相互独立的。所以需要定义一个表示节点的基类。如下：

Expr.h

#ifndef
_EXPR_H
#define
_EXPR_H
#include <iostream>
#include <string>
using namespace std;
namespace Meditation
{
//公共基类，表示节点
class Expr_node
{
friend ostream& operator<<(ostream &,const Expr_node &);
public:
virtual void print(ostream&) const =0;
virtual ~Expr_node(){ }
};
//整数表达式节点
class Int_node:public Expr_node
{
friend class Expr;
int n;
Int_node(int k):n(k) {}
void print(ostream & o) const
{
o<<n;
}
};
//一元表达式节点
class Unary_node:public Expr_node
{
friend class Expr;
string op;
Expr_node * opnd;
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
{
friend class Expr;
string op;
Expr_node *left;
Expr_node *right;
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<<")";
}
};
}
#endif

Expr.cpp

#include "expr.h"
using namespace Meditation;
ostream& operator<<(ostream & o,const Expr_node & e)
{
e.print(o);
return o;
}

上面的方法，有一个问题。用户处理的不是值而是指针，所以必须记住分配和释放对象。动态分配：

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

这里，我们必须记住删除这些节点，但是我们不再拥有指向内层new调用所构造出来的对象的指针了！如果通过Binary_node和Unary_node的析构函数删除它们的操作数，也不行，因为可能会多次删除对象，可能有不止一个Expr_node指向同一个下层的表达式树对象。

3. 句柄类

在Expr_node类族中，仅仅表示了图中的圆圈，而没有对箭头建模，正是因为这里把箭头简单的描述成指针，这些用户需要亲自操作指针。所以，类Expr应该是一种句柄类，表示一个边或者说该树结构根源一个边。由于用户关心的是树而不是树种的单个节点，可以用Expr来隐藏Expr_node的继承层次。在Expr中通过构造函数创建三种Expr_node,并且将这个对象的地址存储在创建中的Expr对象中。Expr类的用户就不会直接看到Expr_node 对象了。

class Expr {
friend class Expr_node;
friend ostream& operator<<(ostream&, const Expr&);
Expr_node* p;
public:
Expr(int);
Expr(const String&, Expr);
Expr(const String&, Expr, Expr);
Expr(const String&, Expr, Expr, Expr);
Expr(const Expr& t) { p = t.p; ++p->use; }//由于构造函数为Expr_node分配了内存，需要实现复制构造函数和赋值操作符管理下层的Expr_node
~Expr() { if (--p->use == 0) delete p; }
Expr& operator=(const Expr& t);
int eval() const { return p->eval(); }//新添加的，为了求表达式的值
};
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 String& op, Expr left, Expr middle, Expr right)
{
p = new Ternary_node(op, left, middle, right);
}

当Expr类复制一个Expr_node时，该Expr将其引用计数加1，当引用者为0，删除底层的Expr_node。

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& t)
{
t.p->print(o);
return o;
}

避免复制：让每一个Expr_node包含一个引用计数器，指明同时有多少个Expr指向同一个Expr_node,Expr和Expr_node类协同管理引用计数，当且仅当一个Expr_node的引用计数等于0，该节点才被删除。所以需要在Expr_node中加入引用计数，Expr类声明为友元，帮助管理计数。

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

更改每个派生自Expr_node的类，令其操作为私有，将Expr声明为友元，存储Expr。

class Binary_node: public Expr_node {
friend class Expr;
string op;
Expr left;
Expr right;
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 t = Expr("*", Expr("-", 5), Expr("+", 3, 4));

求表达式的值

cout << t << " = " << t.eval() << endl;

或者

t = Expr("*", t, t);

cout << t << " = " << t.eval() << endl;

需要在Expr类中添加函数，把求值传递给其指向的Expr_node。

int eval() const { return p->eval(); }

在Expr_node中添加一个虚函数。

class Expr_node {

protected:

virtual int eval() const = 0;

//其他和前面的相同

};

接着为每个派生自Expr_node的子类添加一个函数来实现求值运算。

Int_node最简单，直接返回其值即可。

int eval() const { return n; }

对于Unbry_node

int
Unary_node::eval() const
{
if (op == "-")
return -opnd.eval();//会调用Expr类的成员eval,然后再调用其指向的Expr_node的虚函数eval,调用到了实际类型的eval();
throw "error, bad op " + op + " in UnaryNode";
}

对Binary_node:

int
Binary_node::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 + " in BinaryNode";
}

现在可以对表达式进行求值。

int main()
{
Expr t = Expr("*", Expr("-", 5), Expr("+", 3, 4));
cout << t << " = " << t.eval() << endl;
cout << "((-5)*(3+4)) = -35" << endl;
t = Expr("*", t, t);
cout << t << " = " << t.eval() << endl;
cout << "(((-5)*(3+4))*((-5)*(3+4))) = 1225" << endl;
return 0;
}