目标是实现简化操作：删除表达式树及其每个子表达式树中第一个元素周围的括号，其中表达式作为括在各个括号中的字符串输入给出。这必须适用于任意数量的括号，例如：
(12)3((45)6) -> 123(456)，删除 12 周围的括号，然后删除 45 周围的括号
((12)3)4(((5)67)8) -> 1234(5678)，删除 12 周围的括号，然后是 123，然后是 5，然后是 567。不要删除 5678 周围的括号，因为这是第二个元素。
我该怎么做呢？
编辑：到目前为止我所拥有的是这样的：
def simplify(expression):
"""
call itself recursively until no consecutive parentheses exist
"""
result = []
consec_parens = 0
inside_nested = False
for char in expression:
if char == ')' and inside_nested:
inside_nested = False
consec_parens = 0
continue
if char == '(':
consec_parens += 1
else:
consec_parens = 0
if consec_parens == 2:
inside_nested = True
else:
result.append(char)
result = ''.join(result)
if result == expression:
return result
return simplify(result)
它适用于嵌套括号数量至少为两个的所有情况，但不适用于头部，即对于 (AB)C，它不会删除 AB 周围的括号。但是，对于 ((AB)C)，它会删除 AB 周围的括号，从而得到 (ABC)。
这可以被视为一个有限状态机（具有三个状态），您可以在每个级别实例化一次，其中每个(符号创造了一个新的水平。或者，它是一个确定性的下推自动机 https://en.wikipedia.org/wiki/Pushdown_automaton有两个简单的状态（一个正在进行的状态和一个完成的状态，我们都没有显式地建模）和三个堆栈符号，每个符号代表当前级别的机器状态：
-
Before- 进入关卡后我们立即所处的状态。遇到除
)转换到其他某种状态。
-
Inside- 我们所处的状态 while 位于需要删除的括号内。遇到一个进入
(而在Before.
-
Done- 当前关卡处理完毕后我们所处的状态。这意味着我们要么已经删除了一组括号，要么不需要删除，因为第一个元素没有包含在其中。
另外，遇到一个(将一个新符号推入堆栈，该符号模拟进入新级别，以及)从中弹出一个符号，该符号模拟从某一关卡离开的情况。所有输入字符都会附加到结果中except当。。。的时候Before → Inside and Inside → Done发生转变。
下面的代码是将上面的代码简单翻译成Python：
from enum import Enum
class State(Enum):
Before = 0
Inside = 1
Done = 2
def simplify(expression):
levels = [State.Before]
result = []
for c in expression:
if c == '(':
if levels[-1] == State.Before:
levels[-1] = State.Inside
else:
result.append(c)
levels.append(State.Before)
elif c == ')':
levels.pop()
if levels[-1] == State.Inside:
levels[-1] = State.Done
else:
result.append(c)
else:
if levels[-1] == State.Before:
levels[-1] = State.Done
result.append(c)
return ''.join(result)
测试以上内容，我们得到：
>>> simplify('(12)3((45)6)')
'123(456)'
>>> simplify('((12)3)4(((5)67)8)')
'1234(5678)'
>>> simplify('(AB)C')
'ABC'
>>> simplify('((AB)C)')
'ABC'
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
