3

私はただふざけていて、不思議なことに、単純な再帰関数でネストされたブラケットを解析するのが少し難しいことに気づきました。

たとえば、プログラムがユーザーの詳細を検索することを目的としている場合、 から{{name surname} age}へ{Bob Builder age}、次に へと移動する可能性がありBob Builder 20ます。

これは、概念を示す中括弧内の合計を合計するためのミニプログラムです。

  // Parses string recursively by eliminating brackets
  def parse(s: String): String = {
    if (!s.contains("{")) s
    else {
      parse(resolvePair(s))
    }
  }

  // Sums one pair and returns the string, starting at deepest nested pair
  // e.g.
  // {2+10} lollies and {3+{4+5}} peanuts
  // should return:
  // {2+10} lollies and {3+9} peanuts
  def resolvePair(s: String): String = {
    ??? // Replace the deepest nested pair with it's sumString result
  }

  // Sums values in a string, returning the result as a string
  // e.g. sumString("3+8") returns "11"
  def sumString(s: String): String = {
    val v = s.split("\\+")
    v.foldLeft(0)(_.toInt + _.toInt).toString
  }

  // Should return "12 lollies and 12 peanuts"
  parse("{2+10} lollies and {3+{4+5}} peanuts")

を置き換えることができるクリーンなコードのアイデアは???素晴らしいでしょう。この問題に対するエレガントな解決策を探しているのは、ほとんど好奇心からです。

4

2 に答える 2

6

パーサーコンビネーターは、この種の状況を処理できます。

import scala.util.parsing.combinator.RegexParsers
object BraceParser extends RegexParsers {
  override def skipWhitespace = false
  def number = """\d+""".r ^^ { _.toInt }
  def sum: Parser[Int] = "{" ~> (number | sum) ~ "+" ~ (number | sum) <~ "}" ^^ {
    case x ~ "+" ~ y => x + y
  }
  def text = """[^{}]+""".r
  def chunk = sum ^^ {_.toString } | text
  def chunks = rep1(chunk) ^^ {_.mkString} | ""
  def apply(input: String): String = parseAll(chunks, input) match {
    case Success(result, _) => result
    case failure: NoSuccess => scala.sys.error(failure.msg)
  }
}

それで：

BraceParser("{2+10} lollies and {3+{4+5}} peanuts")
//> res0: String = 12 lollies and 12 peanuts

パーサーコンビネータに慣れるまでには多少の投資が必要ですが、それだけの価値があると思います。

上記の構文を解読するには、次のようにします。

  • 正規表現と文字列には、文字列の結果でプリミティブ パーサーを作成するための暗黙的な変換があり、型はParser[String].
  • 演算子は^^、解析された要素に関数を適用できます
    • することで aParser[String]を a に変換できますParser[Int]^^ {_.toInt}
    • パーサーはモナドでありParser[T].^^(f)、Parser[T].map(f)
  • 、およびいくつかの入力が特定の順序である必要があり ~ます~><~
    • 結果から入力の片側を削除し~>ます<~
    • 結果のcase a ~ bパターンマッチを許可します
    • パーサーはモナドであり(p ~ q) ^^ { case a ~ b => f(a, b) }、for (a <- p; b <- q) yield (f(a, b))
    • (p <~ q) ^^ fと同等ですfor (a <- p; _ <- q) yield f(a)
  • rep11 つ以上の要素の繰り返しです
  • |入力を左側のパーサーと照合しようとし、失敗した場合は右側のパーサーを試します
于 2013-06-13T07:11:32.710 に答える
1

どうですか

def resolvePair(s: String): String = {
val open = s.lastIndexOf('{')
val close = s.indexOf('}', open)
if((open >= 0) && (close > open)) {
    val (a,b) = s.splitAt(open+1)
    val (c,d) = b.splitAt(close-open-1)
    resolvePair(a.dropRight(1)+sumString(c).toString+d.drop(1))
} else
    s
}

私はそれが醜いことを知っていますが、うまくいくと思います。

于 2013-06-12T23:56:45.430 に答える