将括号子集映射到字符

Question

我正在尝试创建一个Scala方法，它将采用一个由字符串表示的父括号组，并将每个子括号组映射到不同的字母。然后，它应该将这些放入一个Map中并返回，因此基本上我像这样调用以下方法：

val s = "((2((x+3)+6)))"
val map = mapParentheses(s)

其中 s 可以包含任意数量的括号集合，返回的 Map 应包含：

"(x+3)" -> 'a'

"(a+6)" -> 'b'

"(2b)" -> 'c'

"(c)" -> 'd'

所以，在我的程序中，我可以调用“d”并获取“(c)”，它将变成“((2b))”，然后是“((2(a+6)))”，最后是“((2((x+3)+6)))”。发送到方法“mapParentheses”的字符串永远不会有不匹配的括号或主要父括号之外的额外字符，因此永远不会发送以下项目：

• "(fsf)a" 因为 a 在父括号之外
• "(a(aa))(a)" 因为 (a) 在父括号之外
• "((a)" 因为括号不匹配
• ")a(" 因为括号不匹配

所以我想知道是否有人知道创建这个“mapParentheses”方法的简单（或困难）方法。

- Seren

---

你能在同一层级上有多个括号嵌套吗（例如：((x+1)+(y+2))）？ - Travis Brown

@TravisBrown - 没关系。字符串保证是正确的，而且一般解决方案和假设同一级别不会有多个块的解决方案一样简单。 - Rex Kerr

@RexKerr：如果您知道每个级别只有一个，那么可以编写一个稍微更好的解析器组合器版本。 - Travis Brown

@TravisBrown - 好的，你已经证明了这一点，我同意。 - Rex Kerr

@TravisBrown - 是的，任何括号的组合都是可能的，但整个字符串将被包含在一对“父”括号中。 - Seren

Answer 1

你可以很容易地使用Scala的解析器组合器来完成这个任务。首先是导入和一些简单的数据结构：

import scala.collection.mutable.Queue
import scala.util.parsing.combinator._

sealed trait Block {
  def text: String
}

case class Stuff(text: String) extends Block

case class Paren(m: List[(String, Char)]) extends Block {
  val text = m.head._2.toString
  def toMap = m.map { case (k, v) => "(" + k + ")" -> v }.toMap
}

即一个块表示输入的子字符串，它可以是非括号内容，也可以是括号中的内容。

现在来看解析器本身：

class ParenParser(fresh: Queue[Char]) extends RegexParsers {
  val stuff: Parser[Stuff] = "[^\\(\\)]+".r ^^ (Stuff(_))

  def paren: Parser[Paren] = ("(" ~> insides <~ ")") ^^ {
    case (s, m) => Paren((s -> fresh.dequeue) :: m)
  }

  def insides: Parser[(String, List[(String, Char)])] =
    rep1(paren | stuff) ^^ { blocks =>
      val s = blocks.flatMap(_.text)(collection.breakOut)
      val m = blocks.collect {
        case Paren(n) => n
      }.foldLeft(List.empty[(String, Char)])(_ ++ _)
      (s, m)
    }

  def parse(input: String) = this.parseAll(paren, input).get.toMap
}

在最后一行使用get并不是理想的选择，但是可以通过您的声明来证明我们可以期望输入格式良好。

现在我们可以创建一个新的解析器，并将一个可变队列和一些新的变量传递进去：

val parser = new ParenParser(Queue('a', 'b', 'c', 'd', 'e', 'f'))

现在尝试使用您的测试字符串：

scala> println(parser parse "((2((x+3)+6)))")
Map((c) -> d, (2b) -> c, (a+6) -> b, (x+3) -> a)

按要求翻译如下:

好的。一项更有趣的练习(留给读者完成)是通过解析器来传递一些状态，以避免使用可变队列。

- Travis Brown

---

你觉得使用 Iterator[Char]（或者 => Char）作为参数会更好，这样如果需要的话就可以生成一个无限的数据源。 - Rex Kerr

Answer 2

这是一个经典的递归解析问题。将不同的部分保存起来可能很有用。稍后我们会添加一些实用方法来帮助我们。

