Nawiasy pasujące w Scali --- podejście funkcjonalne

Question

Załóżmy, że chcę przetworzyć ciąg z różnymi nawiasami otwierającymi i zamykającymi (użyłem nawiasów w tytule, ponieważ uważam, że jest on bardziej powszechny - pytanie jest jednak takie samo), więc że rozdzielam wszystkie wyższe poziomy na liście.

Dane:

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

chcę:

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

Droga Robię to poprzez liczenie otwieranie i zamykanie nawiasów i dodanie do listy, gdy dostanę licznik na 0. Mam jednak brzydki imperatywny kod. Możesz założyć, że oryginalny ciąg jest dobrze uformowany.

Moje pytanie brzmi: jakie byłoby miłe funkcjonalne podejście do tego problemu?

Uwagi: Zastanawiam się, czy użyć metody for ... yield, ale biorąc pod uwagę użycie liczników, nie mogę uzyskać prostego warunku (muszę mieć także warunki do aktualizacji liczników) i nie wiem jak Mógłbym użyć tej konstrukcji w tym przypadku.

Answer 1

Szybkie rozwiązanie używając Scala parsera combinator biblioteki:

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

sprawdzenie go w 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]]) 

Answer 2

Spróbuj tego:

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

Powroty:

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

Answer 3

Co o:

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

wyraziłeś wymagania licząc nawias wydaje się perfekcyjnie. Jak zrobiłbyś to w sposób funkcjonalny? Możesz sprawić, że stan jawnie minął.

Więc najpierw definiujemy nasze państwo, które gromadzi wyniki w blocks lub skleja następny block i śledzi głębokość:

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

Następnie piszemy czystą funkcję przetwarzane że zwraca następny stan. Mamy nadzieję, że możemy dokładnie obejrzeć tę jedną funkcję i upewnić się, że jest poprawna.

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

Wtedy właśnie użył foldLeft przetwarzać dane o stanie początkowym:

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 

która zwraca:

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

Answer 5

Masz brzydkie rozwiązanie imperatyw, więc dlaczego nie zrobić ładnie wyglądający? :)

To imperatywne tłumaczenie rozwiązania huynhjl, ale po prostu post, aby pokazać, że czasami imperatyw jest zwięzły i być może łatwiejszy do naśladowania.

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 
    }