Dấu ngoặc đơn phù hợp trong Scala --- phương pháp tiếp cận chức năng

Question

Giả sử tôi muốn phân tích một chuỗi với các dấu ngoặc mở và đóng khác nhau (tôi đã sử dụng dấu ngoặc đơn trong tiêu đề vì tôi tin nó là phổ biến hơn - câu hỏi vẫn giống nhau) tôi nhận được tất cả các cấp cao hơn được phân tách trong một danh sách.

Given:

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

Tôi muốn:

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

Con đường tôi đang làm điều này là bằng cách đếm khai mạc và bế ngoặc và thêm vào danh sách bất cứ khi nào tôi nhận được truy cập của tôi đến 0. Tuy nhiên, tôi có một mã bắt buộc xấu xí. Bạn có thể giả định rằng chuỗi gốc được tạo thành tốt.

Câu hỏi của tôi là: phương pháp tiếp cận chức năng tốt đẹp cho vấn đề này là gì?

Lưu ý: Tôi đã nghĩ đến việc sử dụng cấu trúc năng suất nhưng tôi không thể có được điều kiện đơn giản (tôi cũng phải có điều kiện để cập nhật bộ đếm) và tôi không biết cách Tôi có thể sử dụng cấu trúc này trong trường hợp này.

Answer 1

giải pháp nhanh bằng Scala phân tích cú pháp combinator thư viện:

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

Kiểm tra nó trong 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

Hãy thử điều này:

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

lợi nhuận:

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

Answer 3

gì về:

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

Với yêu cầu của bạn đếm ngoặc dường như hoàn toàn tốt đẹp. Làm thế nào bạn sẽ làm điều đó một cách chức năng? Bạn có thể làm cho nhà nước được thông qua một cách rõ ràng.

Vì vậy, đầu tiên chúng tôi xác định tình trạng của chúng tôi mà tích lũy kết quả trong blocks hoặc móc nối tiếp theo block và theo dõi độ sâu:

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

Sau đó chúng ta viết một hàm thuần túy mà xử lý trả về trạng thái tiếp theo. Hy vọng rằng, chúng ta chỉ có thể xem xét cẩn thận chức năng này và đảm bảo nó đúng.

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

Sau đó, chúng ta chỉ cần sử dụng một foldLeft để xử lý dữ liệu với một trạng thái ban đầu:

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 

nào trả về:

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

Answer 5

Bạn có một giải pháp cấp bách xấu xí, vậy tại sao không làm cho một cái đẹp trai? :)

Đây là bản dịch bắt buộc của giải pháp của huynhjl, nhưng chỉ đăng tải để cho thấy rằng đôi khi bắt buộc là ngắn gọn và có thể dễ dàng hơn để theo dõi.

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 
    }