Разбор строки с последующим преобразованием в другой формат в 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 Это пример алгебраического типа данных, и при поиске этого термина вы можете найти гораздо больше информации.