java - Solving logical expressions in Java with minimum iterations
问题描述
I'm working on solving the logical expressions in Java comprising of AND, OR, and NOT operators.
The program has to output if the input was TRUE
for any Boolean values of the variables included. I've done it successfully but it is not efficient enough.
My current solution goes like:
Make a truth table for each variable in the expression and evaluate row by row.
(p ∧ ¬q) ∨ (r ∧ s) ∨ (¬p ∨ u)
In the above example, I'll have to evaluate the whole expression with a truth table of variables p q r s
.
Now, I'm thinking of implementing an alternate solution that goes like this: Consider the example above.
We can notice that even by just solving the p ∧ ¬q
part, all of the expression comes out to be TRUE
. This saves us the hassle of 3 extra variables.
Now, my question is this. How to program this in JAVA? How do I even get to know if the input does have a pattern like above? Or is it just an expression that I have to evaluate for the whole Truth Table? Like the one below
(p ∨ ¬q) ∧ (r ∨ (s ∧ (¬p ∨ u)))
解决方案
This is a well known NP-complete problem, see Boolean Satisfiability Problem.
This means there is no known polynomial time solution, but there are many >P solutions out there.
You will have to brute force it and short circuit where you can. (ex: if all operators are or
and you find a true
value you can stop computation)
推荐阅读
- r - 当使用 \n 换行时,减少 geom_label() 和 geom_text() 中 R ggplot 中的行高
- java - 如何使用 protobuf-gradle-plugin 指定 Protobuf 路径
- json - Foreach Json 结果 Ionic Angular
- html -
- 在 HTML 中的“for”循环中使用时,标记不会从 1 递增并保持为 1
- ios - 在 swift 项目中安装 alamofire pod 时出错
- c++ - get_shift() 后原始短语未打印
- xcode - 为 iOS 模拟器库构建问题
- spring - 自动装配接口与类
- python - Python上的CWs风格排名系统
- python - 如何通过 Python 请求复制 Google 登录?