文章目录
何为表达式树
1
上图就是一个表达式树（手动滑稽）
下面我会给出把中缀表达式（字符串）转化成表达式树的代码
表达式树实现
作为二叉树的一个应用，这里就用二叉树这种数据结构来实现~
这里有一个重要的知识点，在利用指针实现的二叉树中，叶节点（叶结点）与非叶节点是否使用相同的定义十分重要。使用相同的类可以简化实现，但是可能导致空间上的浪费。
有一些应用只需要叶结点存储数据，还有一些应用要求分支结点（非叶节点）与叶结点存储不同类型的数据。
代码（1）用同样的方式实现叶子节点和非叶节点
代码（2）用不同的方式实现叶子节点和非叶节点
（感觉（1）不好理解的话可以先看（2））
（1）
// Node implementation with simple inheritance
class VarBinNode { // Node base class基类
public:
virtual ˜VarBinNode() {}
virtual bool isLeaf() = 0; // Subclasses must implement
};
class LeafNode : public VarBinNode { // Leaf node叶子结点
private:
Operand var; // Operand value
public:
LeafNode(const Operand& val) { var = val; } // Constructor
bool isLeaf() { return true; } // Version for LeafNode
Operand value() { return var; } // Return node value
};
class IntlNode : public VarBinNode { // Internal node非叶子结点
private:
VarBinNode* left; // Left child
VarBinNode* right; // Right child
Operator opx; // Operator value
public:
IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r)
{ opx = op; left = l; right = r; } // Constructor
bool isLeaf() { return false; } // Version for IntlNode
VarBinNode* leftchild() { return left; } // Left child
VarBinNode* rightchild() { return right; } // Right child
Operator value() { return opx; } // Value
};
void traverse(VarBinNode *root) { // Preorder traversal
if (root == NULL) return; // Nothing to visit
if (root->isLeaf()) // Do leaf node
cout << "Leaf: " << ((LeafNode *)root)->value() << endl;
else { // Do internal node
cout << "Internal: "
<< ((IntlNode *)root)->value() << endl;
traverse(((IntlNode *)root)->leftchild());
traverse(((IntlNode *)root)->rightchild());
} }
（2）
#include<iostream>
using namespace std;
#define Operand char
#define Operator char
//Node implementation with the composite design pattern 复合设计模式
class VarBinNode { //Node base class 基类
public:
virtual ~VarBinNode(){}
virtual bool isLeaf() = 0;
virtual void traverse() = 0;
};
class LeafNode :public VarBinNode { //Leaf node 叶子结点
private:
Operand var; //Operand value 运算数
public:
LeafNode(const Operand& val) { var = val; }
bool isLeaf() { return true; }
Operand value() { return var; } //Return node value
void traverse() { //叶子结点的遍历
cout << "Leaf:" << value() << endl;
}
};
class IntlNode :public VarBinNode { //Internal node 非叶子节点
private:
VarBinNode* lc; //Left child 左孩子
VarBinNode* rc; //Right child 右孩子
Operator opx; //Operator value 运算符号
public:
IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r) {
opx = op; lc = l; rc = r;
}
bool isLeaf() { return false; }
VarBinNode* left() { return lc; } //Return left child左孩子
VarBinNode* right() { return rc; } //Return right child右孩子
Operator value() { return opx; } //Return operator value 运算符号
void traverse() { //非叶子结点的遍历
cout << "Internal:" << value() << endl;
if (left() != NULL)left()->traverse();
if (right() != NULL)right()->traverse();
}
};
//Do a preorder traversal先序遍历
void traverse(VarBinNode* root) {
if (root != NULL)root->traverse();
}
之后再用上面任意一种完成表达式树的构建（这里用（2））
#include<iostream>
using namespace std;
#define Operand char
#define Operator char
//Node implementation with the composite design pattern 复合设计模式
class VarBinNode { //Node base class 基类
public:
virtual ~VarBinNode() {}
virtual bool isLeaf() = 0;
virtual void traverse() = 0;
};
class LeafNode :public VarBinNode { //Leaf node 叶子结点
private:
Operand var; //Operand value 运算数
public:
LeafNode(const Operand& val) { var = val; }
bool isLeaf() { return true; }
Operand value() { return var; } //Return node value
void traverse() { //叶子结点的遍历
cout << "Leaf:" << value() << endl;
}
};
class IntlNode :public VarBinNode { //Internal node 非叶子节点
private:
VarBinNode* lc; //Left child 左孩子
VarBinNode* rc; //Right child 右孩子
Operator opx; //Operator value 运算符号
public:
IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r) {
opx = op;lc = l; rc = r;
}
bool isLeaf() { return false; }
VarBinNode* left() { return lc; } //Return left child左孩子
VarBinNode* right() { return rc; } //Return right child右孩子
Operator value() { return opx; } //Return operator value 运算符号
void traverse() { //非叶子结点的遍历
cout << "Internal:" << value() << endl;
if (left() != NULL)
left()->traverse();
if (right() != NULL)
right()->traverse();
}
};
//Do a preorder traversal先序遍历
void traverse(VarBinNode* root) {
if (root != NULL)root->traverse();
}
class Expressiontree { //表达式树
private:
VarBinNode* Root; //Tree root 树根
public:
Expressiontree(Operand op) { //Leaf constructor 叶子结点的构造函数
Root = new LeafNode(op);
}
//Intlnode constructor 非叶子节点的构造函数
Expressiontree(const Operator& op, Expressiontree* l, Expressiontree* r) {
Root = new IntlNode(op, l->Root, r->Root);
}
Expressiontree(VarBinNode*& node) {
Root = node;
}
void traversetree() { //遍历表达式树
traverse(Root);
}
VarBinNode* getRoot() { //获取树根结点
return Root;
}
~Expressiontree(){}
};
Expressiontree* buildtree(string s, int l, int r) {
//在创建树的时候，如果孩子节点为空，让它指向emptynode节点
if (r < l)
return NULL;
//上面这个判断条件没有必要，因为不会出现这种情况，除非错误输入，比如只输入了: "()"或者"2+"
int c1 = -1, c2 = -1;
int flag = 0;
if (r == l) { //叶子结点
return new Expressiontree(s[r]);
}
for (int i = l; i <= r; ++i) {
if (s[i] == '(')
++flag;
else if (s[i] == ')')
--flag;
else if (s[i] == '+' || s[i] == '-') {
if (flag == 0) { //说明这里的加减号在括号外，可以拿来做根结点
c1 = i;
}
}
else if (s[i] == '*' || s[i] == '/') {
if (flag == 0) {
c2 = i;
}
}
}
if (c1 < 0)c1 = c2; //如果括号外面没有加减号，用乘除号代替
if (c1 < 0)return buildtree(s, l + 1, r - 1);
Expressiontree* left = buildtree(s, l, c1 - 1);
Expressiontree* right = buildtree(s, c1 + 1, r);
Expressiontree* op = new Expressiontree(s[c1], left, right);
return op;
}
void deletetree(IntlNode*tree) { //删除表达式树，释放空间
if (tree->left() != NULL) {
if (tree->left()->isLeaf() == false) {
deletetree((IntlNode*)tree->left());
}
else
delete tree->left();
}
if (tree->right() != NULL) {
if (tree->right()->isLeaf() == false) {
deletetree((IntlNode*)tree->right());
}
else
delete tree->right();
}
delete tree;
}
int main() {
string expression = "4*x*(2*x+a)-c";
//构建表达式树
Expressiontree* expressiontree = buildtree(expression, 0, expression.size() - 1);
expressiontree->traversetree(); //遍历表达式树
deletetree((IntlNode*)expressiontree->getRoot()); //释放空间
}
然后有两个概念需要提及：
接着，还是这个图，
1
后序遍历（先左后右再根）就可以得到我们想要的后缀表达式
（2）代码 ：先序遍历结果
2
后序遍历代码：（在（2）基础上加了一个traverse2()方法）
#include<iostream>
using namespace std;
#define Operand char
#define Operator char
//Node implementation with the composite design pattern 复合设计模式
class VarBinNode { //Node base class 基类
public:
virtual ~VarBinNode() {}
virtual bool isLeaf() = 0;
virtual void traverse() = 0; //用来先序遍历
virtual void traverse2() = 0; //用来后序遍历
};
class LeafNode :public VarBinNode { //Leaf node 叶子结点
private:
Operand var; //Operand value 运算数
public:
LeafNode(const Operand& val) { var = val; }
bool isLeaf() { return true; }
Operand value() { return var; } //Return node value
void traverse() { //叶子结点的遍历
cout << "Leaf:" << value() << endl;
}
void traverse2() { //叶子结点的遍历
cout << "Leaf:" << value() << endl;
}
};
class IntlNode :public VarBinNode { //Internal node 非叶子节点
private:
VarBinNode* lc; //Left child 左孩子
VarBinNode* rc; //Right child 右孩子
Operator opx; //Operator value 运算符号
public:
IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r) {
opx = op;lc = l; rc = r;
}
bool isLeaf() { return false; }
VarBinNode* left() { return lc; } //Return left child左孩子
VarBinNode* right() { return rc; } //Return right child右孩子
Operator value() { return opx; } //Return operator value 运算符号
void traverse() { //非叶子结点的遍历
cout << "Internal:" << value() << endl;
if (left() != NULL)
left()->traverse();
if (right() != NULL)
right()->traverse();
}
void traverse2() { //非叶子结点的遍历
if (left() != NULL)left()->traverse2();
if (right() != NULL)right()->traverse2();
cout << "Internal:" << value() << endl;
}
};
//Do a preorder traversal先序遍历
void traverse(VarBinNode* root) {
if (root != NULL)root->traverse();
}
//Do a postorder traversal后序遍历
void traverse2(VarBinNode* root) {
if (root != NULL)root->traverse2();
}
class Expressiontree { //表达式树
private:
VarBinNode* Root; //Tree root 树根
public:
Expressiontree(Operand op) { //Leaf constructor 叶子结点的构造函数
Root = new LeafNode(op);
}
//Intlnode constructor 非叶子节点的构造函数
Expressiontree(const Operator& op, Expressiontree* l, Expressiontree* r) {
Root = new IntlNode(op, l->Root, r->Root);
}
Expressiontree(VarBinNode*& node) {
Root = node;
}
void traversetree() { //遍历表达式树，先序
traverse(Root);
}
void traversetree2() { //遍历表达式树，后序
traverse2(Root);
}
VarBinNode* getRoot() { //获取树根结点
return Root;
}
~Expressiontree(){}
};
Expressiontree* buildtree(string s, int l, int r) {
//在创建树的时候，如果孩子节点为空，让它指向emptynode节点
if (r < l)
return NULL;
//上面这个判断条件没有必要，因为不会出现这种情况，除非错误输入，比如只输入了: "()"或者"2+"
int c1 = -1, c2 = -1;
int flag = 0;
if (r == l) { //叶子结点
return new Expressiontree(s[r]);
}
for (int i = l; i <= r; ++i) {
if (s[i] == '(')
++flag;
else if (s[i] == ')')
--flag;
else if (s[i] == '+' || s[i] == '-') {
if (flag == 0) { //说明这里的加减号在括号外，可以拿来做根结点
c1 = i;
}
}
else if (s[i] == '*' || s[i] == '/') {
if (flag == 0) {
c2 = i;
}
}
}
if (c1 < 0)c1 = c2; //如果括号外面没有加减号，用乘除号代替
if (c1 < 0)return buildtree(s, l + 1, r - 1);
Expressiontree* left = buildtree(s, l, c1 - 1);
Expressiontree* right = buildtree(s, c1 + 1, r);
Expressiontree* op = new Expressiontree(s[c1], left, right);
return op;
}
void deletetree(IntlNode*tree) { //删除表达式树，释放空间
if (tree->left() != NULL) {
if (tree->left()->isLeaf() == false) {
deletetree((IntlNode*)tree->left());
}
else
delete tree->left();
}
if (tree->right() != NULL) {
if (tree->right()->isLeaf() == false) {
deletetree((IntlNode*)tree->right());
}
else
delete tree->right();
}
delete tree;
}
int main() {
string expression = "4*x*(2*x+a)-c";
//构建表达式树
Expressiontree* expressiontree = buildtree(expression, 0, expression.size() - 1);
expressiontree->traversetree2(); //遍历表达式树
deletetree((IntlNode*)expressiontree->getRoot()); //释放空间
}
后序遍历结果：
3
---------------------------
表达式树优化
代码优化：
在非叶节点traverse()方法中，我们看到每次递归遍历前，都要判断左右子节点是否为空，当树的深度增加时，这造成的时间开销是呈指数增长的，因此我们最好把这两个判断条件给去掉。
（不过因为这里情况特殊，即我们的表达式树一定是一个满二叉树（二元运算符肯定对应了两个操作数），所以可以大胆地去掉判断条件，不过这样还是不好，如果我们的输入出现差错，就有可能导致程序崩溃，因为使用了空指针）
Reference
《数据结构与算法分析（C++版）（第三版）》P103
《数据结构与算法分析（C++版）（第三版）》P104,P105
