代码之家 › 专栏 › 技术社区 › Necrolis

向数学分析器添加条件和函数

mathematical-expressions expression-trees c c++

Necrolis · 技术社区 · 14 年前

我建立了一个基于二叉树的数学表达式解析器,它非常适合“普通”数学,比如: (3.5 * 2) ^ 1 / (1 << 6) . 但是,我想稍微扩展一下,添加一个三元选择运算符,从C镜像一个: {expr} ? {true-expr} : {false-expr} . 我还想添加函数,比如 sin(x) 或 ave(...) .

但是,我不知道如何处理这个问题(由于评估工作的方式),也无法在网络上找到任何涉及这个问题的信息,至少是以非基于语法的方式(如果可能的话,我希望避免使用语法分析器生成器)。

我的解析器current通过评估一个中缀表达式并立即将其转换为一个树来工作,然后从中可以评估该树,即:它的标准表达式树是bog。

目前我的评估者是这样的:

struct Node
{
    int nType;
    union
    {
        unsigned long dwOperator;
        BOOL bValue;
        int nValue; //for indices, args & functions
        number_t fValue;
        char* szValue; //for string literals to pass to functions
    };

    Node* pLeft;
    Node* pRight;
};

number_t EvaluateTree(Node* pNode)
{
    if(pNode == NULL)
        return 0.0f;

    int nType = pNode->nType;
    if(nType == TOKEN_OPERATOR)
    {
        number_t fLeft = EvaluateTree(pNode->pLeft);
        number_t fRight = EvaluateTree(pNode->pRight);
        switch(pNode->dwOperator)
        {
            case '+': return fLeft + fRight;
            case '-': return fLeft - fRight;
            case '*': return fLeft * fRight;
            case '/': return fLeft / fRight;
            case '^': return pow(fLeft,fRight);
            case '_': return pow(fLeft,1.0f/fRight); 
            case '%': return fmod(fLeft,fRight);

            //case '?': return bSelect = ?;
            //case ':': return (bSelect) ? fLeft : fRight;

            //case '>': return fLeft > fRight;
            //case '<': return fLeft < fRight;
            //case '>=': return fLeft >= fRight;
            //case '<=': return fLeft <= fRight;
            //case '==': return fLeft == fRight;
            //case '!=': return fLeft != fRight;
            //case '||': return fLeft || fRight;
            //case '&&': return fLeft && fRight;

            case '&': return static_cast<number_t>(static_cast<unsigned long>(fLeft) & static_cast<unsigned long>(fRight));
            case '|': return static_cast<number_t>(static_cast<unsigned long>(fLeft) | static_cast<unsigned long>(fRight));
            case '~': return static_cast<number_t>(~static_cast<unsigned long>(fRight));
            case '>>': return static_cast<number_t>(static_cast<unsigned long>(fLeft) >> static_cast<unsigned long>(fRight));
            case '<<': return static_cast<number_t>(static_cast<unsigned long>(fLeft) << static_cast<unsigned long>(fRight));

            default:  
                {
                    printf("ERROR: Invalid Operator Found\n");
                    return 0.0f;
                }
        }
    }
    else if(nType == TOKEN_NUMBER)
        return pNode->fValue;
    else if(nType == TOKEN_CALL)
        return CreateCall(pNode); //not implemented
    else if(nType == TOKEN_GLOBAL)
        return GetGlobal(pNode);
    else if(nType == TOKEN_ARGUMENT)
        return GetArgument(pNode);
    else if(nType == TOKEN_STRING)
        return 0.0f;

    return 0.0f;
}

关于如何实现这一点,有什么提示/建议或有用的链接吗?

一小部分示例(按要求):

我已经在工作了

输入: 2 * (3 ^ 1.5) - 4 / (1 << 3)

输出: In-Order: 2.0 * 3.0 ^ 1.5 - 4.0 / 1.0 << 3.0

Pre-Order: - * 2.0 ^ 3.0 1.5 / 4.0 << 1.0 3.0

