古典的な再帰解析の問題。さまざまなビットを保持すると便利な場合があります。後で役立つように、いくつかのユーティリティメソッドを追加します。
trait Part {
def text: String
override def toString = text
}
class Text(val text: String) extends Part {}
class Parens(val contents: Seq[Part]) extends Part {
val text = "(" + contents.mkString + ")"
def mapText(m: Map[Parens, Char]) = {
val inside = contents.collect{
case p: Parens => m(p).toString
case x => x.toString
}
"(" + inside.mkString + ")"
}
override def equals(a: Any) = a match {
case p: Parens => text == p.text
case _ => false
}
override def hashCode = text.hashCode
}
次に、これらのことを解析する必要があります。
def str2parens(s: String): (Parens, String) = {
def fail = throw new Exception("Wait, you told me the input would be perfect.")
if (s(0) != '(') fail
def parts(s: String, found: Seq[Part] = Vector.empty): (Seq[Part], String) = {
if (s(0)==')') (found,s)
else if (s(0)=='(') {
val (p,s2) = str2parens(s)
parts(s2, found :+ p)
}
else {
val (tx,s2) = s.span(c => c != '(' && c != ')')
parts(s2, found :+ new Text(tx))
}
}
val (inside, more) = parts(s.tail)
if (more(0)!=')') fail
(new Parens(inside), more.tail)
}
これで、すべてが解析されました。それでは、すべてのビットを見つけましょう。
def findParens(p: Parens): Set[Parens] = {
val inside = p.contents.collect{ case q: Parens => findParens(q) }
inside.foldLeft(Set(p)){_ | _}
}
これで、必要なマップを作成できます。
def mapParentheses(s: String) = {
val (p,_) = str2parens(s)
val pmap = findParens(p).toSeq.sortBy(_.text.length).zipWithIndex.toMap
val p2c = pmap.mapValues(i => ('a'+i).toChar)
p2c.map{ case(p,c) => (p.mapText(p2c), c) }.toMap
}
それが機能するという証拠:
scala> val s = "((2((x+3)+6)))"
s: java.lang.String = ((2((x+3)+6)))
scala> val map = mapParentheses(s)
map: scala.collection.immutable.Map[java.lang.String,Char] =
Map((x+3) -> a, (a+6) -> b, (2b) -> c, (c) -> d)
再帰が再帰構造を解析するための非常に強力な方法であるというヒントとともに、それがどのように機能するかを理解するための演習として読者に任せます。