我只是在开玩笑,奇怪地发现在简单的递归函数中解析嵌套括号有点棘手。
例如,如果程序的目的是查找用户详细信息,它可能来自{{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")
任何可以替代的干净代码的想法???
会很好。主要是出于好奇,我正在寻找解决这个问题的优雅方法。
解析器组合器可以处理这种情况:
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)
}
}
Then:
BraceParser("{2+10} lollies and {3+{4+5}} peanuts")
//> res0: String = 12 lollies and 12 peanuts
在熟悉解析器组合器之前需要进行一些投资,但我认为这确实值得。
为了帮助您解读上面的语法:
- 正则表达式和字符串具有隐式转换,可以使用字符串结果创建原始解析器,它们具有类型
Parser[String]
.
- the
^^
operator allows to apply a function to the parsed elements
- 它可以转换一个
Parser[String]
into a Parser[Int]
通过做^^ {_.toInt}
- 解析器是一个 monad 并且
Parser[T].^^(f)
相当于Parser[T].map(f)
- the
~
, ~>
and <~
requires some inputs to be in a certain sequence
- the
~>
and <~
从结果中删除输入的一侧
- the
case a ~ b
允许对结果进行模式匹配
- 解析器是一个 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 个或多个元素的重复
-
|
尝试将输入与其左侧的解析器进行匹配,如果失败,它将尝试右侧的解析器
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)