Post-Order: 2.0 3.0 1.5 ^ * 4.0 1.0 3.0 << / -

Result: 9.892304

我要添加的内容

输入: (GetDay() == 31) ? -15.5 : 8.4

输出: 8.4

31日产量: -15.5

输入: max([0],20) (其中[0]表示参数0,[0]=35)

输出: 20

输入: (GetField('employees','years_of_service',[0]) >= 10) ? 0.15 : 0.07 (其中[0]是参数0,而[0]设置为有效索引)

产出(如果员工服务年限少于10年: 0.15

其他输出: 0.07

它基本上是由一些C启发的添加组成的,除了参数不是按名称传递的,而是按索引传递的,字符串是用单引号转义的,而不是双引号。

当我完成最后一个位后,我希望字节码编译或JIT它,因为我计划将它用于游戏或数学相关程序,在这些程序中输入集数据是恒定的,但输入集可以更改,但它被频繁使用,所以它需要“快速”,并且它需要由非程序员使用。

2 回复 | 直到 13 年前

jsl4tv 14 年前

该怎么做?和:取决于解析器生成的树。我将假装解析器生成一个类似树的

      ?
  b       :
        t   f

首先,你不需要在转换之前评估树,而大多数你改变的地方就像

fLeft + fRight;

进入之内

EvaluateTree(pNode->pLeft) + EvaluateTree(pNode->pRight);

用+替换为所有不同的运算符。

为了什么?你…

case ':': return 0.0f; /* this is an error in the parse tree */
case '?': if (!(pNode && pNode->pLeft && pNode->pRight &&
                pNode->pRight->pLeft && pNode->pRight->pRight))
             /* another error in the parse tree */
             return 0.0f;
          return EvaluateBool(pNode->pLeft) ?
                   EvaluateTree(pNode->pRight->pLeft) :
                   EvaluateTree(pNode->pRight->pRight) ;

对于评估bool的定义,您有几个选择。C路或多或少

BOOL EvaluateBool(Node* pNode)
{
    return (EvaluateTree(pNode) == 0.0) ? FALSE : TRUE;
}

然后,您需要为“<”和朋友定义返回0.0表示“假”,以及任何其他表示“真”的定义。值-1是一个非常流行的真值,尽管通常用于在ints中存储bools。

更结构化的方法是将返回booleans的所有运算符(如“<”)移动到被评估bool的主体中,并使其或多或少像被评估树那样工作。

最后,不是做三元运算符?:使用两个节点,您还可以将节点(和解析器)的定义更改为最多具有三个子树,那么大多数运算符将具有两个树,但是?有三个。可能有点像

case '?': return EvaluateBool(pNode->pLeft) ?
                   EvaluateTree(pNode->pMiddle) : 
                   EvaluateTree(pNode->pRight) ;

但是你必须重写你的预顺序,顺序,后顺序树遍历。

第二部分,功能。一种方法是将函数名存储在szValue中。另一种方法是根据函数的不同,为类型设置一组不同的值。您必须在解析器中选择一些规则,并在解释器中使用它。你可以做一些像…

else if(nType == TOKEN_CALL)
    return EvaluateFunc(pNode);

那么evaluatefunc可能看起来像

number_t EvaluateFunc(Node* pNode)
{
    if ((pNode == NULL) || (pNode->szValue == NULL))
        return 0.0f;
    if (0 == strcmp('cos', pNode->szValue))
        return my_cos(EvaluateTree(pNode->pLeft));
    else if (0 == strcmp('gcd', pNode->szValue))
        return my_gcd(EvaluateTree(pNode->pLeft),
                      EvaluateTree(pNode->pRight));
    /* etc */
    else /* unknown function */ return 0.0f;
}

看起来像一个有趣的项目,享受吧!

Tom Sirgedas 14 年前

我认为您应该将“node”结构改为拥有一个子数组,而不是“pleft”和“pright”。像sin()这样的函数有一个参数/子参数。条件(三元)运算符有三个参数/子参数。