3

我只是在开玩笑，奇怪地发现在一个简单的递归函数中解析嵌套括号有点棘手。

例如，如果程序的目的是查找用户详细信息，则它可能会从{{name surname} age}to{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

在熟悉解析器组合器之前需要进行一些投资，但我认为这真的是值得的。

为了帮助您破译上面的语法：

  • 正则表达式和字符串具有隐式转换以创建具有字符串结果的原始解析器，它们具有 type Parser[String]。
  • 运算符^^允许将函数应用于已解析的元素
    • 它可以通过做将 a 转换Parser[String]为 aParser[Int]^^ {_.toInt}
    • Parser 是一个 monad，Parser[T].^^(f)相当于Parser[T].map(f)
  • ,并且要求某些输入按特定顺序 ~排列~><~
    • 并将输入的一侧从结果中~>删除<~
    • 允许case a ~ b模式匹配结果
    • Parser 是一个 monad，(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是 1 个或多个元素的重复
  • |尝试将输入与左侧的解析器匹配，如果失败，它将尝试右侧的解析器
于 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 回答