Paréntesis coincidentes en Scala --- enfoque funcional

Question

Digamos que quiero analizar una cadena con varios corchetes de apertura y cierre (utilicé paréntesis en el título porque creo que es más común - la pregunta es la misma sin embargo) entonces que obtengo todos los niveles superiores separados en una lista.

dado:

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

Quiero:

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

La forma en que estoy haciendo esto es contando la apertura y cierre de corchetes y añadiendo a la lista cada vez que tengo a mi contador a 0. Sin embargo, tengo un código de imperativo feo. Puede suponer que la secuencia original está bien formada.

Mi pregunta es: ¿cuál sería un buen enfoque funcional para este problema?

Notas: He pensado en usar la construcción for ... yield pero dado el uso de los contadores no puedo obtener un condicional simple (debo tener condicionales solo para actualizar los contadores también) y no sé cómo Podría usar esta construcción en este caso.

Answer 1

solución rápida biblioteca utilizando Scala analizador combinador:

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

Comprobación en 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

Prueba esto:

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

devuelve:

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

Answer 3

¿Qué pasa:

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

Dadas sus necesidades contando el paréntesis parece perfectamente bien. ¿Cómo lo harías de una manera funcional? Puede hacer que el estado pase explícitamente.

Así que primero definimos nuestro estado que se acumula en los resultados blocks o concatena la siguiente block y realiza un seguimiento de la profundidad:

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

Entonces escribimos una pura función que procesa que devuelve el siguiente estado. Afortunadamente, podemos mirar cuidadosamente esta función y asegurarnos de que sea correcta.

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

Entonces sólo utilizó un foldLeft para procesar los datos con un estado inicial:

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 

que devuelve:

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

Answer 5

dispondrá de una solución imprescindible feo, así que por qué no hacer uno guapo? :)

Esta es una traducción obligada de la solución de huynhjl, pero simplemente publicando para mostrar que en ocasiones imperativo es conciso y quizás más fácil de seguir.

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 
    }