2

I have a large database of boolean values and want to build a framework for easily running queries over all of the values. To do this, I'd like to write a function that, given a string representation of a boolean expression, would evaluate that expression over all of the elements of the database. For example, given input

(a && b) || c

The function would construct another function that would evaluate

return (funcA() && funcB()) || funcC();

where funcA, funcB, and funcC are functions returning booleans

4

5 回答 5

5

这似乎最好分三步完成。

首先,你需要弄清楚你应该评估什么。这通常分两个步骤完成,称为扫描解析。扫描的工作是将输入字符串分解为一系列标记,即组成文本的更小的逻辑单元。例如,给定字符串

(a && b)

你会把它分解成令牌

(
a
&&
b
)

通常,这是使用正则表达式完成的,尽管您也可以手动完成。主要思想是将确定字符串片段的任务与查看这些片段如何相关的任务分开。

扫描输入后,您需要对其进行解析以确定所说的内容。也就是说,您将把标记重新组合成一个完整的数学表达式,编码运算符优先级、正在使用什么操作数等。有很多算法可以做到这一点,但其中最简单的可能是 Dijkstra 的分流场算法,它相当容易实施。您可能会使用抽象语法树(一种编码输入结构的树结构)来存储此解析步骤的输出。

此时,您对要评估的表达式的含义有了明确的解释,您需要实际评估它!为此,您可能会为每个 AST 节点定义一些函数以从该节点生成值。对于 && 之类的运算符,您将评估左右子表达式,然后计算它们的 AND(或者如果 lhs 为假,则可能使用短路来避免计算 rhs)。对于单个字母,您可以使用反射来调用相应的方法,或者可以有一个将名称映射到函数的表(取决于您想要的安全性。)

作为编码方面的潜在优化,您可能需要考虑省略 AST 的构建,而只计算您想要的值。调车场算法(以及许多其他解析器,例如自上而下的 LL(1) 或自下而上的 LR(1) 解析器)通常允许您根据表达式的组成表达式计算某个表达式的总体值,并且它以这种方式编码可能更容易。但是,如果您计划在像数据库这样的庞大数据集上使用所描述的函数,计算 AST 将为您提供一个对象,您可以在数据库中的每个值上调用该对象以生成您想要的值。

如果您计划对大量数据运行大规模复杂的查询,您甚至可能希望更进一步,将生成的表达式实际转换为 C# 代码,然后编译并加载到正在运行的程序中。我在 Java 中看到过使用这种方法效果很好的示例,但这是针对性能非常高的应用程序而言的,除非您用尽所有其他选项,否则这可能是矫枉过正。

希望这可以帮助!

于 2011-08-31T08:18:53.390 回答
2

好的,这是我选择的解决方案。

我使用以下代码项目

http://www.codeproject.com/KB/dotnet/Expr.aspx

例如,我得到标志和规则 ID 的列表:ArgsList = List<string> ={"0","&&","5"} // (0&&5)

   int id;
   var tmp = new List<string>();
   //------------------------------//
   foreach( string arg in ArgsList)
   {
       if( ( arg != "&&" && arg != "||" && arg != ")" && arg != "(" ) )
       {
          try
          {
              id = int.Parse(arg);
          }
          catch( Exception ex )
          {
               return false;
          }
          tmp.Add(GetRuleById(id, ref errorString).Check(wwObject, ref errorString).ToString());
       }
       else
       {
            tmp.Add(arg);
       }
  }

  //foreach converts it to List<string> = {"True","&&","False"}
  string stringtoeval;
  stringtoeval = string.Join(string.Empty, tmp.ToArray()).ToLower();//"True&&False"
  return (bool)EvalCSCode.EvalCSCode.Eval(stringtoeval);//returns false
于 2011-09-01T07:09:11.133 回答
1

你有括号,所以你必须解析它(递归地,在堆栈上,无论如何)需要首先评估的子表达式。您必须解析运算符(&&、||、!)以及符号(a、b、c),并将它们替换为适当的逻辑运算符或函数调用。

让你开始:

除非您以 ! 开头,否则您将以符号开头 操作员。

如果以符号开头,则下一个字符最好是二元运算符(&&、||)。之后的字符最好是子表达式或符号。如果它是一个子表达式,则递归计算它。如果是符号,则关闭中间的哪个运算符,并酌情将它们与或或组合在一起,并返回值。

于 2011-08-31T07:43:23.183 回答
1

您可以通过解析输入字符串然后使用反射来创建您想要执行的方法并执行它们来完成此操作,但这是一个相当复杂的解决方案。你到底想用这个来完成什么?使用 lambdas 和表达式树和委托可能有更好的方法。

于 2011-08-31T07:47:02.317 回答
0

与其深入解析的细节,我认为这可以使用 .NET 反射来完成(因为我看到了 C# 标记,我希望这个解决方案是可以的)。使用反射发出一个计算给定表达式的方法,然后调用此方法以获取结果。我个人觉得为此编写解析器比使用 .NET 反射更难,也更耗时。

于 2011-08-31T08:37:27.517 回答