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

Question

比如有一个字符串s：

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

我们知道 s 的开头是“(”，我们想找到它的反义词，“blabla”之前的“)”，如何在 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'>, {})

算法是：

• 保留一个包含开括号位置的opens dict。
• 当您找到一个左括号时，您在所有先前的条目上添加 +1，然后为当前位置添加一个新条目
• 当你找到一个右括号时，你在前面的所有输入上都减少了 -1
• 只需运行开盘价，如果任何条目为 0，则意味着我们有一对。