Tạo cấu trúc dữ liệu đệ quy sử dụng bộ phối hợp phân tích cú pháp trong scala

Question

Tôi là người mới bắt đầu ở scala, đang làm việc theo số S99 để tìm hiểu scala. Một trong những vấn đề liên quan đến việc chuyển đổi từ một chuỗi thành một cấu trúc dữ liệu cây. Tôi có thể làm điều đó "bằng tay", bởi tôi cũng muốn xem làm thế nào để làm điều đó bằng cách sử dụng thư viện comber phân tích cú pháp của Scala.

Cấu trúc dữ liệu cho cây là

sealed abstract class Tree[+T] 
case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] { 
    override def toString = "T(" + value.toString + " " + left.toString + " " + right.toString + ")" 
} 
case object End extends Tree[Nothing] { 
    override def toString = "." 
} 
object Node { 
    def apply[T](value: T): Node[T] = Node(value, End, End) 
}  

Và đầu vào được coi là một chuỗi, như thế này: a(b(d,e),c(,f(g,)))

tôi có thể phân tích các chuỗi sử dụng một cái gì đó giống như

trait Tree extends JavaTokenParsers{ 
    def leaf: Parser[Any] = ident 
    def child: Parser[Any] = node | leaf | "" 
    def node: Parser[Any] = ident~"("~child~","~child~")" | leaf 
} 

Nhưng làm thế nào tôi có thể sử dụng thư viện phân tích cú pháp để xây dựng cây? Tôi biết rằng tôi có thể sử dụng ^^ để chuyển đổi, ví dụ, một số chuỗi thành một số nguyên. Nhầm lẫn của tôi đến từ cần thiết để 'biết' trái và phải subtrees khi tạo ra một thể hiện của Node. Làm thế nào tôi có thể làm điều đó, hoặc là một dấu hiệu mà tôi muốn làm một cái gì đó khác nhau?

Tôi có nên chọn thứ mà trình phân tích cú pháp trả về ((((((a~()~(((((b~()~d)~,)~e)~)))~,)~(((((c~()~)~,)~(((((f~()~g)~,)~)~)))~)))~)) để nhập ví dụ ở trên) và xây dựng cây dựa trên điều đó thay vì sử dụng toán tử phân tích cú pháp như ^^ hoặc ^^^ để xây dựng cây trực tiếp?

Answer 1

Có thể thực hiện điều này sạch với ^^, và bạn đang khá chặt chẽ:

object TreeParser extends JavaTokenParsers{ 
    def leaf: Parser[Node[String]] = ident ^^ (Node(_)) 
    def child: Parser[Tree[String]] = node | leaf | "" ^^ (_ => End) 
    def node: Parser[Tree[String]] = 
    ident ~ ("(" ~> child) ~ ("," ~> child <~ ")") ^^ { 
     case v ~ l ~ r => Node(v, l, r) 
    } | leaf 
} 

Và bây giờ:

scala> TreeParser.parseAll(TreeParser.node, "a(b(d,e),c(,f(g,)))").get 
res0: Tree[String] = T(a T(b T(d . .) T(e . .)) T(c . T(f T(g . .) .))) 

Theo tôi cách dễ nhất để tiếp cận các loại vấn đề là nhập các phương thức phân tích cú pháp với các kết quả bạn muốn, và sau đó thêm các hoạt động ánh xạ thích hợp với ^^ cho đến khi trình biên dịch hài lòng.