擅长:python、mysql、java
<p>使用堆栈在嵌套括号的每个级别累积子表达式是一种常见的方法。在每个级别存储左括号的位置和累积表达式字符串。遇到左括号时添加标高。当遇到右括号时,弹出当前级别并将其添加到结果中。此时,替换标记将添加到上一级别的表达式(成为当前级别)</p>
<pre><code>def parGroups(S):
result = dict()
stack = [[0,""]]*2 # parenthesis position, expression
for i,c in enumerate(S+")"): # extra ")" to force out main expression
if c=="(":
stack.append([i,""]) # stack up new group
continue
if c==")":
start,expr = stack.pop(-1) # unstack current group
c = f"[{start}${i}]" # token
result[c[1:-1]] = expr # build result
stack[-1][-1] += c # accumulate expression in current group
return result
</code></pre>
<p>输出:</p>
<pre><code>S = "(7+y+(66+7)+(32+(78*19-(32-0)))+(32-9))+8+9+(9-10)-(9/7)-10"
print(parGroups(S))
{'5$10' : '66+7',
'23$28': '32-0',
'16$29': '78*19-[23$28]',
'12$30': '32+[16$29]',
'32$37': '32-9',
'0$38' : '7+y+[5$10]+[12$30]+[32$37]',
'44$49': '9-10',
'51$55': '9/7',
'0$59' : '[0$38]+8+9+[44$49]-[51$55]-10'}
</code></pre>