string – 将括号子集映射到chars

发布时间：2020-12-16 10:03:35 所属栏目：安全来源：网络整理

导读：我正在尝试创建一个 Scala方法,该方法将采用括号的一个父组(表示为String),然后将每个括号子组映射到不同的字母.然后它应该将它们放在它返回的地图中,所以基本上我调用以下方法： val s = "((2((x+3)+6)))"val map = mapParentheses(s) 其中s可以包含任意数

我正在尝试创建一个 Scala方法,该方法将采用括号的一个父组(表示为String),然后将每个括号子组映射到不同的字母.然后它应该将它们放在它返回的地图中,所以基本上我调用以下方法：

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方法的简单(或不容易)方法.

解决方法

经典的递归解析问题.保持不同的位可以很方便.我们将添加一些实用方法来帮助我们以后.

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)

我将把它作为练习留给读者来弄清楚它是如何工作的,提示递归是解析递归结构的一种非常强大的方法.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!