表达式树及其实现

表达式树介绍

对于数学运算来说，其本质是一个分层的递归结构。每一步计算都是一个操作符作用于相应操作对象， 其操作对象又可以是一个操作数或任意复杂的表达式。而树的递归结构正好用来表示这种表达式。

对于二元运算来说，可以很自然的联系到二叉树：以操作数(operand)作为叶节点，以操作符(operator)为其他节点，其中操作符的左右孩子是它的左右运算对象。以算数表达式(3+2*9)-6/4为例，其转换为表达式树如下图所示：

二叉表达式树是最简单的情况，对于有三元或多元运算的情形，表达式树的节点会有多于两个孩子，即度大于3。这里我们只讨论二叉表达式树。

表达式树在常用于编译器设计中，作为对表达式进行语法分析的工具，能够对表达式进行有效的语法判断和求值。比如C#中的lamda表达式。

表达式树的创建

表达式树可以从输入表达式来创建。其中最简单的实现是通过后缀表达式来创建。其方法与计算后缀表达式结果类似：

1. 利用栈存放叶子节点和子树，记栈为S1；
2. 从左往右扫描后缀表达式，当读到一个操作数时，将其化为节点压入栈S1中；
3. 当读到一个操作符时，将操作符化为节点作根，从栈中弹出两个节点作为左右孩子，生成子树并将子树根节点压入栈中；
4. 当扫描完成，栈中剩下唯一一个节点就是表达式树的根。

表达式树的求值

表达式树利用递归，可以很自然的得出表达式的值。

表达式树的遍历

观察表达式树，我们可以很容易发现，对表达式树进行前序，中序，后序遍历，我们分别可以得到前缀，中缀，后缀表达式。

其中需要注意的差别仅在于二叉树表示中消除了括号。在中序遍历时需要将生成的中缀表达式加上括号：当根结点运算符优先级高于左子树或右子树根结点运算符时，相应左或右子树前就需要加括号。

示例代码如下：

#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);
    }
};