Let`s sagen, ich habe ein paar einfachen Boolesche AusdruckWie wird man mit in Booleschen Ausdrücken von Klammern befreit AND und OR
(A || B) && (C || D)
Das Ziel ist, in diesem Ausdruck los Klammer zu erhalten, zum Beispiel
(A || B) && (C || D) => A && C || A && D || B && C || B && D
Wir wissen, dass &&
wertet vor ||
von links nach rechts. Um dies zu erreichen ich den folgenden algebraischen Datentyp erstellt habe:
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 davon aus, dass wir bereits eine Art von String-Parsern haben, die Zeichenfolge zu Predicate
umwandelt, baut es eine Art Zusammenfassung syntaktischen Baumes. Zum Beispiel für den Ausdruck (true || true) && (true || true)
haben wir den folgenden Baum: And(Or(True, True), Or(True, True))
. Hier kommen die Zahnspangen in Betracht. Wir müssen Or(Or(And(A, C), And(A, D)), Or(And(B, C), And(B,D)))
bekommen. ich mit folgenden Lösung fest:
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
}
Aber es funktioniert nicht korrekt zum Beispiel für diesen Fall: And(False, Or(And(Or(True, True), False), True))
UPD: Wie @coredump wies darauf hin, ich brauche schließlich DNF(sum of products)
Aufgrund Ihrer Titelfrage und der Einleitung war zunächst nicht klar, ob Sie das https://en.wikipedia.org/wiki/Disjunctive_normal_form berechnen wollen oder ob Sie Ihren Code irgendwie umgestalten wollen. Oder vielleicht willst du ja auch kein DNF. Sind das Hausaufgaben? – coredump
@coredump: DNF (Summe der Produkte) - genau das, was ich suche! guter Punkt. – ponkin
In "Und (Falsch, Oder (Und (Oder (Wahr, Wahr), Falsch), Wahr))" möchten Sie nicht, dass es sofort mit False kurzgeschlossen wird, denn wenn 1 Falsch in einem ist Und es bewertet zu falsch? –