如何去掉带有 AND 和 OR 的布尔表达式中的大括号

Question

假设我有一些简单的布尔表达式

(A || B) && (C || D)

目标是去掉这个表达式中的大括号，例如

(A || B) && (C || D) => A && C || A && D || B && C || B && D

我们知道 && 从左到右在 || 之前计算。为此，我创建了以下代数数据类型：

sealed trait Predicate
case class Or(left: Predicate, right: Predicate) extends Predicate
case class And(left: Predicate, right: Predicate) extends Predicate
case object True extends Predicate
case object False extends Predicate

让我们假设我们已经有了某种字符串解析器，它将字符串转换为 Predicate，它构建了某种抽象语法树。例如，对于表达式 (true || true) && (true || true)，我们将得到以下树：And(Or(True, True), Or(True, True))。在这里，我们考虑大括号。我们需要得到 Or(Or(And(A, C), And(A, D)), Or(And(B, C), And(B,D)))。我坚持使用以下解决方案：

def extractOr(pred: Predicate): Predicate = pred match {
    case And(Or(l, r), Or(ll, rr)) => Or(Or(And(l, ll), And(l, rr)), Or(And(r, ll), And(r, rr)))
    case And(Or(l, r), p) => Or(And(l, p), And(r, p))
    case And(p, Or(l, r)) => Or(And(p, l), And(p, r))
    case p => p
}

def popOrPredicateUp(pred: Predicate): Predicate = pred match {
    case And(l, r) => extractOr(And(popOrPredicateUp(l), popOrPredicateUp(r)))
    case Or(l, r) => Or(popOrPredicateUp(l), popOrPredicateUp(r))
    case p => p
}

但是在这种情况下它的工作不正确：And(False, Or(And(Or(True, True), False), True))

UPD：正如@coredump 指出的那样，我需要得到 DNF(sum of products)

Answer 1

终于在@coredump 的大力帮助下（他指出了正确的方向）和Haskell 打包hatt(particulary that code)。我得出以下解决方案：

sealed trait Predicate
case class Or(left: Predicate, right: Predicate) extends Predicate
case class And(left: Predicate, right: Predicate) extends Predicate
case class Not(pred: Predicate) extends Predicate
case object True extends Predicate
case object False extends Predicate

object PredicateOps{

  def toNNF(pred: Predicate): Predicate = pred match {
    case a @ (True | False) => a
    case a @ Not( True | False) => a
    case Not(Not(p)) => p
    case And(l, r) => And(toNNF(l), toNNF(r))
    case Not(And(l, r)) => toNNF( Or(Not(l), Not(r)))
    case Or(l, r) => Or(toNNF(l), toNNF(r))
    case Not(Or(l,r)) => toNNF( And(Not(l), Not(r)))
  }

  def dist(predL: Predicate, predR: Predicate): Predicate = (predL, predR) match {
    case (Or(l, r), p) => Or(dist(l, p), dist(r, p))
    case (p, Or(l, r)) => Or(dist(p, l), dist(p, r))
    case (l, r) => And(l, r)
  }

  def toDNF(pred: Predicate): Predicate = pred match {
    case And(l, r) => dist(toDNF(l), toDNF(r))
    case Or(l, r) =>  Or(toDNF(l), toDNF(r))
    case p => p
  }

}

工作原理如下：

val expr = And(False, Or(And(Or(True, True), False), True))
val dnf = (PredicateOps.toNNF _ andThen PredicateOps.toDNF _).apply(expr)
println(dnf)

并且输出 Or(Or(And(False,And(True,False)),And(False,And(True,False))),And(False,True)) 是正确的 DNF。

如何去掉带有 AND 和 OR 的布尔表达式中的大括号

How to get rid of braces in boolean expressions with AND and OR

algorithm

boolean-logic

scala

abstract-syntax-tree

algebraic-data-types