在学习完堆栈数据结构后，我们很容易两个利用具有LIFO特性的栈——操作数栈、操作符栈实现中缀表达式向后缀表达式的转换，而后缀表达式也只用借助一个操作数栈便可快速求值。

但书上一幅有关表达式树的图片引起了我的注意，我们要如何实现这样的表达式树呢？一顿操作之后按照这篇实现JavaScript的eval()的表达式树教程实现了C++的表达式解析。下面附上我对此js代码的C++复刻版。

//
// Created by Zilin Xiao on 2019/10/17.
//

#include<string>
#include<stack>
#include<vector>
#include<cmath>
#include<iostream>

enum TokenType {UNDEFINED, OPERATOR, INT , DOUBLE}; // 四种Token类型
enum NodeType {OPER, OPRAND}; // 两种树节点类型

using std::string, std::vector, std::stack;

class Token{
public:
    string value;
    TokenType tag;
    Token(string _value, TokenType _tag):value(std::move(_value)), tag(_tag){};
};

class TokenReader{ // 模仿Reader写的TokenReader(羡慕js
protected:
    vector<Token> seq;
    int cur;
    int length;
public:
    TokenReader(vector<Token> input){
        seq = input;
        cur = 0;
        length = input.size();
    }
    Token next(){
        return this->seq[cur++];
    }
    Token prev(){
        return this->seq[cur--];
    }
    Token curr(){
        return this->seq[cur];
    }
    bool has_next(){
        return cur < length;
    }
    Token peek(){
        return this->seq[cur+1];
    }
};

class Reader{
protected:
    string seq;
    int cur;
    int length;
public:
    explicit Reader(string input){
        seq = input;
        cur = 0;
        length = input.size();
    }
    char next(){
        return this->seq[cur++];
    }
    char prev(){
        return this->seq[cur--];
    }
    char curr(){
        return this->seq[cur];
    }
    bool has_next(){
        return cur < length;
    }
    char peek(){
        return this->seq[cur+1];
    }

};

class Lexer{  // 简单的词法分析器
public:
    vector<Token> token_list;
protected:
    Reader* reader;
    Token lastToken(){
        if (token_list.size()>0)
            return token_list[token_list.size()-1];
        else return Token("", UNDEFINED);
    }
    static bool isDigit(char x){
        return x>='0' && x<='9';
    }
    static bool isEscape(char x){
        return x==' ' || x=='\n' || x=='\t';
    }
    static bool isOperator(char op){
        const char ops[] = {'+', '*','-', '/', '%',
        '&', '|', '^', '<', '>', '~', '(',')'}; // 长于一个字符的符号不在此判断
        for (int i = 0; ops[i]!='\0'; ++i) {
            if(op==ops[i]) return true;
        }
        return false;
    }
    Token readNum(){ // 读取数字
        Token ans("", INT);
        while(((reader->has_next() && isDigit(reader->curr()))
        || reader->curr() == '.' || isEscape(reader->curr()))){
            if(isEscape(reader->curr())){
                reader->next();
                continue;
            }
            ans.value += reader->next();
        }

        if(reader->has_next() && reader->curr() == 'e'
        && (reader->peek() == '-' || reader->peek() == '+')){
            string s1(1, reader->next());
            string s2(1, reader->next());
            ans.value += s1+s2;
            while(reader->has_next() && isDigit(reader->curr())){
                ans.value += reader->next();
            }
        }
        if(ans.value.find('.')!=string::npos || ans.value.find("e-")!=string::npos){
            ans.tag = DOUBLE;
        }
        return ans;
    }

    void parse(){
        while(reader->has_next()){
            char cur = reader->next();
            if(isEscape(cur)) continue;
            if(isDigit(cur)){
                reader->prev();
                Token num = readNum();
                token_list.push_back(num);
            }else if(isOperator(cur)){
                TokenType prev_tag = lastToken().tag;
                if(cur == '-'){ // 当遇见“-”， 可能是负数或者减法
                    if(prev_tag!=UNDEFINED && (prev_tag==INT || prev_tag == DOUBLE || lastToken().value == ")")){ // 前一个数是数字，当做运算符
                        string tmpCur(1,cur);
                        Token tmpToken(tmpCur, OPERATOR);
                        token_list.push_back(tmpToken);
                    }else{
                        Token num = readNum();
                        string tmpCur(1,cur);
                        tmpCur += num.value;
                        Token tmpToken(tmpCur, num.tag);
                        token_list.push_back(tmpToken);
                    }
                }
                else if(cur == '~'){
                    Token num = readNum();
                    string tmpCur(1,cur);
                    Token tmpToken(tmpCur+num.value, INT);
                    token_list.push_back(tmpToken);
                }
                else if((cur == '*' || cur == '<' || cur == '>') && reader->has_next() && reader->curr() == cur){
                    string tmpCur(1,cur);
                    string curr = tmpCur + reader->next();
                    Token tmpToken(curr, OPERATOR);
                    token_list.push_back(tmpToken);
                }
                else{ // 无需特殊处理的符号
                    string tmpCur(1,cur);
                    Token tmpToken(tmpCur, OPERATOR);
                    token_list.push_back(tmpToken);
                }
            }else{
                throw "Unidentified Character: " + std::to_string(cur);
            }
        }
    }

public:
    Lexer(string input_expression){
        reader = new Reader(input_expression);
        parse();
    }
};

template <class ElemType>
class Node{
public:
    virtual ElemType eval(){};
    virtual int id(){
        return -1;
    }
};

