Скобки, совпадающие в Scala --- функциональном подходе

Скажем, я хочу проанализировать строку с различными открывающими и закрывающимися скобками (я использовал круглые скобки в заголовке, потому что я считаю, что это более распространено - вопрос тем не менее тем не менее), так что я получаю все более высокие уровни, разделенные список.

Учитывая:

[hello:=[notting],[hill]][3.4(4.56676|5.67787)][the[hill[is[high]]not]]

Я хочу:

List("[hello:=[notting],[hill]]", "[3.4(4.56676|5.67787)]", "[the[hill[is[high]]not]]")

То, как я это делаю, это подсчет открывающих и закрывающих скобок и добавление в список всякий раз, когда я получаю свой счетчик 0. Однако у меня есть уродливый императивный код. Вы можете предположить, что исходная строка хорошо сформирована.

Мой вопрос: что было бы хорошим функциональным подходом к этой проблеме?

Примечания: Я подумал о том, чтобы использовать конструкцию for... yield, но при использовании счетчиков я не могу получить простой условный (у меня должны быть условия только для обновления счетчиков), и я не знаю, как я мог бы использовать эту конструкцию в этом случае.

Ответ 1

Быстрое решение, использующее библиотеку комбинаторов парсеров Scala:

import util.parsing.combinator.RegexParsers

object Parser extends RegexParsers {
  lazy val t = "[^\\[\\]\\(\\)]+".r

  def paren: Parser[String] =
    ("(" ~ rep1(t | paren) ~ ")" |
     "[" ~ rep1(t | paren) ~ "]") ^^ {
      case o ~ l ~ c => (o :: l ::: c :: Nil) mkString ""
    }

  def all = rep(paren)

  def apply(s: String) = parseAll(all, s)
}

Проверка в REPL:

scala> Parser("[hello:=[notting],[hill]][3.4(4.56676|5.67787)][the[hill[is[high]]not]]")
res0: Parser.ParseResult[List[String]] = [1.72] parsed: List([hello:=[notting],[hill]], [3.4(4.56676|5.67787)], [the[hill[is[high]]not]])

Ответ 2

Как насчет:

def split(input: String): List[String] = {
  def loop(pos: Int, ends: List[Int], xs: List[String]): List[String] =
    if (pos >= 0)
      if ((input charAt pos) == ']') loop(pos-1, pos+1 :: ends, xs)
      else if ((input charAt pos) == '[')
        if (ends.size == 1) loop(pos-1, Nil, input.substring(pos, ends.head) :: xs)
        else loop(pos-1, ends.tail, xs)
      else loop(pos-1, ends, xs)
    else xs
  loop(input.length-1, Nil, Nil)
}

scala> val s1 = "[hello:=[notting],[hill]][3.4(4.56676|5.67787)][the[hill[is[high]]not]]"
s1: String = [hello:=[notting],[hill]][3.4(4.56676|5.67787)][the[hill[is[high]]not]]

scala> val s2 = "[f[sad][add]dir][er][p]"
s2: String = [f[sad][add]dir][er][p]

scala> split(s1) foreach println
[hello:=[notting],[hill]]
[3.4(4.56676|5.67787)]
[the[hill[is[high]]not]]

scala> split(s2) foreach println
[f[sad][add]dir]
[er]
[p]

Ответ 3

Учитывая ваши требования, подсчет скобок кажется совершенно прекрасным. Как бы вы это сделали функционально? Вы можете явно передать состояние.

Итак, сначала мы определяем наше состояние, которое накапливает результаты в blocks или объединяет следующий block и отслеживает глубину:

case class Parsed(blocks: Vector[String], block: String, depth: Int)

Затем мы записываем чистую обработанную функцию, которая возвращает следующее состояние. Надеюсь, мы можем просто внимательно рассмотреть эту функцию и убедиться в ее правильности.

def nextChar(parsed: Parsed, c: Char): Parsed = {
  import parsed._
  c match {
    case '[' | '(' => parsed.copy(block = block + c,
                                  depth = depth + 1)
    case ']' | ')' if depth == 1 
                   => parsed.copy(blocks = blocks :+ (block + c),
                                  block = "",
                                  depth = depth - 1)
    case ']' | ')' => parsed.copy(block = block + c,
                                  depth = depth - 1)
    case _         => parsed.copy(block = block + c)
  }
}

Затем мы просто использовали foldLeft для обработки данных с начальным состоянием:

val data = "[hello:=[notting],[hill]][3.4(4.56676|5.67787)][the[hill[is[high]]not]]"
val parsed = data.foldLeft(Parsed(Vector(), "", 0))(nextChar) 
parsed.blocks foreach println

Что возвращает:

[hello:=[notting],[hill]]
[3.4(4.56676|5.67787)]
[the[hill[is[high]]not]]

Ответ 4

У вас есть уродливое императивное решение, так почему бы не сделать красивый?:)

Это императивный перевод решения huynhjl, но просто сообщение, чтобы показать, что иногда императив является кратким и, возможно, проще следовать.

  def parse(s: String) = {
    var res = Vector[String]()
    var depth = 0
    var block = ""
    for (c <- s) {
      block += c
      c match {
        case '[' => depth += 1
        case ']' => depth -= 1
                    if (depth == 0) {
                      res :+= block
                      block = ""
                    }
        case _   =>
      }
    }
    res
  }

Ответ 5

Попробуйте следующее:

val s = "[hello:=[notting],[hill]][3.4(4.56676|5.67787)][the[hill[is[high]]not]]"
s.split("]\\[").toList

возвращает:

List[String](
  [hello:=[notting],[hill],
  3.4(4.56676|5.67787),
  the[hill[is[high]]not]]
)