将括号的子集映射到字符 [英] Mapping sub-sets of parentheses to chars

问题描述

我正在尝试创建一个Scala方法，该方法将使用一组括号，以String形式表示，然后将每个子组的括号映射到其他字母。那么它应该将它们放在一个返回的地图中，所以基本上我调用如下这样的方法：

I am attempting to create a Scala method that will take one parent group of parentheses, represented as a String, and then map each subgroup of parentheses to a different letter. It should then put these in a map which it returns, so basically I call the following method like this:

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

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

Where s could contain any number of sets of parentheses, and the Map returned should contain:

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

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

"(2b)" -> 'c'

"(c)" -> 'd'

所以我程序中的其他地方我可以回忆起'd'（c），将成为（（2b））然后（（2（a + 6）））最后（（2（（x + 3）+6）））。发送到方法 mapParentheses 的字符串将永远不会有不匹配的括号或主要父括号外的额外字符，因此以下项目将永远不会发送：

So that elsewhere in my program I can recall 'd' and get "(c)" which will become "((2b))" then ((2(a+6))) and finally ((2((x+3)+6))). The string sent to the method mapParentheses will never have unmatched parentheses, or extra chars outside of the main parent parentheses, so the following items will never be sent:

• （fsf）a因为 a 在父括号之外
$ （a（aa））（a），因为（a）在父括号之外

• （（a）因为括号不匹配


• ）a（括号是不可比拟的

• "(fsf)a" because the a is outside the parent parentheses
• "(a(aa))(a)" because the (a) is outside the parent parentheses
• "((a)" because the parentheses are unmatched
• ")a(" because the parentheses are unmatched

所以我想知道是否有人知道一个简单（或不容易）的方法来创建这个 mapParentheses

So I was wondering if anyone knew of an easy (or not easy) way of creating this mapParentheses method.

推荐答案

经典递归解析问题，可以方便地保存不同的位，我们将添加一些实用的方法来帮助我们。

Classic recursive parsing problem. It can be handy to hold the different bits. We'll add a few utility methods to help us out later.

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
}

现在你需要解析这些东西：

Now you need to parse into these things:

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)
}

现在我们解决了整件事情。所以让我们找到所有的一切。

Now we've got the whole thing parsed. So let's find all the bits.

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

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

Now we can build the map you want.

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)

我会把它作为一个练习，让读者知道它是如何工作的，提示递归是解析递归结构的一个非常强大的方法。

I will leave it as an exercise to the reader to figure out how it works, with the hint that recursion is a really powerful way to parse recursive structures.

这篇关于将括号的子集映射到字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！