template <class ElemType>
class ConstNode : public Node<ElemType>{
protected:
    TokenType type;
    ElemType value;

public:
    ConstNode(string _c, TokenType _t){
        Node<ElemType>();
        c = _c;
        type = _t;
    }
    ElemType eval(){
        if(type == INT){
            value = atoi(c.c_str());
        }else if(type == DOUBLE){
            value = atof(c.c_str());
        }
        return value;
    }
    int id(){
        return OPRAND;
    }

    string c;
};

template <class ElemType>
class OperatorNode : public Node<ElemType>{
public:
    string op;
    Node<ElemType>* fi, *se;
    OperatorNode(string _op, Node<ElemType> *_fi, Node<ElemType> *_se){
        op = _op;
        fi = _fi;
        se = _se;
    }
    ElemType eval(){
        if(op == "+") return this->fi->eval() + this->se->eval();
        else if(op == "-") return this->fi->eval() - this->se->eval();
        else if(op == "*") return this->fi->eval() * this->se->eval();
        else if(op == "/") return this->fi->eval() / this->se->eval();
        else if(op == "%") return this->fi->eval() % this->se->eval();
        else if(op == "**") return pow(this->fi->eval(), this->se->eval());
        else if(op == "<<") return this->fi->eval() << this->se->eval();
        else if(op == ">>") return this->fi->eval() >> this->se->eval();
        else if(op == "&") return this->fi->eval() & this->se->eval();
        else if(op == "|") return this->fi->eval() | this->se->eval();
        else if(op == "^") return this->fi->eval() ^ this->se->eval();
        else throw "No Such Operator!";
    }
    int id(){
        return OPER;
    }
};

template <class ElemType>
class TreeBuilder{
protected:
    TokenReader *tokenReader;
    stack<string> opStack;
    stack<Node<ElemType>* > numStack;

    void addNode(){
        ConstNode<ElemType> *se = static_cast<ConstNode<ElemType> *>(numStack.top());
        numStack.pop();
        auto *fi = new ConstNode<ElemType>("0", INT);
        if(!numStack.empty()){
            delete fi;
            fi = static_cast<ConstNode<ElemType> *>(numStack.top());
            numStack.pop();
        }
        string op = opStack.top();
        opStack.pop();
        numStack.push(new OperatorNode<ElemType>(op, fi, se));
    }

public:
    explicit TreeBuilder(vector<Token> &tokenList){
        tokenReader = new TokenReader(tokenList);
    }
    Node<ElemType>* buildTree(){
        while(tokenReader->has_next()){
            Token cur = tokenReader->next();

            switch(cur.tag){
                case INT: // Don't Know How to Deal With Different DataType   Leave it temporarily
                // C++菜鸡并不会处理在STL容器中插入不同类型元素
                case DOUBLE:
                    numStack.push(new ConstNode<ElemType>(cur.value, cur.tag));
                    break;
                case OPERATOR:
                    if(cur.value == "(")
                        opStack.push("(");
                    else if (cur.value == ")"){
                        while(!opStack.empty() && opStack.top() != "("){
                            addNode();
                        }
                        opStack.pop();
                    }else if(cur.value == "%" || cur.value == "**"){
                        while(!opStack.empty() && opStack.top() == cur.value){
                            addNode();
                        }
                        opStack.push(cur.value);
                    }else if(cur.value == "*" || cur.value == "/"){
                        while(!opStack.empty() && opStack.top() == "*" && opStack.top() == "/"){
                            addNode();
                        }
                        opStack.push(cur.value);
                    }else if(cur.value == "+" || cur.value == "-"){
                        while(!opStack.empty() && opStack.top() != "(" &&
                                opStack.top() != "|"
                                && opStack.top() != "&" && opStack.top() != "^"){
                            addNode();
                        }
                        opStack.push(cur.value);
                    }
                    else if(cur.value == "|" || cur.value == "&" ||
                        cur.value == "^" ||cur.value == "<<" || cur.value == ">>"){
                        while(!opStack.empty() && opStack.top() != "("){
                            addNode();
                        }
                        opStack.push(cur.value);
                    }else{
                        throw "Undefined Operator!";
                    }
                case UNDEFINED:
                    // For Debug
                    break;
            }
        }
        while(!opStack.empty()){
            addNode();
        }
        if(numStack.size() == 1) return numStack.top();
        else throw "Error Expression!";
    }

};


template <class Type>
class ExpressionTree{
protected:
    void DisplayHelp(Node<Type> *r, int level);
public:
    Node<Type> *root;
    ExpressionTree(){
        root = nullptr;
    }
    void Display(){
        DisplayHelp(root, 1);
        std::cout<<std::endl;
    }
};

template<class Type>
void ExpressionTree<Type>::DisplayHelp(Node<Type> *r, int level) {
    if(r != nullptr){
        if(r->id() == OPER){
            auto rop = static_cast<OperatorNode<Type> *>(r); // 强制类型提升
            DisplayHelp(rop->fi, level+1);
            std::cout<<std::endl;
            for (int i = 0; i < level - 1; ++i) {
                std::cout<<" ";
            }
            std::cout<<rop->op;
            DisplayHelp(rop->se, level + 1);
        }else if(r->id() == OPRAND){
            auto rk = static_cast<ConstNode<Type> *>(r);
            std::cout<<std::endl;
            for (int i = 0; i < level - 1; ++i) {
                std::cout<<" ";
            }
            std::cout<<rk->c;
        }
    }
}
// 测试代码
int main(){
    try{
        Lexer lTest("(1+2)*3");
        TreeBuilder<int> tBuilder(lTest.token_list);
        ExpressionTree<int> t;
        t.root = tBuilder.buildTree();
        std::cout<<t.root->eval()<<std::endl;
        std::cout<<std::endl;
        t.Display();
    }catch(const char* msg){
        std::cout<<msg<<std::endl;
    }
    return 0;
}

效果：