表达式树介绍
对于数学运算来说,其本质是一个分层的递归结构。每一步计算都是一个操作符作用于相应操作对象, 其操作对象又可以是一个操作数或任意复杂的表达式。而树的递归结构正好用来表示这种表达式。
对于二元运算来说,可以很自然的联系到二叉树:以操作数(operand)作为叶节点,以操作符(operator)为其他节点,其中操作符的左右孩子是它的左右运算对象。以算数表达式(3+2*9)-6/4
为例,其转换为表达式树如下图所示:
二叉表达式树是最简单的情况,对于有三元或多元运算的情形,表达式树的节点会有多于两个孩子,即度大于3。这里我们只讨论二叉表达式树。
表达式树在常用于编译器设计中,作为对表达式进行语法分析的工具,能够对表达式进行有效的语法判断和求值。比如C#中的lamda表达式。
表达式树的创建
表达式树可以从输入表达式来创建。其中最简单的实现是通过后缀表达式来创建。其方法与计算后缀表达式结果类似:
- 利用栈存放叶子节点和子树,记栈为S1;
- 从左往右扫描后缀表达式,当读到一个操作数时,将其化为节点压入栈S1中;
- 当读到一个操作符时,将操作符化为节点作根,从栈中弹出两个节点作为左右孩子,生成子树并将子树根节点压入栈中;
- 当扫描完成,栈中剩下唯一一个节点就是表达式树的根。
表达式树的求值
表达式树利用递归,可以很自然的得出表达式的值。
表达式树的遍历
观察表达式树,我们可以很容易发现,对表达式树进行前序,中序,后序遍历,我们分别可以得到前缀,中缀,后缀表达式。
其中需要注意的差别仅在于二叉树表示中消除了括号。在中序遍历时需要将生成的中缀表达式加上括号:当根结点运算符优先级高于左子树或右子树根结点运算符时,相应左或右子树前就需要加括号。
示例代码如下:
#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:
//constructor
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);
}
};
最新评论
干饭啦,干饭啦
太棒了
你好看
好看
谢谢
好看
感谢
哈哈,有意思