와 부울 표현식에서 괄호를 제거하는 방법 AND와 OR

Question

Let`s 내가 예를

를 들어, 목표는,이 식에 괄호를 제거하는 것입니다

(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 

Let`s 우리가 이미 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 (특히 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) 

그리고 올바른 DNF이다 출력 Or(Or(And(False,And(True,False)),And(False,And(True,False))),And(False,True)) .