Groovy的 - 分割字符串與多個括號匹配

Question

我有以下字符串：

「（1：&（（2：乙| 3：C）&（4：d | 5：E）））| （6：F & 7：G）'

我想將它們解析爲樹形層次結構對象。 1：A，2：B，3：C應該在葉子中，並且&或|在根。 括號是很重要的，所以從例如字符串應被轉換成：

  | 
     / \ 
     / \ 
     &  & 
    /\ /\ 
    / \ / \ 
    1:A & 6:F 7:G 
     /\ 
     / \ 
    / \  
     |  | 
    /\ /\ 
    2:B 3:C 4:D 5:E 

我試圖使用已拆支架圖案，但我無法轉換結果在一個合理的層次結構。 我用完了想法，也許你們中的一些人會有一些？

Answer 1

另一種解決方案使用正則表達式。

這個想法是遞歸地解析匹配葉子節點和表達式的輸入字符串。 parse方法的每個調用都將匹配它的整個輸入，並返回一個帶有輸入值的節點（如果它是一個葉）或帶有兩個遞歸評估的子節點的節點（如果它匹配「表達式運算符表達式「）。

在其目前的形式，它需要高度規則輸入：

• 葉必須在形式位：upperCaseCharacter沒有括號操作者和表達式之間
• 一個空間
• 一個表達式可以是一個葉或東西括在內

每當正則表達式匹配，所有匹配的組被收集和空值被刪除。將會有8個非空組（因爲分組括號的數量總是相同的），並且內部組將總是數字2,3和5，其中3是運算符，2和5是左邊的輸入並且右節點。

toString該方法簡單地寫出在波蘭表示法（運EX1 EX2）的表達。

class Node { 
    String value 
    Node left, right 

    static leaf = /(\d:[A-Z])/ 
    static op = /([&|])/ 
    static par = /\((.+)\)/ 

    static parse(String text) { 
     if (text ==~ "^$leaf\$") { 
      return new Node(value: text) 
     } 
     def matcher = text =~ "^($leaf|$par) $op ($leaf|$par)\$" 
     if (matcher.matches()) { 
      def (l,o,r) = (matcher[0] - null)[2,3,5] 
      return new Node(left: parse(l), value: o, right: parse(r)) 
     } 
     throw new IllegalArgumentException("Irregular input: $text") 
    } 

    String toString() { 
     left && right ? "$value $left $right" : value 
    } 
} 

例子：

println Node.parse('1:A') 
println Node.parse('1:A & 2:B') 
println Node.parse('(1:A & 2:B) | 3:C') 
println Node.parse('(1:A & ((2:B | 3:C) & (4:D | 5:E))) | (6:F & 7:G)') 

產生如下的波蘭式的輸出：

1:A 
& 1:A 2:B 
| & 1:A 2:B 3:C 
| & 1:A & | 2:B 3:C | 4:D 5:E & 6:F 7:G 

Answer 2

Reverse Polish Notation

Relevant question on StackOverflow

Answer 3

我覺得這確實是（至少對於你的榜樣輸入）。

首先，我將所有X:Y實例替換爲Leaf實例，將Leaf存儲在緩存列表中，並將X:Y替換爲緩存中Leaf的索引。

然後，我反覆查找(L O R)模式，爲它創建一個Node實例（在緩存中查找L和R），將其添加到緩存中，並將其替換爲字符串中的緩存索引。

然後你剩下一個字符串11 | 9（或類似的），它可以像以前一樣轉換成節點。

希望能夠解釋它。可能是使用合適解析器生成，如果這是什麼嚴重情況，或將需要在未來延伸的更明智的解決辦法...

import groovy.transform.* 

def input = '(1:A & ((2:B | 3:C) & (4:D | 5:E))) | (6:F & 7:G)' 

def cache = [] 

// Remove all X:Y items into a lookup table 
input = input.replaceAll(/\w+:\w+/) { 
    cache << new Leaf(it) 
    cache.size() - 1 
} 

// Then keep finding Nodes filling them with cached values and adding them into the cache 
while(input ==~ /.*\(\d+ [&|] \d+\).*/) { 
    input = input.replaceAll(/\(\d+ [&|] \d+\)/) { 
     def (left,op,right) = it[ 1..-2 ].tokenize() 
     cache << new Node(cache[ left.toInteger() ], op, cache[ right.toInteger() ]) 
     cache.size() - 1 
    } 
} 

// Then we're left with "11 | 9", so make the root node 
def (left,op,right) = input.tokenize() 
def tree = new Node(cache[ left.toInteger() ], op, cache[ right.toInteger() ]) 

println tree 

/////////////////////////////////////////////////////// 
// Classes to hold leafs and nodes 

@Canonical 
class Leaf { 
    String value 
    String toString(String prefix) { 
     "${prefix}${value}" 
    } 
} 

@TupleConstructor 
class Node { 
    def left, op, right 
    String toString(String prefix) { 
     """${prefix}left: 
      |${prefix}${left.toString(prefix + ' ')} 
      |${prefix}op: $op 
      |${prefix}right: 
      |${prefix}${right.toString(prefix + ' ')}""".stripMargin() 
    } 
    String toString() { 
     toString('') 
    } 
}