ShuntingYard-Algorithmus in Scala

Letzte Woche bin ich im Blog von Object Mentor auf eine interessante "Coding Kata" von Brett Schuchert gestoßen. Der Trick bei einer Kata ist, dass Sie das Programm Schritt für Schritt mit Hilfe von Tests wachsen lassen, so wie eine Kata im Karate einem Schüler beigebracht wird. Das Problem dieser Kata war der Shunting Yard-Algorithmus von Dijkstra. Ich wollte sehen, ob ich diese Kata in Scala implementieren kann.

Anstatt den Algorithmus wie beschrieben zu schreiben, besteht der Trick in einer Coding Kata darin, dass Sie zuerst einen Test schreiben und dann dafür sorgen, dass der Test besteht. Und anschließend jedes Mal einen Test hinzufügen und alles im grünen Bereich halten. Brett hat die Testfälle in seinem Blogeintrag beschrieben. Der Shunting Yard-Algorithmus wird verwendet, um eine mathematische Funktion in Infix-Notation in eine umgekehrte polnische oder Postfix-Notation umzuwandeln. Zum Beispiel kann er einen Ausdruck wie 3+4 in 3 4 + umwandeln. Um diesen Algorithmus zu implementieren, muss man ein String-Parsing durchführen, um den Infix-String aufzubrechen. Scala verfügt über die Parser-Kombinatoren, die genau das tun können. Mit einem Parser baue ich einen abstrakten Syntaxbaum (AST) auf, der die Formel in Form eines Baumes darstellt. Ein AST für 3 + 4 und (3 + 4) * 4 sieht so aus:

Die AST-Darstellung der Formel kann dann einfach in umgekehrter polnischer Notation ausgegeben werden, wie der Code zeigt. Der endgültige Parser sieht wie folgt aus: [scala] import scala.util.parsing.combinator.syntactical. abstract class Expr { def rpn:String } case class BinaryOperator(lhs:Expr, op:String, rhs:Expr) extends Expr { def rpn:String = lhs.rpn + " " + rhs.rpn + " " + op } case class Number(v:String) extends Expr { def rpn:String = v } case class Variable(v:String) extends Expr { def rpn:String = v } case class Function(f:String, e:List[Expr]) extends Expr { def rpn:String = { var s = "" e.foreach { x => s += x.rpn + " " } s += f Rückgabe s } } object ShuntingYard extends StandardTokenParsers { lexical.delimiters ++= List("+","-", "*","/", "^","(",")",",") def Wert :Parser[Expr] = numericLit ^^ { s => Nummer(n) } def variable:Parser[Expr] = ident ^^ { s => Variable(n) } def parens:Parser[Expr] = "(" ~> expr <~ ")" def argument:Parser[Expr] = expr <~ (","?) def func:Parser[Expr] = ( ident ~ "(" ~ (argument+) ~ ")" ^^ { case f ~ ~ e ~ => Function(f, e) }) def term = (value | parens | func | variable) // Muss rekursiv definiert werden, da ^ rechts-assoziativ ist def pow :Parser[Expr] = ( term ~ "^" ~ pow ^^ {case left ~ ~ right ~> BinaryOperator(links, "^", rechts) }| Begriff) def factor = pow ( "" ^^^ { (left:Expr, right:Expr) = > BinaryOperator(links, "", rechts) } | "/" ^^^ { (left:Expr, right:Expr) => BinaryOperator(left, "/", right) } ) def Summe = Faktor ("+" ^^^ { (links:Expr, rechts:Expr) => BinaryOperator(links, "+", rechts) } | "-" ^^^ { (links:Expr, rechts:Expr) => BinaryOperator(links, "-", rechts) } ) def expr = ( Summe | Begriff ) def parse(s:String) = { val tokens = new lexical.Scanner(s) phrase(expr)(tokens) } def shunt(exprstr: String) : String = exprstr match { case null => return "" Fall "" => return "" Fall => parse(exprstr) match { case Success(tree, ) => println("Tree: "+tree) val v = tree.rpn println("RPN: "+v) return v case e: NoSuccess => Console.err.println(e) return e.toString } } } [/scala] Natürlich habe ich dies anhand des folgenden Unit-Tests getestet, von dem ich nur einen kleinen Teil zeigen werde. Man kann dies leicht vervollständigen, indem man sich Bretts Beispiele ansieht: [scala] importieren org.junit.Test import org.junit.Assert._ Klasse ShuntingYardTest { @Test def test_11() { assertEquals("4 g f", ShuntingYard.shunt("f(g(4))")) } @Test def test_12() { assertEquals("3 4 19 f", ShuntingYard.shunt("f(3, 4, 19)")) } @Test def test_13() { assertEquals("3 4 2 1 5 - 2 3 ^ ^ / +", ShuntingYard.shunt("3 + 4 2 / ( 1 - 5 ) ^ 2 ^ 3")) } @Test def test_14 () { assertEquals("4 5 + 1 a 2 ^ + 8 b + 10 f ", ShuntingYard.shunt("f(4+5,1+a^2,(8+b)10)")) } } [/scala] Von allen Tests, die Brett definiert hat, besteht nur einer nicht. Können Sie erkennen, welcher das ist? Da dies natürlich eine meiner ersten Übungen in Scala ist, ist sie wahrscheinlich noch nicht optimal. Verbesserungen sind in den Kommentaren willkommen!