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

Question

比如有一个字符串 s：

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

我们知道s的开头是"("，我们想要找到它的对立面，在"blabla"之前的")"，在Python中应该如何做？

有没有可能以一种简单直观的方式做到这一点，而不使用状态机？或者有没有任何库可以实现这个功能？

- zchenah

---

这可能会有所帮助：https://dev59.com/rXRB5IYBdhLWcg3wv5tA#524624 - Amit

不好意思，我害怕你无法通过这种问题来避免正则表达式。 - EnricoGiampieri

@AmitMizrahi 非常感谢，这是一个好方法。所以问题应该改为是否有库可以做这种事情... - zchenah

我从未使用过它，但你可能可以用 pyparsing 做类似这样的事情。 - mgilson

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))())'
>>> 

- Abhijit

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字典。
• 当你找到一个开括号时，在所有先前的条目上加上+1，然后在当前位置添加一个新条目。
• 当你找到一个闭括号时，在所有先前的条目上减去-1。
• 只需运行opens，如果任何条目为0，则表示我们有一对。

- andrefsp