<p>真正解决这个问题的最佳方法是维护堆栈。对于遇到的每一个<code>(</code>,您可以将索引值推送到堆栈中,对于每一个<code>)</code>,您需要使用插入最后一个<code>(</code>索引的数字弹出堆栈。这意味着<code>(</code>的索引和{<cd2>}的索引形成一对。在</p>
<p>这可以通过这样做来实现</p>
<pre><code>seq = '(((((((..((((.....(..)))).((((.........)))).....(((((..)....))))))))))))....'
xStack = []
for i, x in enumerate(seq):
if x == '(':
xStack.append(i)
if x == ')':
o = xStack.pop()
</code></pre>
<p>现在有了基本的步骤,除了维护括号的索引之外,还需要一些其他的东西。在pop操作之后,您需要存储匹配对,为此,我们引入另一个变量,当遇到<code>.</code>时,基本上什么都不做</p>
^{pr2}$
<p>现在我们得到了如下所示的结果对</p>
^{3}$
<p>我们需要找出所有的空闲空间在哪里,这可以很容易地通过以下操作来完成</p>
<pre><code>spacesList = [i for i in range(len(seq)) if seq.startswith('.', i)]
</code></pre>
<p>结果是</p>
<pre><code>[7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59, 72, 73, 74, 75]
</code></pre>
<p>现在可以很容易地编写一个函数,其中传递<code>spacesList</code>和{<cd8>},并获得每个可能对之间的可用空间数。有很多可能的优化,但这应该能够让你朝着正确的方向开始。在</p>
<pre><code>def getSpacesCount(spacesList, resultingPairs):
for pair in resultingPairs:
a = pair[0]
b = pair[1]
spacesCount = 0
for val in spacesList:
if a < val < b:
spacesCount+=1
print a,b,spacesCount
seq = '(((((((..((((.....(..)))).((((.........)))).....(((((..)....))))))))))))....'
xStack = []
resultingPairs = []
for i, x in enumerate(seq):
if x == '(':
xStack.append(i)
if x == ')':
o = xStack.pop()
tempPair = [o, i]
resultingPairs.append(tempPair)
if x == '.':
pass
spacesList = [i for i in range(len(seq)) if seq.startswith('.', i)]
getSpacesCount(spacesList, resultingPairs)
</code></pre>
<p>有左括号的位置值,右括号的位置值,以及它们之间的自由空间数。在</p>
<pre><code>>>> getSpacesCount(spacesList, resultingPairs)
18 21 2
12 22 7
11 23 7
10 24 7
29 39 9
28 40 9
27 41 9
26 42 9
52 55 2
51 60 6
50 61 6
49 62 6
48 63 6
9 64 28
6 65 30
5 66 30
4 67 30
3 68 30
2 69 30
1 70 30
0 71 30
</code></pre>
<p><strong>编辑</strong>
似乎不知道如何编辑stackoverflow的注释,请将函数更新为</p>
^{8}$
<p>这将给你计数和位置。你喜欢哪一个你都可以留着。在</p>
<pre><code>>>> getSpacesCount(spacesList, resultingPairs)
18 21 2 [19, 20]
12 22 7 [13, 14, 15, 16, 17, 19, 20]
11 23 7 [13, 14, 15, 16, 17, 19, 20]
10 24 7 [13, 14, 15, 16, 17, 19, 20]
29 39 9 [30, 31, 32, 33, 34, 35, 36, 37, 38]
28 40 9 [30, 31, 32, 33, 34, 35, 36, 37, 38]
27 41 9 [30, 31, 32, 33, 34, 35, 36, 37, 38]
26 42 9 [30, 31, 32, 33, 34, 35, 36, 37, 38]
52 55 2 [53, 54]
51 60 6 [53, 54, 56, 57, 58, 59]
50 61 6 [53, 54, 56, 57, 58, 59]
49 62 6 [53, 54, 56, 57, 58, 59]
48 63 6 [53, 54, 56, 57, 58, 59]
9 64 28 [13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59]
6 65 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59]
5 66 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59]
4 67 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59]
3 68 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59]
2 69 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59]
1 70 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59]
0 71 30 [7, 8, 13, 14, 15, 16, 17, 19, 20, 25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 46, 47, 53, 54, 56, 57, 58, 59]
</code></pre>