python - Python文字列で反対の文字を見つける方法は?

Question

文字列 s があるように:

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

s の始まりは "(" であり、"blabla" の前の ")" の反対を見つけたいのですが、Python でこれを行うにはどうすればよいですか?

ステータスマシンを使わずに、シンプルで直感的な方法でこれを行うことは可能ですか? またはこれを行うことができるライブラリはありますか？

Answer 1

正規表現、パイパーシングを試すことができますが、線形時間の複雑さを持つ単純なオプションは次の単純な方法です

>>> 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'>, {})

アルゴリズムは次のとおりです。

• 開き角かっこの位置を含むopensdictを保持します。
• 開いた角かっこを見つけたら、前のすべてのエントリに+1を追加してから、現在の位置に新しいエントリを追加します
• 閉じ括弧を見つけると、以前のすべての入力で-1が減少します
• オープンを実行するだけで、エントリが0の場合は、ペアがあることを意味します。