Parsing eine Zeichenfolge dann in ein anderes Format zu konvertieren, in Scala

Question

Ich habe eine aussagenlogische Formel, zum Beispiel in diesem String-Format:

(~d \/ x) /\ (y \/ ~b) /\ (~y \/ a \/ b)

ich einen Parser wie folgt geschrieben:

import scala.util.parsing.combinator._ 

class CNFParser extends JavaTokenParsers with RegexParsers { 
    def expr: Parser[Any] = term~rep("/\\"~term) 
    def term: Parser[Any] = value~rep("\\/"~value) 
    def value: Parser[Any] = ident | "~"~ident | "("~expr~")" 

} 

object Test_02 extends CNFParser { 
    def main(args: Array[String]): Unit = { 

    println("input: " + "(~d \\/ x) /\\ (y \\/ ~b) /\\ (~y \\/ a \\/ b)") 
    println(parseAll(expr, "(~d \\/ x) /\\ (y \\/ ~b) /\\ (~y \\/ a \\/ b)")) 

    } 
} 

Nun, die geparste Ausgabe sieht so aus:

[1.41] parsed: (((((~(((~~d)~List((\/~x)))~List()))~))~List())~List((/\~((((~((y~List((\/~(~~b))))~List()))~))~List())), (/\~((((~(((~~y)~List((\/~a), (\/~b)))~List()))~))~List())))) 

Ich versuche mehrere Möglichkeiten , mit den Operationen ^^, um diese "extra" Klammern und Zeug loszuwerden, aber ohne Erfolg.

Eigentlich ist das Ergebnis, das ich bekommen will, ist die Formel in einem .dimacs-Format zu konvertieren, wobei jeder Buchstaben/Wort eine Zahl ist, die \/ Betreiber werden ein space zwischen der Literale und die \/ wird ein newline (wo ein Am Ende jeder Zeile wird der Wert 0 eingefügt. Konkret für mein Beispiel hier - wenn x = 1, y = 2, a = 3, b = 4, d = 5 - dann wird die resultierende Datei muss wie folgt aussehen:

c filename.cnf 
p cnf 5 3 
-5 1 0 
2 -4 0 
-2 3 4 

Jeder Hinweis, wie ich auch weiterhin zu erreichen, das wirklich willkommen ist! Vielen Dank.

Answer 1

Sie möchten Parser[Any] nicht haben; stattdessen einen Datentyp darstellen Formeln definieren:

sealed trait Formula 
case class Variable(name: String) extends Formula { 
    override def toString = name 
} 
case class And(left: Formula, right: Formula) { 
    override def toString = s"($left /\ $right)" 
} 
// etc. 

Sie alle Vorgänge hinzufügen, können Sie zu Formula am Ende brauchen (oder auf dem Begleitobjekt) als auch.

Dann definieren Sie Parser[Formula] und arbeiten mit Formula s, nicht mit Strings.

Formula ist ein Beispiel für einen algebraischen Datentyp, und durch die Suche nach diesem Begriff können Sie eine Menge mehr Informationen finden.