Python的正則表達式，用於解析在給定的BNF定義如下格式

我有表示在以下BNF定義狀格式的樹AA txt文件的樹結構：Python的正則表達式，用於解析在給定的BNF定義如下格式

branches : '(' <value1> <value2> <n_children> <branches> ')' 
     | ''

對於樹中的每個節點具有兩個值作爲整數的value1和value2，是整數的子代的數量和分支。文件的一個子集的一個例子是這樣的：

(1796161 2205411 3 
    (1796288 2205425 0 ) 
    (1811141 2205419 1 
     (1811652 2205480 1 
      (1812161 2205496 4 
       (1812288 2205521 1 
        (1812415 2205526 0 )) 
       (1812034 2205516 0 ) 
       (1827651 2205510 2 
        (1827906 2205581 2 
         (1843777 2205588 2 
          (1844032 2205626 1 
           (1844159 2205632 0 )) 
          (1843138 2205617 0 )) 
         (1828288 2205591 1 
          (1828161 2205597 0 ))) 
        (1827012 2205563 0 )) 
       (1811907 2205511 0 )))) 
    (1796034 2205420 0 ))

有沒有一種很好的方式使用正則表達式（S）來分析這些數據，將不涉及我的性格手動讀取文件字符跟蹤的所有的禁忌和保留的關係（親子）排序。

來源

2016-12-28 Siddharth Shukla

括號並不真正的問題在這裏，不是嗎？該格式在沒有縮進或圓括號的情況下同樣有效，因爲它會告訴您當前節點有多少個子節點。所以，當你閱讀每一行時，你就知道該節點有多少個孩子要閱讀。一旦你完成，你回到父節點，並繼續閱讀* that *節點，等等等等。 –

@RushyPanchal括號用於標記節點的結尾。你說得對，孩子的數量已經給出，你知道有多少孩子可以解析，但我仍然需要跟蹤已打開和已關閉的括號，以跟蹤我在樹中的位置。 –

如果您使用堆棧來跟蹤樹中的位置，則不需要跟蹤括號。每次你下到樹上（即兒童數> 0），將當前節點推入堆棧。當你讀完孩子後，彈出父母並繼續閱讀孩子。它需要更多的簿記而不僅僅是一個堆棧（你需要記錄每個級別有多少個孩子可以閱讀），但它並不要求你知道括號是如何嵌套的。 –

這是一個最簡單的解析器，可以讓你編寫自己的語法，如pyPEG。下面創建Node對象，其中每個Node可以有零個或更多孩子的樹：

import re 

from pypeg2 import attr, ignore, List, maybe_some, parse 

Int = re.compile(r'[0-9]+') # a positive integer 

class Values(List): 
    '''A pair of values associated with each node in the tree. 

    For example, in the node 

     (1 2 0) 

    the values are 1 and 2 (and 0 is the number of children). 
    ''' 

    grammar = 2, Int 

class Node(List): 
    '''A node in the tree. 

    Attributes: 
     values  The pair of values associated with this node 
     children A list of child nodes 
    ''' 

    def __repr__(self): 
     return 'Values: ' + ', '.join(self.values) 

# Grammar for Node is recursive (a Node can contain other Nodes), 
# so we have to set it outside of the Node class definition. 
Node.grammar = (
    '(', 
    attr('values', Values), 
    ignore(Int), 
    attr('children', maybe_some(Node)), 
    ')' 
) 

def print_tree(root, indent=0): 
    '''Print a tree of Nodes recursively''' 

    print(' ' * indent, end='') 
    print(root) 

    if len(root.children) > 0: 
     for child in root.children: 
      print_tree(child, indent + 2) 


if __name__ == '__main__': 

    tree = ''' 
     (1796161 2205411 3 
      (1796288 2205425 0 ) 
      (1811141 2205419 1 
       (1811652 2205480 1 
        (1812161 2205496 4 
         (1812288 2205521 1 
          (1812415 2205526 0 )) 
         (1812034 2205516 0 ) 
         (1827651 2205510 2 
          (1827906 2205581 2 
           (1843777 2205588 2 
            (1844032 2205626 1 
             (1844159 2205632 0 )) 
            (1843138 2205617 0 )) 
           (1828288 2205591 1 
            (1828161 2205597 0 ))) 
          (1827012 2205563 0 )) 
         (1811907 2205511 0 )))) 
      (1796034 2205420 0 )) 
    ''' 

    root = parse(tree, Node) 
    print_tree(root)

輸出：

Values: 1796161, 2205411 
    Values: 1796288, 2205425 
    Values: 1811141, 2205419 
    Values: 1811652, 2205480 
     Values: 1812161, 2205496 
     Values: 1812288, 2205521 
      Values: 1812415, 2205526 
     Values: 1812034, 2205516 
     Values: 1827651, 2205510 
      Values: 1827906, 2205581 
      Values: 1843777, 2205588 
       Values: 1844032, 2205626 
       Values: 1844159, 2205632 
       Values: 1843138, 2205617 
      Values: 1828288, 2205591 
       Values: 1828161, 2205597 
      Values: 1827012, 2205563 
     Values: 1811907, 2205511 
    Values: 1796034, 2205420

來源

2016-12-28 19:16:46 ThisSuitIsBlackNot

Python的正則表達式，用於解析在給定的BNF定義如下格式

回答

相關問題