4

文字列として表される括弧の1つの親グループを取得し、括弧の各サブグループを別の文字にマップするScalaメソッドを作成しようとしています。次に、これらをマップに配置して返す必要があるため、基本的には次のようなメソッドを呼び出します。

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

ここで、sには任意の数の括弧のセットを含めることができ、返されるマップには次のものが含まれている必要があります。

"(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メソッドを作成する簡単な（または簡単ではない）方法を誰かが知っているかどうか疑問に思いました。

4

3 に答える 3

3

これは、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)

望んだ通りに。より興味深い演習（読者に任せます）は、可変キューを回避するために、ある状態をパーサーに通すことです。

于 2012-09-15T23:34:11.583 に答える
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)

再帰が再帰構造を解析するための非常に強力な方法であるというヒントとともに、それがどのように機能するかを理解するための演習として読者に任せます。

于 2012-09-15T22:21:52.483 に答える
0 
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
  }

Optionこれは、解析された場合に a を含む を出力しますMap。これは、解析されなかった場合に例外をスローするよりも優れています。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
于 2012-09-17T00:06:27.710 に答える