我正在解决 Java 中的逻辑表达式,包括 AND、OR 和 NOT 运算符。
如果包含变量的任何 boolean 值的输入为 TRUE
,则程序必须输出。我已经成功完成了,但效率不够。
我目前的解决方案是这样的:
为表达式中的每个变量制作真值表并逐行求值。
(p ∧ ¬q) ∨ (r ∧ s) ∨ (¬p ∨ u)
在上面的示例中,我必须使用变量真值表p q r s
来评估整个表达式。
现在,我正在考虑实现如下所示的替代解决方案: 考虑上面的例子。
我们可以注意到,即使只求解 p ∧ ¬q
部分,所有表达式的结果都是 TRUE
。这为我们省去了 3 个额外变量的麻烦。
现在,我的问题是这样的。如何在 JAVA 中对此进行编程?我什至如何知道输入是否具有上述模式?或者它只是我必须为整个真值表评估的表达式?就像下面的一样
(p ∨ ¬q) ∧ (r ∨ (s ∧ (¬p ∨ u)))
最佳答案
这是一个众所周知的 NP 完全问题,请参阅 Boolean Satisfiability Problem .
这意味着没有已知的多项式时间解,但有很多 >P 解。
您将不得不暴力破解它并在可能的地方短路。 (例如:如果所有运算符都是 or
,并且您找到一个 true
值,您可以停止计算)
关于java - 用最少的迭代次数解决 Java 中的逻辑表达式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54753109/