2

我有一个基于二叉树的数学表达式解析器，它非常适用于“普通”数学，例如：(3.5 * 2) ^ 1 / (1 << 6). 但是，我想稍微扩展它以添加一个三元选择运算符，镜像来自 C: 的那个{expr} ? {true-expr} : {false-expr}。我还想添加功能，例如sin(x)or ave(...)。

然而，我不知道如何处理这个问题（由于评估的工作方式），我也无法在网上找到任何涵盖这个的东西，至少以非基于语法的方式（我想避免语法分析器生成器为此，如果可能的话）。

我的解析器当前通过评估中缀表达式并立即将其转换为树来工作，然后可以从那里评估树，即：它是标准表达式树。

目前我的评估员看起来像这样：

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] 设置为有效索引）

输出（如果员工的 years_of_service 小于 10：0.15

否则输出：0.07

它基本上是数学，带有一些受 C 启发的添加，除了参数不是按名称传递，而是按索引传递，并且字符串由单引号转义而不是双引号。

当我完成最后一点时，我希望要么编译字节码，要么 JIT 它，因为我计划将它用于游戏或依赖数学的程序，其中输入集数据是恒定的，但输入集可以改变，但它被频繁使用，所以它需要“快速”，并且需要非程序员可以使用。

4

2 回答 2

1

正确的做法是什么？and : 取决于解析器生成的树。我会假装解析器生成一棵树

      ?
  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) ;

对于 EvaluateBool 的定义，您有几个选择。C方式或多或少

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

然后你需要定义 '<' 和返回 0.0 为 false 的朋友，以及任何其他为 true 的定义。值 -1 是一个非常流行的真值，尽管通常用于将布尔值存储在整数中。

更结构化的方法是将所有返回布尔值的运算符（如 '<'）移动到 EvaluateBool 的主体中，并使其或多或少地像 EvaluateTree 一样工作。

最后，不要让三元运算符 ?: 使用两个节点，您还可以将节点（和解析器）的定义更改为最多具有三个子树，然后大多数运算符将有两个树，但是 ?: 将有三个. 也许像

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

但是随后您将不得不重写您的前序、中序、后序树遍历。

第二部分，功能。一种方法是将函数的名称存储在 szValue 中。另一个是根据函数有一堆不同的 nType 值。您必须在解析器中选择一些规则，并在解释器中使用它。你可以做类似...

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

看起来很有趣的项目，享受吧！

于 2010-07-18T21:25:49.773 回答
1

我认为您应该将“节点”结构更改为具有子数组，而不是“pLeft”和“pRight”。像 sin() 这样的函数有一个参数/子项。条件（三元）运算符具有三个参数/子项。

于 2010-07-18T22:01:54.940 回答