解析嵌套在方括号内的值

问题描述

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

I'm just fooling about and strangely found it a bit tricky to parse nested brackets in a simple recursive function.

例如，如果程序打算使用它来查找用户详细信息，则它可能从{{name surname} age}到{Bob Builder age}，然后到Bob Builder 20.

For example, if the program's purpose it to lookup user details, it may go from {{name surname} age} to {Bob Builder age} and then to Bob Builder 20.

这里是一个小程序，用于将总计放在大括号中，以证明这一概念.

Here is a mini-program for summing totals in curly brackets that demonstrates the concept.

  // 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")

任何干净的代码都可以代替???的想法都很棒.我寻求好奇心解决这个问题主要是出于好奇.

Any ideas to a clean bit of code that could replace the ??? would be great. It's mostly out of curiosity that I'm searching for an elegant solution to this problem.

推荐答案

解析器组合器可以处理这种情况:

Parser combinators can handle this kind of situation:

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

在适应解析器组合器之前需要进行一些投资，但是我认为这确实值得.

There is some investment before getting comfortable with parser combinators but I think it is really worth it.

为帮助您解释以上语法:

To help you decipher the syntax above:

• 正则表达式和字符串具有隐式转换，以创建具有字符串结果的原始解析器，它们的类型为Parser[String].
• ^^运算符允许将函数应用于已解析的元素
  • 它可以通过执行^^ {_.toInt}
  将Parser[String]转换为Parser[Int]
  • 解析器是monad，而Parser[T].^^(f)等同于Parser[T].map(f)
  • regular expression and strings have implicit conversions to create primitive parsers with strings results, they have type Parser[String].
  • the ^^ operator allows to apply a function to the parsed elements
    • it can convert a Parser[String] into a Parser[Int] by doing ^^ {_.toInt}
    • Parser is a monad and Parser[T].^^(f) is equivalent to Parser[T].map(f)
    • ~>和<~将输入的一侧从结果中删除
    • 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)
    • the ~> and <~ drop one side of the input out of the result
    • the case a ~ b allows to pattern match the results
    • Parser is a monad and (p ~ q) ^^ { case a ~ b => f(a, b) } is equivalent to for (a <- p; b <- q) yield (f(a, b))
    • (p <~ q) ^^ f is equivalent to for (a <- p; _ <- q) yield f(a)

    这篇关于解析嵌套在方括号内的值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！