添加条件和条件数学解析器的功能 [英] Adding Conditionals & Functions to a Math Parser
问题描述
我有一个基于二进制树的数学表达式解析器，该解析器非常适合普通"数学，例如:(3.5 * 2) ^ 1 / (1 << 6).但是，我想对其进行一点扩展以添加一个三元选择运算符，从C:{expr} ? {true-expr} : {false-expr}镜像一个.我还想添加功能，例如sin(x)或ave(...).
I have a binary tree based mathematical expression parser I built, which works great for 'normal' math, like: (3.5 * 2) ^ 1 / (1 << 6). however, I would like to expand it a little to add a ternary selection operator, mirroring the one from C: {expr} ? {true-expr} : {false-expr}. I would also like to add functions, like sin(x) or ave(...).
但是我不知道如何处理(由于评估的工作方式)，我也无法在网络上找到任何涵盖此内容的内容，至少没有基于非语法的方式(我想避免语法分析器生成器).
I however have no clue to how the handle this (due to the way the evaluation works), nor can I find anything on the web that covers this, atleast in a non-grammer based way (I'd like to avoid grammer parser generators for this, if possible).
我的解析器当前的工作方式是评估一个中缀表达式并将其立即转换为树，然后从那里可以评估该树，即:它是标准表达式树.
My parser current works by evaluating an infix expression and immediatly converting it to a tree, then from there the tree can be evaluated, ie: its you bog standard expression tree.
目前，我的评估者看起来像这样:
currently my evaluator looks like so:
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;
}
有关如何实现此目标的任何提示/技巧/建议或有用链接?
Any tips/pointers/advice or useful links on how I can accomplish this?
一小部分示例(根据要求):
A small set of examples (as requested):
输入: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)
Input: max([0],20) (where [0] denotes argument 0, and [0] = 35)
输出:20
输入:(GetField('employees','years_of_service',[0]) >= 10) ? 0.15 : 0.07(其中[0]为参数0，[0]设置为有效索引)
Input: (GetField('employees','years_of_service',[0]) >= 10) ? 0.15 : 0.07 (where [0] is argument 0, and [0] is set to a valid index)
输出(如果该雇员的服务年限小于10:0.15
Output (if years_of_service for the emplyee is less than 10: 0.15
其他输出:0.07
它基本上是数学运算，带有一些受C启发的加法运算，除了参数不是按名称传递，而是通过索引传递，而字符串用单引号引起来，而不是加倍.
Its basically math with some C inspired additions, except arguments aren't passed by name, but rather index, and strings are escaped by single quotes instead doubles.
当我完成最后的工作后，我希望使用字节码编译或JIT，因为我打算将其用于诸如游戏或数学相关程序之类的事情，其中输入集数据是恒定的，但是输入集可以更改，但是经常使用，因此需要快速"，并且必须可供非程序员使用.
When once I have the final bit done, I'm hoping to either bytecode compile or JIT it, as I'm planing to use this for things like games or math reliant programs, where the input set data is constant, but the input set can change, but its being used frequently, so it needs to be 'fast', and it needs to be usable by non-programmers.
推荐答案
正确的做法是?和:取决于解析器生成的树.我会假装解析器会生成像这样的树
The correct thing to do for ? and : depends on the tree produced by the parser. I will pretend the parser generates a tree like
?
b :
t f
首先，您无需在切换之前评估树，大多数情况下，您需要进行类似的更改
First you need to not evaluate the trees before the switch, and most places you change something like
fLeft + fRight;
进入
EvaluateTree(pNode->pLeft) + EvaluateTree(pNode->pRight);
用+替换为所有各种运算符.
With + replaced by all the various operators.
对于?:您愿意....
For ?: you do ....
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的方式或多或少
For a definition of EvaluateBool you have a couple choices. The C way is more or less
BOOL EvaluateBool(Node* pNode)
{
return (EvaluateTree(pNode) == 0.0) ? FALSE : TRUE;
}
然后，您需要为'<'定义和返回0.0的false以及返回true的其他朋友.值-1是一个非常流行的真实值，尽管通常用于将整数存储为整数.
Then you need definitions for '<' and friends that return 0.0 for false, and anything else for true. The value -1 is a very popular true value, though generally for storing bools in ints.
更结构化的方法是移动所有运算符，例如'<'.会将布尔值返回到EvaluateBool的主体中，并使它像EvaluateTree一样工作或多或少.
The more structured way is to move all the operators like '<' that return booleans into the body of EvaluateBool, and make it work more-or-less like EvaluateTree does.
最后，代替使用三元运算符?:使用两个节点，还可以将节点(和解析器)的定义更改为最多具有三个子树，然后大多数运算符将具有两个树，但是?:将有三个.也许像
Finally, instead of making the ternary operator ?: use two nodes, you could also change the definition of the node (and the parser) to have up to three sub trees, then most operators would have two trees, but ?: would have three. Maybe something like
case '?': return EvaluateBool(pNode->pLeft) ?
EvaluateTree(pNode->pMiddle) :
EvaluateTree(pNode->pRight) ;
但是随后，您将不得不重新编写顺序，顺序，顺序树遍历.
But then you'll have to rewrite your pre-order, in-order, post-order tree traversals.
第二部分，功能.一种方法是将函数名称存储在szValue中.另一个是根据功能，nType具有许多不同的值.您将必须在解析器中选择一些规则，然后在解释器中使用它.你可以做类似...
Second part, functions. One way you could do it is store the name of the function in szValue. Another is have a bunch of different values for nType depending on the function. You will have to pick some rule in the parser, and use it here in the interpreter. You could do something like...
else if(nType == TOKEN_CALL)
return EvaluateFunc(pNode);
然后EvaluateFunc看起来像
Then EvaluateFunc could look something like
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;
}
看起来像一个有趣的项目，尽情享受吧！
Looks like a fun project, enjoy!
这篇关于添加条件和条件数学解析器的功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
