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

Question

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

Дано:

[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, но при использовании счетчиков я не могу получить простой условный (у меня должны быть условные обозначения только для обновления счетчиков), и я не знаю, как Я мог бы использовать эту конструкцию в этом случае.

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

Проверка его в РЕПЛ:

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

Answer 2

Попробуйте это:

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

Answer 3

Что о:

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] 

Answer 4

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

Итак, сначала мы определяем наше состояние, которое аккумулирует результаты в 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]] 

Answer 5

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

Это императивный перевод решения 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 
    }