标签: boolean-expression

我写了一个小应用程序,将表达式解析为抽象语法树.现在,我使用一堆启发式方法来决定如何最好地评估查询.不幸的是,有一些例子使得查询计划非常糟糕.

我已经找到了一种方法来证明应该如何评估查询,但我需要先将表达式放入CNF或DNF,以获得可证明的正确答案.我知道这可能导致潜在的指数时间和空间,但对于典型的查询,我的用户运行这不是问题.

现在,转换为CNF或DNF是我一直手工完成的,以简化复杂的表达式.(好吧,也许不是所有的时间,但我确实知道如何使用例如demorgan的定律,分配定律等).但是,我不知道如何开始将其转换为可作为算法实现的方法.我看过有关查询优化的论文,有几篇以"首先我们把东西放入CNF"或"首先我们把东西放入DNF"开头,他们似乎从未解释过他们实现这一目标的方法.

我应该从哪里开始？

这是对其他人过滤/查询汽车列表的问题的后续行动.有一个RESTful过滤请求的建议是将过滤器表达式放在URI的查询中,如下所示:

/cars?color=blue&type=sedan&doors=4

没关系.但是如果我的过滤查询变得更复杂并且我需要使用布尔运算符,例如:

((color=blue OR type=sedan) AND doors=4) OR color=red

也就是说,我想找一辆四门蓝色轿车或一辆四门轿车,但如果这辆车是红色的,我会毫不关心任何其他房产.

是否有任何类型的约定在RESTful URI的查询参数中提供布尔表达式？我想我可以通过创建一些新的查询表达式语言并将其放入一个POST,但这似乎是一种沉重而专有的方法.别人怎么解决这个问题？

我的Perl 5.26.2 x64(Cygwin)的经验行为是,当且仅当其字符串部分是真实时,双变量才是真实的:

# Falsy number, truthy string => truthy
$ perl -MScalar::Util=dualvar -E 'my $v=dualvar 0, "foo"; say "yes" if $v'
yes

# Truthy number, falsy string => falsy
$ perl -MScalar::Util=dualvar -E 'my $v=dualvar 1, ""; say "yes" if $v'

# Truthy number, truthy string => truthy
$ perl -MScalar::Util=dualvar -E 'my $v=dualvar 1, "foo"; say "yes" if $v'
yes

# Falsy number, falsy string => falsy
$ perl -MScalar::Util=dualvar -E 'my $v=dualvar 0, ""; say …

val exp = "( 0 == 1 && 10 > 11 ) || ( 10 < 9 ) && ( 10 == 10)"
val result: Boolean = evaluate(exp) //result = true/false

如何在 Android (Kotlin) 中编写一个简单的程序来评估上述字符串并获得布尔结果？我不想使用像 那样的完整评估器JEL or JEval, Js Eval or any other library，因为它们对于这个特定要求来说太大了。

Preconditions :
Operators supported : < > == && || 
Works only on digits

也不想用 ScriptEngineManager()

注意：javax.script 包在 Android 上不可用。

我写了这个:

if( a == -11 && b == -1 ){
{

if( a == -1) AND ( b == -1)...

但是没有工作,我也有同样的问题OR.如何编写包含OR或的表达式AND？

这不是一个实际问题 - 我只是对我观察到的一些奇怪的行为感到好奇,并且想知道我是否正确地理解了"is"操作符.

这是一些可预测的Python解释器输出:

>>> True is True
True
>>> (1==1) is True
True

现在让我们定义一个名为True的变量:

>>> True = 'abc'
>>> True == 'abc'
True
>>> True is 'abc'
True

对于布尔运算,解释器仍将返回"True",但布尔运算的结果被认为与"abc"和"True"都不相同.

>>> (1==1)
True
>>> (1==1) is 'abc'
False
>>> (1==1) is True
False

谁能解释这种奇怪的行为？

我正在开发一个流规则引擎，我的一些客户有几百条规则，他们想对到达系统的每个事件进行评估。规则是纯（即无副作用）布尔表达式，它们可以任意深度嵌套。

客户在运行时创建、更新和删除规则，我需要动态检测和适应规则的数量。目前，表达式计算在内部 AST 上使用解释器，我还没有开始考虑 codegen。

与往常一样，树中的某些谓词的计算成本比其他谓词要便宜得多，而且我一直在寻找一种算法或数据结构，以便更容易找到便宜的谓词，并且可以有效地解释为控制整个表达。我对这种模式的心理标题是“ANDs all way to the root”，即所有祖先都是ANDs的任何谓词都可以解释为控制。

尽管进行了几天的文献搜索，阅读了有关 ROBDD、CNF、DNF 等的信息，但我还是无法从行业中的常见做法到我的特定用例关闭循环。我发现似乎相关的一件事是布尔表达式索引的分析和优化， 但不清楚如何在不自己实现 BE-Tree 数据结构的情况下应用它，因为似乎没有开源实现。

我一直半开玩笑地向我的团队提到，这些天我们将需要一个 SAT 求解器。我想编写一个遍历树并跟踪每个祖先是 AND 还是 OR 的递归算法可能就足够了，但我一直有“这肯定是一个已解决的问题”的感觉。:)

编辑：与几个朋友交谈后，我想我可能有一个解决方案的草图！

1. 将表达式转换为联合范式，根据定义，其中每个节点都处于有效的短路位置。
2. 使用 Tseitin 算法尽量避免 CNF 变换导致的表达式大小的指数膨胀
3. 对于树中的每个AND，按成本升序排序（即最便宜的到左边）
4. ？？？
5. 利润！^Weval 像往常一样:)

C语言没有布尔数据类型,而是使用整数.比较运算符(如==和<=)返回整数值0表示false,1表示true表示.但是,C中的if语句会将其条件的任何非零值视为等于true.为什么不同？为什么不允许关系运算符返回任何非零值来表示true？

它是pythonic使用or,类似于PHP将如何使用or die()？

我一直在用
quiet or print(stuff)
而不是
if verbose: print(stuff)
最近.

我认为它看起来更好,它们做同样的事情,并且它节省了一条线.在性能方面,一个人会比另一个人好吗？

两者的字节码看起来几乎和我一样,但我真的不知道我在看什么......

or

  
  2           0 LOAD_FAST                0 (quiet)
              3 JUMP_IF_TRUE_OR_POP     15
              6 LOAD_GLOBAL              0 (print)
              9 LOAD_CONST               1 ('foo')
             12 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
        >>   15 POP_TOP
             16 LOAD_CONST               0 (None)
             19 RETURN_VALUE

VS if

  2           0 LOAD_FAST                0 (verbose)
              3 POP_JUMP_IF_FALSE       19

  3           6 LOAD_GLOBAL              0 (print)
              9 LOAD_CONST               1 ('bar')
             12 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             15 POP_TOP …

哪个更好？(为什么？)

if somevalue == False:

要么

if somevalue is False:

如果somevalue是字符串,你的答案会改变吗？