boolean - 将带括号的条件转换为不带括号的等价条件

Question

我正在开发一个应用程序，用户可以在其中为某些任务添加条件。

例如，他可以有条件 a、b、c、d 并将它们组合在一起，最终看起来像：

(a AND b) OR ( c AND d )
或
(a AND b AND c) or d
或
(a AND !b) AND c OR !d

等等

如何通过删除括号将这些条件转换为等效条件？

Answer 1

AND布尔代数中的每个表达式都可以仅使用, OR, 和!(unary NOT)转换为等价表达式，无需括号。

这是一个简单但低效的算法：

使用示例表达式(a OR !b) AND c，

1. 为变量的每个真值组合建立一个真值表：

   | a | b | c | (a OR !b) AND c  |
   | 0   0   0 | 0                |
   | 0   0   1 | 1                |
   | 0   1   0 | 0                |
   | 0   1   1 | 0                |
   | 1   0   0 | 0                |
   | 1   0   1 | 1                |
   | 1   1   0 | 0                |
   | 1   1   1 | 1                |
   

2. 对于表达式为真的每一组值（最右列中的每一行），使用s1创建一个表达式，并且仅针对该特定值集计算为真。AND!

   | a | b | c | (a OR !b) AND c  |
   | 0   0   0 | 0                |
   | 0   0   1 | 1                |  (!a AND !b AND c )
   | 0   1   0 | 0                |
   | 0   1   1 | 0                |
   | 1   0   0 | 0                |
   | 1   0   1 | 1                |  (a  AND !b AND c )
   | 1   1   0 | 0                |
   | 1   1   1 | 1                |  (a  AND b  AND c )
   

3. 用 OR 连接表达式。

   (!a AND !b AND c ) OR (a  AND !b AND c ) OR (a  AND b  AND c )
   

4. 生成的表达式很少是最小的，因此您可能希望在之后应用一些最小化技术。

   (!a AND !b AND c) OR (a AND !b AND c) OR (a AND b AND c)
   =
   (!a AND !b AND c) OR (a AND c)
   =
   (!b AND c) OR (a AND c)
   

达达！

需要注意的是，在步骤 1 中构建真值表是一个 O(2^n) 操作（以变量数量计），这很糟糕。对于具有大量变量的情况，您可能需要使用不同的技术。该算法的主要优点是它使任何表达式如何转换为您想要的形式变得非常明显。

编辑：要清楚，如果您使用正常的优先规则，您可以删除最终表达式中的括号。

Answer 2

您可以使用布尔代数的各种属性来帮助简化表达式，但您可能无法摆脱所有括号。括号对于某些表达式是必需的，因为 NOT、AND 和 OR 的运算没有顺序。因此，如果您不能重新排列表达式以从左到右阅读，则需要括号。

Answer 3

不完全确定转换为非括号等效项的动机是什么，所以我认为这意味着您正在尝试建立一种表达能力（即表达语言），以便用户将他们所需的任务条件传达给您的应用程序。

您无法消除对括号的需求，并且仍然支持具有正常运算符优先级规则的正常中缀表达式语言中的任意复杂表达式。

你有几个选择，我认为：

1. 支持括号。（它们并不难解析。）

2. 使用不使用括号的替代相对标准或众所周知的表达语言，例如反向波兰表示法，又名 RPN。请参阅http://en.wikipedia.org/wiki/Reverse_Polish_notation。RPN 使用后缀表示法，允许用户通过定位和堆叠而不是使用括号来完全控制运算符优先级。这是以必须仔细（重新）排序操作数和操作为代价的。（没有免费的午餐。）

3. 将您的语言的表现力限制为某些特定模式，这些模式在更正常（中缀）语言（具有运算符优先级）中不需要括号。

最后，如果你有一个用户界面来帮助用户编写他们的表达式（而不是文本语言），你可以像上面的 #2 那样做一些事情，并使用用户定义子表达式的顺序来指示运算符的优先级，而不需要括号。基本上，您的 UI 将帮助他们构建表达式树。

最后，如果您的问题是如何删除括号以执行表达式，这更像是代码生成问题。同样，RPN 堆栈很有用。或者，您可以将（可能带有括号的）表达式转换为由附加（在编译器术语中是临时的）变量显式连接的单个迷你（例如三个操作数）语句。例如，(a + b) * c变成t1 = a + b后面跟着final-result = t1 * c。