表达式树

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <fstream>
using namespace std;
typedef int HNODE;
struct BinTreeNode{
    char op;
    double value;
    bool calculated;
    HNODE hNode_left;
    HNODE hNode_right;
    BinTreeNode(char c='\0',double v=0,bool flag=false,HNODE l=0,HNODE r=0):
        op(c),value(v),calculated(flag),hNode_left(l),hNode_right(r){}
    void setValue(double v){
        value=v;
    }
    double getValue(){
        return value;
    }
    void setCalculated(bool setter=true){
        calculated=setter;
    }
    bool isCalculated(){
        return calculated;
    }
    HNODE getHNode_left(){
        return hNode_left;
    }
    HNODE getHNode_right(){
        return hNode_right;
    }
    void setOperator(char c){
        op=c;
    }
    char getOperator(){
        return op;
    }
    friend ostream &operator<<(ostream &os,BinTreeNode &node){
        if(node.op=='\0'){
            os<<"((\""<<"^"<<","<<node.value<<"\"))";
        }
        else
            os<<"((\""<<node.op<<","<<node.value<<"\"))";
        return os;
    }
};

struct BinTree{
    HNODE hNode_root;
    vector<BinTreeNode> nodes;
    BinTree(){

        hNode_root=newNode(BinTreeNode('\0',0,true,0,0));
    }
    HNODE newNode(const BinTreeNode &node){
        HNODE hNode=nodes.size();
        nodes.push_back(node);
        return hNode;
    }
    void inOrder(HNODE hNode_current){
        if(!hNode_current)return ;
        inOrder(nodes[hNode_current].getHNode_left());
        cout<<hNode_current<<" ";
        inOrder(nodes[hNode_current].getHNode_right());
    }
    void inOrder(){
        inOrder(hNode_root);
    }
    friend ostream &operator<<(ostream &os,BinTree &tree){
        for(HNODE hNode=1;hNode<tree.nodes.size();++hNode){
            os<<hNode<<tree.nodes[hNode]<<endl;
        }
        HNODE hNode_current;
        HNODE hNode_next;
        queue<HNODE>q;
        q.push(tree.hNode_root);
        while(!q.empty()){
            hNode_current=q.front();
            q.pop();
            hNode_next=tree.nodes[hNode_current].getHNode_left();
            if(hNode_next){
                os<<hNode_current<<"----"<<hNode_next<<endl;
                q.push(hNode_next);
            }
            hNode_next=tree.nodes[hNode_current].getHNode_right();
            if(hNode_next){
                os<<hNode_current<<"----"<<hNode_next<<endl;
                q.push(hNode_next);
            }
        }
        return os;
    }
};
enum Error_Type{
    NONE_ERROR,
    ERR_DIV_ZERO,
    ERR_DISMATCH_RBRACKET,
    ERR_MULTIPLE_DOT

};

static string SError_Type[]{
    "NONE_ERROR",
    "ERR_DIV_ZERO",
    "ERR_DISMATCH_RBRACKET",
    "ERR_MULTIPLE_DOT"
};


