用C++实现输入自定义公式字符串程序返回计算结果的功能(AST)

主流程图如下：

String

输入的自定义公式字符串。

Lexer

词法分析，识别输入的字符串，遍历String的每个字符，将字符串按照类型TokenType拆分成各个独立的部分，存在Vector中。

enum TokenType{
    ADD,                 //        +
    SUB,                 //        -
    MUL,                 //        *
    DIV,                 //        /
    SEC_BEGIN,           //        (
    SEC_END,             //        )
    NUM,                 //        数字
    ID,                  //        字符串
    COMMA                //        ,
};

Token

存放字符串解析后的记号对象

typedef struct Token     //        记号类
{
    std::string value;
    TokenType    tt;
} Token ;

Parser

语法分析，遍历vector<Token> tokens元素，解析每一个token，按照对应的类型构造出相应的节点类，按照对应的语法放在相应的位置上，生成一个具有语法关系的二叉树（解析树），并返回根节点。

实现过程：

• 首先最顶层仍然是+法，因为它的优先级最低，树的层次越低代表计算优先级越高。文法实现方法是:expr()调用term()，term()调用factor()。

• factor(): 它的作用是识别数字，字符串，和 ()。

  （1）.如果是数字：直接构造NumNode节点。

  （2）.如果是字符串：判断下一个Token是否是(，

  • 如果是：则为自定义方法名，构造FunNode节点，并继续解析后面()内的参数，构造ArgsNode节点，并set到FunNode节点的子节点上。

  • 如果不是：则为自定义别名，直接构造IDNode节点。

  （3）.如果是 ()：则表示括号内是一个完整的表达式（子树），递归调用exper()方法作为一个新的子树重头解析，并将这个新子树的根节点返回链接到它的上一个节点上。至于返回的子树是左还是右，则取决于它的上层调用单元term()。

• term()：作用是识别乘除，我们可以通过它来返回一个子树，至于返回的子树是左还是右，则取决于它的上层调用单元expr()。

​ 如果匹配到乘除符号，则构造BinaryExpNode节点，并添加这个节点的左右子树。右子树调用factor()方法来生成，

​ 左子树会通过递归调用term()方法来生成。如果一直有乘除号，则一直向下生成新的子树节点。
3.

• expr()：它的作用是识别加减。它主要用来组装term()返回的子树，作为最顶层的结构，最终生成整个树的根节点。

​ 如果匹配到加减符号，则构造BinaryExpNode节点，并添加这个节点的左右子树。右子树调用term()方法来生成，

​ 左子树会通过递归调用expr()方法来生成。如果一直有加减号，则一直向下生成新的子树节点。

算术表达式”2*7+3″的解析树:

再来看一下算术表达式“7 +（（2 + 3））”的解析树：

Tree

解析树，ASTNode是根节点。

class ASTNode{
protected:
    Token token;
    ASTNodeGC* _scope;
public:
    ASTNode(Token t,ASTNodeGC* scope);
    virtual void AddLeft(ASTNode* node);
    virtual void AddRight(ASTNode* node);
    virtual Rational exec(IDataProvider* idp, IFuncProvider* ifp) =0;
    virtual ~ASTNode();
    virtual void releseScope();
};

• ASTNode ：节点基类，所有类型的节点都继承这个类，构造的时候，会调用add_to_gc(this)方法将这个对象加入ASTNodeGC集合里。

• ASTNodeGC ：用来存放所有节点对象的集合，用来析构的时候释放动态内存申请的节点类对象。

• NumNode ：数字节点类，构造的时候会将对应的字符串转换为数字存在成员变量_value中。

• IDNode ：字符串节点类。

• BinaryExpNode ：四则运算节点类，实现了AddLeft()和AddRight()方法，如果是这个运算符类型的节点对象，则会寻找它的左右节点，作为他的子树添加进去。

• ArgsNode ：自定义函数的参数节点类，实现了两个方法，
  addExpr() ：添加第一个参数的节点。

  addRestArgs()：如果有大于1个的参数，则递归解析添加节点，GoAhead()解析下一个参数，直到解析到NULL。

  参数节点树见下图：
  

• FuncNode ：自定义函数的节点类，实现addArgs()方法，用来添加参数。

Exec

自定义的别名和方法写在IDataProvider::get_date_by_name和IFuncProvider::call_func()里面。

用根节点调用方法exec(IDataProvider* idp,IFuncProvider* ifp)，则可以通过递归的方式来遍历我们前面生成的语法树结构Tree，从优先级最低的最底部开始计算，一层层往上推导，直到执行到根节点算出来结果，然后返回。执行到每一个节点的时候，由于虚函数的动态绑定，会分别调用各子类实现的exec方法，从而自动推导出结果。

• NumNode::exec()： 直接返回_value

• IDNode::exec()： 调用我们自定义的方法来取值get_date_by_name()

• BinaryExpNode::exec()： 如果识别到四则运算节点，则会递归调用其子节点，直到子节点变成叶返回。我们需要在将操作符应用到子节点中的操作数之前，先获取子节点中操作符节点的运算结果。

  例如，算术表达式”2*7+3″的解析树中，“*“是””+“的子节点，我们如果想让”+“完成运算，它的前提是”*”的节点已经有了运算结果。
  
  四则运算节点的exec递归方法：

  Rational BinaryExpNode::exec(IDataProvider * idp, IFuncProvider* ifp)
  {
      Rational left=_left->exec(idp,ifp);
      Rational right=_right->exec(idp,ifp);
      switch(token.tt)
      {
          case ADD:
              return left+right;
          case SUB:
              return left-right;
          case MUL:
              return left*right;
          case DIV:
              return left/right;
          default :
              string exp="unknow operator "+token.value;
              throw CL_NODE_Exception(exp.c_str());
      }
  };
  

• ArgsNode::exec()： 执行第一个参数的子树结构，获得一个结果。

• ArgsNode::execAll()： 调用ArgsNode::exec() 方法，将结果存在集合里，再递归调用其子节点的ArgsNode::execAll()方法，直到将所有参数放到集合里。

• FuncNode::exec()： 调用其第一个参数的execAll()方法，来递归获取所有的参数的值，再调用相应的方法call_func()将所有参数作为入参传入。

Num

Exec的计算结果，是一个实数。