在 Scala 中解析一个字符串，然后转换为另一种格式

Question

我有一个命题公式，例如，在这种字符串格式中：

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

我写了一个这样的解析器：

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)"))
}
}

那么，解析后的输出如下所示：

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

我正在尝试几种方法，通过使用操作^^来摆脱这些"额外"括号和东西，但没有成功。

实际上，我想要得到的结果是以.dimacs格式转换公式，其中每个字母/单词都是一个数字，/运算符成为文字之间的space，/成为newline(其中在每行末尾插入值0)。具体来说，对于我这里的示例 - 如果x = 1, y = 2, a = 3, b = 4, d = 5- 那么生成的文件必须如下所示：

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

任何关于我如何继续实现这一目标的提示都非常受欢迎！谢谢。

Answer 1

你不想有Parser[Any]; 相反，定义一个表示公式的数据类型：

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.

您也可以添加最终需要Formula的任何操作(或添加到伴随对象)。

然后定义Parser[Formula]并使用Formula，而不是字符串。

Formula是代数数据类型的一个例子，通过搜索此术语，您可以找到更多信息。