trait Part {
  def text: String
  override def toString = text
}
class Text(val text: String) extends Part {}
class Parens(val contents: Seq[Part]) extends Part {
  val text = "(" + contents.mkString + ")"
  def mapText(m: Map[Parens, Char]) = {
    val inside = contents.collect{
      case p: Parens => m(p).toString
      case x => x.toString
    }
    "(" + inside.mkString + ")"
  }
  override def equals(a: Any) = a match {
    case p: Parens => text == p.text
    case _ => false
  }
  override def hashCode = text.hashCode
}

现在你需要解析这些内容：

def str2parens(s: String): (Parens, String) = {
  def fail = throw new Exception("Wait, you told me the input would be perfect.")
  if (s(0) != '(') fail
  def parts(s: String, found: Seq[Part] = Vector.empty): (Seq[Part], String) = {
    if (s(0)==')') (found,s)
    else if (s(0)=='(') {
      val (p,s2) = str2parens(s)
      parts(s2, found :+ p)
    }
    else {
      val (tx,s2) = s.span(c => c != '(' && c != ')')
      parts(s2, found :+ new Text(tx))
    }
  }
  val (inside, more) = parts(s.tail)
  if (more(0)!=')') fail
  (new Parens(inside), more.tail)
}

现在我们已经解析了整个内容，接下来让我们找到其中的所有部分。

def findParens(p: Parens): Set[Parens] = {
  val inside = p.contents.collect{ case q: Parens => findParens(q) }
  inside.foldLeft(Set(p)){_ | _}
}

现在我们可以构建您想要的地图。

def mapParentheses(s: String) = {
  val (p,_) = str2parens(s)
  val pmap = findParens(p).toSeq.sortBy(_.text.length).zipWithIndex.toMap
  val p2c = pmap.mapValues(i => ('a'+i).toChar)
  p2c.map{ case(p,c) => (p.mapText(p2c), c) }.toMap
}

它有效的证据：

scala> val s = "((2((x+3)+6)))"
s: java.lang.String = ((2((x+3)+6)))

scala> val map = mapParentheses(s)
map: scala.collection.immutable.Map[java.lang.String,Char] =
  Map((x+3) -> a, (a+6) -> b, (2b) -> c, (c) -> d)

我将把它留给读者作为一个练习，提示是递归是解析递归结构的一种非常强大的方法。

- Rex Kerr

---

为什么要在标准库中使用解析器组合器时还要遭受所有这些 if (x(0)=='(') 的煎熬呢？ - Travis Brown

@TravisBrown - 因为当你有一个几乎微不足道的任务时，添加解析库的认知负担是不值得的，如果你想要理解解决方案的工作原理（而不仅仅是它是否有效）。 - Rex Kerr

还不错，虽然我认为解析器组合方法实际上使问题的结构更加清晰，即使在这样一个相当简单的情况下。 - Travis Brown

@TravisBrown - 这确实使一些部分更清晰，但是还有一些需要理解的"魔法"。一旦你理解了表面层和内部的魔法，我同意这是一种更好的表达问题逻辑结构的方式。 - Rex Kerr

Answer 3

def parse(s: String, 
  c: Char = 'a', out: Map[Char, String] = Map() ): Option[Map[Char, String]] =
  """\([^\(\)]*\)""".r.findFirstIn(s) match {
    case Some(m) => parse(s.replace(m, c.toString), (c + 1).toChar , out + (c -> m))
    case None if s.length == 1 => Some(out)
    case _ => None
  }

如果解析成功，这将输出包含Map的Option，这比抛出异常更好。我猜你真正想要的是从Char到String的映射，所以这就是它的输出结果。c和out是默认参数，因此您不需要自己输入它们。正则表达式的意思是“任意数量的不是括号的字符，被括号包围”（括号字符需要用“\”转义）。findFirstIn查找第一个匹配项并返回Option[String]，我们可以对其进行模式匹配，将该字符串替换为相关字符。

val s = "((2((x+3)+6)))"
parse(s)  //Some(Map(a -> (x+3), b -> (a+6), c -> (2b), d -> (c)))
parse("(a(aa))(a)") //None

- Luigi Plinge