本文最后编辑于 前，其中的内容可能需要更新。
表达式树介绍
对于数学运算来说，其本质是一个分层的递归结构。每一步计算都是一个操作符作用于相应操作对象， 其操作对象又可以是一个操作数或任意复杂的表达式。而树的递归结构正好用来表示这种表达式。
对于二元运算来说，可以很自然的联系到二叉树：以操作数(operand)作为叶节点，以操作符(operator)为其他节点，其中操作符的左右孩子是它的左右运算对象。以算数表达式(3+2*9)-6/4为例，其转换为表达式树如下图所示：
二叉表达式树是最简单的情况，对于有三元或多元运算的情形，表达式树的节点会有多于两个孩子，即度大于3。这里我们只讨论二叉表达式树。
表达式树在常用于编译器设计中，作为对表达式进行语法分析的工具，能够对表达式进行有效的语法判断和求值。比如C#中的lamda表达式。
表达式树的创建
表达式树可以从输入表达式来创建。其中最简单的实现是通过后缀表达式来创建。其方法与计算后缀表达式结果类似：
- 利用栈存放叶子节点和子树，记栈为S1；
- 从左往右扫描后缀表达式，当读到一个操作数时，将其化为节点压入栈S1中；
- 当读到一个操作符时，将操作符化为节点作根，从栈中弹出两个节点作为左右孩子，生成子树并将子树根节点压入栈中；
- 当扫描完成，栈中剩下唯一一个节点就是表达式树的根。
表达式树的求值
表达式树利用递归，可以很自然的得出表达式的值。
表达式树的遍历
观察表达式树，我们可以很容易发现，对表达式树进行前序，中序，后序遍历，我们分别可以得到前缀，中缀，后缀表达式。
其中需要注意的差别仅在于二叉树表示中消除了括号。在中序遍历时需要将生成的中缀表达式加上括号：当根结点运算符优先级高于左子树或右子树根结点运算符时，相应左或右子树前就需要加括号。
示例代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| #include <cstring>
#include <string>
#include <vector>
#include <stack>
#include "./expression.h"
using namespace std;
class ExpressionTree {
public:
struct TreeNode {
string data_;
TreeNode* left_;
TreeNode* right_;
TreeNode(const string& data, TreeNode* left = NULL, TreeNode* right = NULL)
:data_(data), left_(left), right_(right) {}
};
private:
TreeNode* root_;
static void destroy(TreeNode* cur) {
if(cur) {
destroy(cur->left_);
destroy(cur->right_);
delete cur;
}
}
static int calc(int l, const string& op, int r) {
if(op == "#") {
return 0 - r;
} else if (op == "+") {
return l + r;
} else if (op == "-") {
return l - r;
} else if (op == "*") {
return l * r;
} else if (op == "/") {
return l / r;
}
return 0;
}
static int getVal(TreeNode* cur) {
if(!cur) return 0;
if(!cur->left_ && !cur->right_) {
return atoi(cur->data_.c_str());
}
int l = getVal(cur->left_);
int r = getVal(cur->right_);
return calc(l, cur->data_, r);
}
static void preOrder(TreeNode* cur, void (*f)(TreeNode*) = NULL) {
if(!cur || !f) return;
f(cur);
preOrder(cur->left_, f);
preOrder(cur->right_, f);
}
static void inOrder(TreeNode* cur, void (*f)(TreeNode*) = NULL) {
if(!cur || !f) return;
inOrder(cur->left_, f);
f(cur);
inOrder(cur->right_, f);
}
static void postOrder(TreeNode* cur, void (*f)(TreeNode*) = NULL) {
if(!cur || !f) return;
postOrder(cur->left_, f);
postOrder(cur->right_, f);
f(cur);
}
public:
ExpressionTree(): root_(NULL) {
}
~ExpressionTree() {
destroy(root_);
}
void createByPostOrder(const vector<string>& tokens) {
stack<TreeNode*> nodeStack;
for(size_t i(0); i < tokens.size(); ++i) {
const string& t = tokens[i];
TreeNode* n = new TreeNode(t);
if(!isOperator(t)) {
nodeStack.push(n);
} else if (t == "#") {
n->right_ = nodeStack.top();
nodeStack.pop();
nodeStack.push(n);
} else {
n->right_ = nodeStack.top();
nodeStack.pop();
n->left_ = nodeStack.top();
nodeStack.pop();
nodeStack.push(n);
}
}
this->root_ = nodeStack.top();
}
int getResult() {
return getVal(root_);
}
void preOrder(void (*f)(TreeNode*) = NULL) {
preOrder(root_, f);
}
void inOrder(void (*f)(TreeNode*) = NULL) {
inOrder(root_, f);
}
void postOrder(void (*f)(TreeNode*) = NULL) {
postOrder(root_, f);
}
};
|