Оказывается, этот вид парсинга мне тоже интересен, поэтому я проделал немного больше работы над ним.
Кажется, есть чувство, что такие вещи, как упрощение выражений, сложны. Я не уверен. Давайте посмотрим на довольно полное решение. (Распечатка tn выражений для меня бесполезна, и у вас уже есть несколько примеров Scala, поэтому я пропущу это.)
Во-первых, нам нужно извлечь различные части языка. Я выберу регулярные выражения, хотя можно использовать и комбинаторы парсера:
object OpParser {
val Natural = "([0-9]+)"r
val Number = """((?:-)?[0-9]+(?:\.[0-9]+)?(?:[eE](?:-)?[0-9]+)?)"""r
val Variable = "([a-z])"r
val Unary = "(exp|sin|cos|tan|sqrt)"r
val Binary = "([-+*/^])"r
val Nary = "(sum|prod|list)"r
Довольно просто. Мы определяем различные вещи, которые могут появиться. (Я решил, что пользовательские переменные могут быть только одной строчной буквой, а числа могут быть с плавающей точкой, поскольку у вас есть функция exp.) r в конце означает, что это регулярное выражение, и это даст нам вещи в скобках.
Теперь нам нужно представить наше дерево. Есть несколько способов сделать это, но я выберу абстрактный базовый класс со специальными выражениями в качестве case-классов, поскольку это облегчает сопоставление с образцом. Кроме того, нам может потребоваться хорошая печать, поэтому мы переопределим toString. Однако в основном мы будем использовать рекурсивные функции для выполнения тяжелой работы.
abstract class Expr {
def text: String
def args: List[Expr]
override def toString = args match {
case l :: r :: Nil => "(" + l + " " + text + " " + r + ")"
case Nil => text
case _ => args.mkString(text+"(", ",", ")")
}
}
case class Num(text: String, args: List[Expr]) extends Expr {
val quantity = text.toDouble
}
case class Var(text: String, args: List[Expr]) extends Expr {
override def toString = args match {
case arg :: Nil => "(" + text + " <- " + arg + ")"
case _ => text
}
}
case class Una(text: String, args: List[Expr]) extends Expr
case class Bin(text: String, args: List[Expr]) extends Expr
case class Nar(text: String, args: List[Expr]) extends Expr {
override def toString = text match {
case "list" =>
(for ((a,i) <- args.zipWithIndex) yield {
"%3d: %s".format(i+1,a.toString)
}).mkString("List[\n","\n","\n]")
case _ => super.toString
}
}
В основном это довольно скучно - каждый класс дел переопределяет базовый класс, а text и args автоматически заменяют def. Обратите внимание, что я решил, что list является возможной n-арной функцией, и что она будет напечатана с номерами строк. (Причина в том, что если у вас несколько строк ввода, иногда удобнее работать со всеми ними как одним выражением; это позволяет им быть одной функцией.)
Как только наши структуры данных определены, нам нужно проанализировать выражения. Удобно представлять материал для анализа в виде списка токенов; когда мы анализируем, мы возвращаем как выражение, так и оставшиеся токены, которые мы не анализировали - это особенно полезная структура для рекурсивного анализа. Конечно, мы можем ничего не проанализировать, поэтому лучше обернуть его также в Option.
def parse(tokens: List[String]): Option[(Expr,List[String])] = tokens match {
case Variable(x) :: "=" :: rest =>
for ((expr,remains) <- parse(rest)) yield (Var(x,List(expr)), remains)
case Variable(x) :: rest => Some(Var(x,Nil), rest)
case Number(n) :: rest => Some(Num(n,Nil), rest)
case Unary(u) :: rest =>
for ((expr,remains) <- parse(rest)) yield (Una(u,List(expr)), remains)
case Binary(b) :: rest =>
for ((lexp,lrem) <- parse(rest); (rexp,rrem) <- parse(lrem)) yield
(Bin(b,List(lexp,rexp)), rrem)
case Nary(a) :: Natural(b) :: rest =>
val buffer = new collection.mutable.ArrayBuffer[Expr]
def parseN(tok: List[String], n: Int = b.toInt): List[String] = {
if (n <= 0) tok
else {
for ((expr,remains) <- parse(tok)) yield { buffer += expr; parseN(remains, n-1) }
}.getOrElse(tok)
}
val remains = parseN(rest)
if (buffer.length == b.toInt) Some( Nar(a,buffer.toList), remains )
else None
case _ => None
}
Обратите внимание, что мы используем сопоставление с образцом и рекурсию, чтобы выполнить большую часть тяжелой работы - мы выбираем часть списка, выясняем, сколько аргументов нам нужно, и передаем их рекурсивно. N-арная операция немного менее удобна, но мы создаем небольшую рекурсивную функцию, которая будет анализировать N вещей за один раз, сохраняя результаты в буфере.
Конечно, это немного недружелюбно для использования, поэтому мы добавили некоторые функции-обертки, которые позволили бы нам хорошо взаимодействовать с ним:
def parse(s: String): Option[Expr] = parse(s.split(" ").toList).flatMap(x => {
if (x._2.isEmpty) Some(x._1) else None
})
def parseLines(ls: List[String]): Option[Expr] = {
val attempt = ls.map(parse).flatten
if (attempt.length<ls.length) None
else if (attempt.length==1) attempt.headOption
else Some(Nar("list",attempt))
}
Хорошо, теперь как насчет упрощения? Одна вещь, которую мы могли бы сделать, это числовое упрощение , где мы предварительно вычисляем выражения и заменяем исходное выражение его сокращенной версией. Это похоже на рекурсивную операцию - найти числа и объединить их. Сначала мы получаем несколько вспомогательных функций для вычисления чисел:
def calc(n: Num, f: Double => Double): Num = Num(f(n.quantity).toString, Nil)
def calc(n: Num, m: Num, f: (Double,Double) => Double): Num =
Num(f(n.quantity,m.quantity).toString, Nil)
def calc(ln: List[Num], f: (Double,Double) => Double): Num =
Num(ln.map(_.quantity).reduceLeft(f).toString, Nil)
и затем мы делаем упрощение:
def numericSimplify(expr: Expr): Expr = expr match {
case Una(t,List(e)) => numericSimplify(e) match {
case n @ Num(_,_) => t match {
case "exp" => calc(n, math.exp _)
case "sin" => calc(n, math.sin _)
case "cos" => calc(n, math.cos _)
case "tan" => calc(n, math.tan _)
case "sqrt" => calc(n, math.sqrt _)
}
case a => Una(t,List(a))
}
case Bin(t,List(l,r)) => (numericSimplify(l), numericSimplify(r)) match {
case (n @ Num(_,_), m @ Num(_,_)) => t match {
case "+" => calc(n, m, _ + _)
case "-" => calc(n, m, _ - _)
case "*" => calc(n, m, _ * _)
case "/" => calc(n, m, _ / _)
case "^" => calc(n, m, math.pow)
}
case (a,b) => Bin(t,List(a,b))
}
case Nar("list",list) => Nar("list",list.map(numericSimplify))
case Nar(t,list) =>
val simple = list.map(numericSimplify)
val nums = simple.collect { case n @ Num(_,_) => n }
if (simple.length == 0) t match {
case "sum" => Num("0",Nil)
case "prod" => Num("1",Nil)
}
else if (nums.length == simple.length) t match {
case "sum" => calc(nums, _ + _)
case "prod" => calc(nums, _ * _)
}
else Nar(t, simple)
case Var(t,List(e)) => Var(t, List(numericSimplify(e)))
case _ => expr
}
Снова обратите внимание на интенсивное использование сопоставления с образцом, чтобы найти, когда мы находимся в хорошем случае, и отправить соответствующий расчет.
Теперь, конечно, алгебраическое замещение намного сложнее! На самом деле все, что вам нужно сделать, это заметить, что выражение уже использовано, и назначить переменную. Поскольку синтаксис, который я определил выше, допускает подстановку переменных на месте, мы можем на самом деле просто изменить наше дерево выражений, чтобы включить больше назначений переменных. Таким образом, мы делаем ( редактируется для вставки переменных, только если у пользователя нет ):
def algebraicSimplify(expr: Expr): Expr = {
val all, dup, used = new collection.mutable.HashSet[Expr]
val made = new collection.mutable.HashMap[Expr,Int]
val user = new collection.mutable.HashMap[Expr,Expr]
def findExpr(e: Expr) {
e match {
case Var(t,List(v)) =>
user += v -> e
if (all contains e) dup += e else all += e
case Var(_,_) | Num(_,_) => // Do nothing in these cases
case _ => if (all contains e) dup += e else all += e
}
e.args.foreach(findExpr)
}
findExpr(expr)
def replaceDup(e: Expr): Expr = {
if (made contains e) Var("x"+made(e),Nil)
else if (used contains e) Var(user(e).text,Nil)
else if (dup contains e) {
val fixed = replaceDupChildren(e)
made += e -> made.size
Var("x"+made(e),List(fixed))
}
else replaceDupChildren(e)
}
def replaceDupChildren(e: Expr): Expr = e match {
case Una(t,List(u)) => Una(t,List(replaceDup(u)))
case Bin(t,List(l,r)) => Bin(t,List(replaceDup(l),replaceDup(r)))
case Nar(t,list) => Nar(t,list.map(replaceDup))
case Var(t,List(v)) =>
used += v
Var(t,List(if (made contains v) replaceDup(v) else replaceDupChildren(v)))
case _ => e
}
replaceDup(expr)
}
Вот и все - полностью функциональная процедура алгебраической замены.Обратите внимание, что он формирует наборы выражений, которые он видел, отслеживая, какие из них являются дубликатами.Благодаря магии case-классов, все равенства определены для нас, так что это просто работает.Затем мы можем заменить любые дубликаты по мере их поиска, чтобы найти их.Обратите внимание, что процедура замены разделена пополам, и она совпадает с в незаменяемой версии дерева, но использует замененную версию.
Хорошо, теперь давайтедобавьте несколько тестов:
def main(args: Array[String]) {
val test1 = "- + ^ x 2 ^ y 2 1"
val test2 = "+ + +" // Bad!
val test3 = "exp sin cos sum 5" // Bad!
val test4 = "+ * 2 3 ^ 3 2"
val test5 = List(test1, test4, "^ y 2").mkString("list 3 "," ","")
val test6 = "+ + x y + + * + x y + 4 5 * + x y + 4 y + + x y + 4 y"
def performTest(test: String) = {
println("Start with: " + test)
val p = OpParser.parse(test)
if (p.isEmpty) println(" Parsing failed")
else {
println("Parsed: " + p.get)
val q = OpParser.numericSimplify(p.get)
println("Numeric: " + q)
val r = OpParser.algebraicSimplify(q)
println("Algebraic: " + r)
}
println
}
List(test1,test2,test3,test4,test5,test6).foreach(performTest)
}
}
Как это работает?
$ scalac OpParser.scala; scala OpParser
Start with: - + ^ x 2 ^ y 2 1
Parsed: (((x ^ 2) + (y ^ 2)) - 1)
Numeric: (((x ^ 2) + (y ^ 2)) - 1)
Algebraic: (((x ^ 2) + (y ^ 2)) - 1)
Start with: + + +
Parsing failed
Start with: exp sin cos sum 5
Parsing failed
Start with: + * 2 3 ^ 3 2
Parsed: ((2 * 3) + (3 ^ 2))
Numeric: 15.0
Algebraic: 15.0
Start with: list 3 - + ^ x 2 ^ y 2 1 + * 2 3 ^ 3 2 ^ y 2
Parsed: List[
1: (((x ^ 2) + (y ^ 2)) - 1)
2: ((2 * 3) + (3 ^ 2))
3: (y ^ 2)
]
Numeric: List[
1: (((x ^ 2) + (y ^ 2)) - 1)
2: 15.0
3: (y ^ 2)
]
Algebraic: List[
1: (((x ^ 2) + (x0 <- (y ^ 2))) - 1)
2: 15.0
3: x0
]
Start with: + + x y + + * + x y + 4 5 * + x y + 4 y + + x y + 4 y
Parsed: ((x + y) + ((((x + y) * (4 + 5)) + ((x + y) * (4 + y))) + ((x + y) + (4 + y))))
Numeric: ((x + y) + ((((x + y) * 9.0) + ((x + y) * (4 + y))) + ((x + y) + (4 + y))))
Algebraic: ((x0 <- (x + y)) + (((x0 * 9.0) + (x0 * (x1 <- (4 + y)))) + (x0 + x1)))
Так что я не знаю, полезно ли это для вас, но это оказывается полезным для меня.И именно с такими вещами я бы не решался заняться в C ++, потому что различные вещи, которые должны были быть легкими, оказывались болезненными.
Редактировать: Вот пример использования этой структурыпечатать временные назначения, просто чтобы продемонстрировать, что эта структура идеально подходит для таких вещей.
Код:
def useTempVars(expr: Expr): Expr = {
var n = 0
def temp = { n += 1; "t"+n }
def replaceTemp(e: Expr, exempt: Boolean = false): Expr = {
def varify(x: Expr) = if (exempt) x else Var(temp,List(x))
e match {
case Var(t,List(e)) => Var(t,List(replaceTemp(e, exempt = true)))
case Una(t,List(u)) => varify( Una(t, List(replaceTemp(u,false))) )
case Bin(t,lr) => varify( Bin(t, lr.map(replaceTemp(_,false))) )
case Nar(t,ls) => varify( Nar(t, ls.map(replaceTemp(_,false))) )
case _ => e
}
}
replaceTemp(expr)
}
def varCut(expr: Expr): Expr = expr match {
case Var(t,_) => Var(t,Nil)
case Una(t,List(u)) => Una(t,List(varCut(u)))
case Bin(t,lr) => Bin(t, lr.map(varCut))
case Nar(t,ls) => Nar(t, ls.map(varCut))
case _ => expr
}
def getAssignments(expr: Expr): List[Expr] = {
val children = expr.args.flatMap(getAssignments)
expr match {
case Var(t,List(e)) => children :+ expr
case _ => children
}
}
def listAssignments(expr: Expr): List[String] = {
getAssignments(expr).collect(e => e match {
case Var(t,List(v)) => t + " = " + varCut(v)
}) :+ (expr.text + " is the answer")
}
Выбранные результаты (из listAssignments(useTempVars(r)).foreach(printf(" %s\n",_))):
Start with: - + ^ x 2 ^ y 2 1
Assignments:
t1 = (x ^ 2)
t2 = (y ^ 2)
t3 = (t1 + t2)
t4 = (t3 - 1)
t4 is the answer
Start with: + + x y + + * + x y + 4 5 * + x y + 4 y + + x y + 4 y
Algebraic: ((x0 <- (x + y)) + (((x0 * 9.0) + (x0 * (x1 <- (4 + y)))) + (x0 + x1)))
Assignments:
x0 = (x + y)
t1 = (x0 * 9.0)
x1 = (4 + y)
t2 = (x0 * x1)
t3 = (t1 + t2)
t4 = (x0 + x1)
t5 = (t3 + t4)
t6 = (x0 + t5)
t6 is the answer
Второе редактирование: поиск зависимостей также не так уж плох.
Код:
def directDepends(expr: Expr): Set[Expr] = expr match {
case Var(t,_) => Set(expr)
case _ => expr.args.flatMap(directDepends).toSet
}
def indirectDepends(expr: Expr) = {
val depend = getAssignments(expr).map(e =>
e -> e.args.flatMap(directDepends).toSet
).toMap
val tagged = for ((k,v) <- depend) yield (k.text -> v.map(_.text))
def percolate(tags: Map[String,Set[String]]): Option[Map[String,Set[String]]] = {
val expand = for ((k,v) <- tags) yield (
k -> (v union v.flatMap(x => tags.get(x).getOrElse(Set())))
)
if (tags.exists(kv => expand(kv._1) contains kv._1)) None // Cyclic dependency!
else if (tags == expand) Some(tags)
else percolate(expand)
}
percolate(tagged)
}
def listDependents(expr: Expr): List[(String,String)] = {
def sayNothing(s: String) = if (s=="") "nothing" else s
val e = expr match {
case Var(_,_) => expr
case _ => Var("result",List(expr))
}
indirectDepends(e).map(_.toList.map(x =>
(x._1, sayNothing(x._2.toList.sorted.mkString(" ")))
)).getOrElse(List((e.text,"cyclic")))
}
И если мы добавим новые тестовые случаи val test7 = "list 3 z = ^ x 2 - + z ^ y 2 1 w = - z y" и val test8 = "list 2 x = y y = x" ипокажите ответы с помощью for ((v,d) <- listDependents(r)) println(" "+v+" requires "+d) мы получим (выбранные результаты):
Start with: - + ^ x 2 ^ y 2 1
Dependencies:
result requires x y
Start with: list 3 z = ^ x 2 - + z ^ y 2 1 w = - z y
Parsed: List[
1: (z <- (x ^ 2))
2: ((z + (y ^ 2)) - 1)
3: (w <- (z - y))
]
Dependencies:
z requires x
w requires x y z
result requires w x y z
Start with: list 2 x = y y = x
Parsed: List[
1: (x <- y)
2: (y <- x)
]
Dependencies:
result requires cyclic
Start with: + + x y + + * + x y + 4 5 * + x y + 4 y + + x y + 4 y
Algebraic: ((x0 <- (x + y)) + (((x0 * 9.0) + (x0 * (x1 <- (4 + y)))) + (x0 + x1)))
Dependencies:
x0 requires x y
x1 requires y
result requires x x0 x1 y
Так что я думаю, что на вершине такой структуры все ваши индивидуальные требования удовлетворяются блоками из одной или двух дюжин строккода Scala.
Редактировать: вот оценка выражения, если вам дано сопоставление из переменных в значения:
def numericEvaluate(expr: Expr, initialValues: Map[String,Double]) = {
val chain = new collection.mutable.ArrayBuffer[(String,Double)]
val evaluated = new collection.mutable.HashMap[String,Double]
def note(xv: (String,Double)) { chain += xv; evaluated += xv }
evaluated ++= initialValues
def substitute(expr: Expr): Expr = expr match {
case Var(t,List(n @ Num(v,_))) => { note(t -> v.toDouble); n }
case Var(t,_) if (evaluated contains t) => Num(evaluated(t).toString,Nil)
case Var(t,ls) => Var(t,ls.map(substitute))
case Una(t,List(u)) => Una(t,List(substitute(u)))
case Bin(t,ls) => Bin(t,ls.map(substitute))
case Nar(t,ls) => Nar(t,ls.map(substitute))
case _ => expr
}
def recurse(e: Expr): Expr = {
val sub = numericSimplify(substitute(e))
if (sub == e) e else recurse(sub)
}
(recurse(expr), chain.toList)
}
, и это используется так же в процедуре тестирования:
val (num,ops) = numericEvaluate(r,Map("x"->3,"y"->1.5))
println("Evaluated:")
for ((v,n) <- ops) println(" "+v+" = "+n)
println(" result = " + num)
дает результатыкак эти (с вводом x = 3 и y = 1.5):
Start with: list 3 - + ^ x 2 ^ y 2 1 + * 2 3 ^ 3 2 ^ y 2
Algebraic: List[
1: (((x ^ 2) + (x0 <- (y ^ 2))) - 1)
2: 15.0
3: x0
]
Evaluated:
x0 = 2.25
result = List[
1: 10.25
2: 15.0
3: 2.25
]
Start with: list 3 z = ^ x 2 - + z ^ y 2 1 w = - z y
Algebraic: List[
1: (z <- (x ^ 2))
2: ((z + (y ^ 2)) - 1)
3: (w <- (z - y))
]
Evaluated:
z = 9.0
w = 7.5
result = List[
1: 9.0
2: 10.25
3: 7.5
]
Другая задача - выбрать переменные, которые еще не использовались - просто установить вычитание из зависимостейresult список.diff - это название метода вычитания.