解析值

Question

我只是在擺弄奇怪地發現這是一個有點棘手的一個簡單的遞歸函數解析嵌套的括號內。

例如，如果該計劃的目的是查找用戶的詳細信息，它可能會從{{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") 

任何想法的代碼乾淨一點，可以更換???將是巨大的。這主要是出於好奇，我正在尋找一個優雅的解決這個問題。

Answer 1

解析器組合可以處理這種情況：

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]。
• 的^^運營商可以通過做^^ {_.toInt}
• Parser是一個單子和Parser[T].^^(f)一個函數應用於解析的元素
  • 它可以在Parser[String]轉換爲Parser[Int]相當於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)
• rep1是一個或多個元素的重複
• |嘗試ma在左邊輸入解析器，如果失敗則嘗試右邊的解析器

Answer 2

如何

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 
} 

我知道這是醜陋的，但我認爲它工作正常。