Nah*_*hum 2 c# algorithm parsing expression-evaluation
我有一个庞大的布尔值数据库,并希望构建一个框架,以便在所有值上轻松运行查询.为此,我想编写一个函数,给定一个布尔表达式的字符串表示,将在数据库的所有元素上计算该表达式.例如,给定输入
(a && b) || c
该函数将构造另一个将要评估的函数
return (funcA() && funcB()) || funcC();
其中funcA,funcB和,funcC是和功能返回布尔值
这似乎最好分三步完成.
首先,你需要弄清楚你应该评估什么.这通常分两步完成,称为扫描和解析.扫描的工作是将输入字符串分解为一系列标记,组成文本的较小逻辑单元.例如,给定字符串
(a && b)
你会把它分解成代币
(
a
&&
b
)
通常,这是使用正则表达式完成的,但您也可以手动完成.主要思想是将确定字符串片段的任务与查看这些片段相关的任务分开.
扫描完输入后,需要对其进行解析以确定所说的内容.也就是说,你将令牌重新组合成一个完整的数学表达式编码运算符优先级,正在使用的操作数等等.有很多算法可以做到这一点,但也许最简单的算法是Dijkstra的调车码算法,这很容易实行.您可能会使用抽象语法树存储此解析步骤的输出,这是一种编码输入结构的树结构.
此时,您对要评估的表达式的含义有明确的解释,您需要对其进行实际评估!为此,您可能会为每个AST节点定义一些从该节点生成值的函数.对于像&&这样的运算符,您将评估左右子表达式,然后计算它们的AND(或者如果lhs为假则可能使用短路来避免计算rhs).对于单个字母,您可以使用反射来调用相应的方法,或者可以将表映射到函数的表(取决于您想要的安全性).
作为编码方面的潜在优化,您可能需要考虑省略AST的构造,并且只需计算您想要的值.分流码算法(以及许多其他解析器,例如自上而下的LL(1)或自下而上的LR(1)解析器)通常允许您根据其组成表达式计算表达式的某些总值,并且可能更容易以这种方式编码.但是,如果您计划在数据库之类的大型数据集上使用所描述的函数,那么计算AST会为您提供一个对象,您可以调用数据库中的每个值来生成您想要的值.
如果您计划对大量数据运行大规模复杂查询,您甚至可能希望更进一步,实际将生成的表达式转换为C#代码,然后编译并加载到正在运行的程序中.我已经在Java中看到过这样的例子,但这是一个非常高性能的应用程序,并且除非你已经用尽所有其他选项,否则这可能是一种过度杀伤力.
希望这可以帮助!