如何在python字符串中找到相反的字符？

Question

比如有一個字符串s：

s = "((abc)((123))())blabla" 

我們知道S的開頭「（」我們要找到它的對面，「）」「布拉布拉」之前，如何做到這一點在python中？

是否可以在不使用狀態機的情況下以簡單直觀的方式執行此操作？ 還是有任何圖書館可以做到這一點？

Answer 1

您可以嘗試正則表達式，pyparsing，但線性時間複雜度幼稚的選項下面簡單的方式

>>> s = "((abc)((123))())blabla" 
>>> count = 0 
>>> for i,e in enumerate(s): 
    if e == '(': 
     count += 1 
    elif e == ')': 
     count -= 1 
    if not count: 
     break 


>>> s[:i + 1] 
'((abc)((123))())' 
>>> 

Answer 2

的代碼就可以實現，通過：

from collections import defaultdict 

opens = defaultdict(int) 

open_close_pair = [] 

s = '((abc)((123))())blabla' 
openc, closec = '(', ')' 

for c in range(0, len(s)): 
    if s[c] == openc: 
     # +1 in every entry 
     for key, val in opens.items(): 
      opens[key] += 1 
     opens[c] += 1 

    elif s[c] == closec: 
     # -1 in every entery 
     for key, val in opens.items(): 
      opens[key] -= 1 
    else: 
     pass 

    for key, val in opens.items(): 
     if val == 0: 
      # open the entry to the open close pairs 
      open_close_pair.append((key, c)) 
      # the bracket is close so can be removed from the counter 
      del opens[key] 

for x in open_close_pair: 
    print " %s %s " % (s[x[0]], s[x[1]]) 
print open_close_pair 
print opens 

輸出是：

() 
() 
() 
() 
() 
[(1, 5), (7, 11), (6, 12), (13, 14), (0, 15)] 
defaultdict(<type 'int'>, {}) 

的算法是：

• 保持一個打開包含的位置字典打開括號。
• 當你找到一個開放的支架，你以前的所有條目添加+1，比當你發現一個右括號加上當前位置
• 一個新條目，您減少-1以前所有的enteries
• 只需運行打開，如果有任何條目爲0意味着我們有一對。