struct ExpressionTree:public BinTree{
    string expression;
    int pos;
    Error_Type error;
    ExpressionTree(){
        pos=0;
        expression="";
        error=NONE_ERROR;
    }
    double getValue(HNODE hNode_current){
        BinTreeNode &node=nodes[hNode_current];
        if(node.isCalculated()){
            return node.getValue();
        }
        node.setCalculated();
        switch(node.getOperator()){
            case '\0':
                break;
            case '+':
                node.setValue(getValue(node.getHNode_left())+getValue(node.getHNode_right()));
                break;
            case '-':
                node.setValue(getValue(node.getHNode_left())-getValue(node.getHNode_right()));
                break;
            case '*':
                node.setValue(getValue(node.getHNode_left())*getValue(node.getHNode_right()));
                break;
            case '/':
                node.setValue(getValue(node.getHNode_left())/getValue(node.getHNode_right()));
                break;
        }
        return node.getValue();
    }
    double getValue(){
        return getValue(hNode_root);
    }
    double operator()(const string &exp){
        pos=0;
        expression="";
        error=NONE_ERROR;
        nodes.resize(0);
        hNode_root=newNode(BinTreeNode('\0',0,true,0,0));
        expression=filter(exp);
        hNode_root=evalExpression();
        return getValue(hNode_root);
    }
    HNODE evalExpression(){
        HNODE hNode_current;
        HNODE hNode_term;
        HNODE hNode_history;
        char op;
        hNode_term=evalTerm();
        if(error){
            return 0;
        }
        hNode_current=hNode_term;
        while(!end()){
            op=expression[pos];
            if(op!='+'&&op!='-'){
                return hNode_current;
            }
            ++pos;
            hNode_term=evalTerm();
            if(error){
                return 0;
            }
            hNode_history=hNode_current;
            hNode_current=newNode(BinTreeNode(op,0,false,hNode_history,hNode_term));
        }
        return hNode_current;
    }
    HNODE evalTerm(){
        HNODE hNode_current;
        HNODE hNode_factor;
        HNODE hNode_history;
        char op;
        hNode_factor=evalFactor();
        if(error){
            return 0;
        }
        hNode_current=hNode_factor;
        while(!end()){
            op=expression[pos];
            if(op!='*'&&op!='/'){
                return hNode_current;
            }
            ++pos;
            hNode_factor=evalFactor();
            if(error){
                return 0;
            }
            hNode_history=hNode_current;
            hNode_current=newNode(BinTreeNode(op,0,false,hNode_history,hNode_factor));
        }
        return hNode_current;
    }
    HNODE evalFactor(){
        HNODE hNode_current;
        HNODE hNode_history;
        if(expression[pos]=='('){
            ++pos;
            hNode_current=evalExpression();
            if(error){
                return 0;
            }
            if(expression[pos]!=')'){
                error=ERR_DISMATCH_RBRACKET;
                return 0;
            }
            ++pos;
        }
        else if(expression[pos]=='-'){
            ++pos;
            hNode_history=evalFactor();
            if(error){
                return 0;
            }
            hNode_current=newNode(BinTreeNode('-',0,false,0,hNode_history));
        }
        else if(isdigit(expression[pos])){
            hNode_current=evalID();
            if(error){
                return 0;
            }
        }

        return hNode_current;
    }
    HNODE evalID(){
        bool dot_flag=false;
        string buffer;
        while(!end()){
            if(expression[pos]!='.'&&!isdigit(expression[pos])){
                break;
            }
            else if(expression[pos]=='.'){
                if(dot_flag){
                    error=ERR_MULTIPLE_DOT;
                    return 0;
                }
            }
            buffer+=expression[pos];
            ++pos;
        }
        return newNode(BinTreeNode('\0',stod(buffer),true,0,0));
    }
    bool end()
    {
        return expression[pos] == '\0';
    }

    string filter(const string &exp)
    {
        string text;
        for (auto c : exp)
        {
            if(isdigit(c)||c=='.'||c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'){//过滤输入,只允许特定的运算符,数字,小数点进入expression
                text+=c;
            }
        }
        return text;
    }
    void what(){
        if(error){
            cout<<SError_Type[error]<<endl;
        }
        else{
            cout<<"construction complete"<<endl;
        }
    }
    friend ostream &operator<<(ostream &os,ExpressionTree &tree){//打印树的样子
        for(HNODE hNode=1;hNode<tree.nodes.size();++hNode){
            os<<hNode<<tree.nodes[hNode]<<endl;
        }
        HNODE hNode_current;
        HNODE hNode_next;
        queue<HNODE>q;
        q.push(tree.hNode_root);
        while(!q.empty()){
            hNode_current=q.front();
            q.pop();
            hNode_next=tree.nodes[hNode_current].getHNode_left();
            if(hNode_next){
                os<<hNode_current<<"----"<<hNode_next<<endl;
                q.push(hNode_next);
            }
            hNode_next=tree.nodes[hNode_current].getHNode_right();
            if(hNode_next){
                os<<hNode_current<<"----"<<hNode_next<<endl;
                q.push(hNode_next);
            }
        }
        return os;
    }
    bool outFile(string filepath){//将mermaid作图输出到文件
        ofstream fout(filepath.c_str(),ios::app);//前面的不删除,附加打开
        if(fout.is_open()==false){
            cout<<"error filepath"<<endl;
            return false;
        }
        streambuf *oldcout=cout.rdbuf(fout.rdbuf());
        if(error){
            cout<<SError_Type[error];

        }
        else{
            cout<<"## `"<<expression<<"`"<<endl;//给一个二级标题
            cout<<"```mermaid"<<endl;
            cout<<"graph"<<endl<<endl;
            cout<<(*this)<<endl;
            cout<<"```"<<endl;
        }
        // cout.close();
        cout.rdbuf(oldcout);
        fout.close();
        return true;

    }
};


int main(){
    ExpressionTree tree;
    string expression;
    while(true){
        cout<<">";
        cin>>expression;
        if(expression=="q"){
            break;
        }
        cout<<tree(expression)<<endl;
        tree.outFile("tree.md");//本次建树附加到tree.md最后面

    }

    return 0;
}