删除表达式树中第一个元素周围和Python中每个子表达式树中的括号

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)

这可以看作是一个有限状态机(有三个状态),你可以在每个级别实例化一次,其中每个(符号创建一个新的级别.或者,它是一个确定性的 pushdown automaton,有两个平凡的状态(一个进行中的状态和一个完成)状态,我们都没有显式建模)和三个堆栈符号,每个符号表示当前级别的机器状态：

>之前 – 我们进入一个级别后立即进入的状态.遇到任何字符,除了)转换到其他状态.
>内部 – 我们所处的状态,而在括号内需要删除.通过装饰来进入(在之前.
>完成 – 处理当前级别时我们所处的状态.这意味着我们已经删除了一组括号或者我们不需要,因为第一个元素没有包含在它们中.

此外,遇到a(将新符号推入堆栈,模型进入新级别,以及a)从中弹出一个符号,这些模型从一个级别离开.除非发生Before→Inside和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'