删除表达式树及其每个子表达式树中第一个元素周围的括号 [英] Remove the parentheses around the very first element in an expression tree and in each of its sub-expression trees in Python

问题描述

目标是实现一个简化操作：删除表达式树及其每个子表达式树中第一个元素周围的圆括号，其中表达式以字符串输入的形式被包含在各个括号中。这必须适用于任意数量的括号，例如：

The goal is to implement a simplification operation: remove the parentheses around the very first element in an expression tree and in each of its sub-expression trees, where the expression is given as a string input enclosed in various parentheses. This must work for an arbitrary number of parentheses, so for example:

（12）3（（45）6） - > 123（456），删除周围的括号12然后约45

(12)3((45)6) -> 123(456), remove the parentheses around 12 then around 45

（（12）3）4（（（5）67）8） - > 1234（5678），删除12周围的括号，然后删除123 ，然后5，然后567.不要删除5678周围的括号，因为那是第二个元素。

((12)3)4(((5)67)8) -> 1234(5678), remove the parentheses around 12, then 123, then 5, then 567. Do not remove the parentheses around 5678 since that is the second element.

我该怎么做？

编辑：到目前为止我是这样的：

So far what I have is this:

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)

它适用于所有情况其中嵌套括号的数量至少为2，但是它不适用于头部，即对于（AB）C，它不会删除AB周围的括号。然而，对于（（AB）C），它删除AB周围的括号，导致（ABC）。

It works for all cases where the number of nested parentheses is at least two, but it doesn't work for the head, i.e. for (AB)C, it does not remove the parentheses around AB. However, for ((AB)C) it removes the parentheses around AB resulting in (ABC).

推荐答案

作为一个有限状态机（具有三个状态），每个级别实例化一次，其中每个（）创建一个新的级别，或者，它是一个确定性的下推自动机具有两个微不足道的状态（正在进行状态和完成状态，我们都不明确模拟）和三个堆栈符号，每个代表当前级别的机器状态：

This can be viewed as a finite state machine (with three states) which you instantiate once per level, where each ( symbol creates a new level. Alternatively, it is a deterministic pushdown automaton with two trivial states (an in-progress state and a done state, neither of which we model explicitly) and three stack symbols, each representing the state of the machine for the current level:

• 之前 - 我们是在之外的任何字符）转换到某个其他状态。


• Inside - 我们在括号内需要删除的状态。 在 之前遇到（）。


• 完成我们处于当前级别的状态，这意味着我们已经删除了一组括号，或者我们不需要，因为第一个元素没有被包含在其中。

• Before - The state we are in immediately after entering a level. Encountering any characters except ) transitions to some other state.
• Inside - The state we are in while inside parentheses that need to be removed. Entered by encoutering a ( while in Before.
• Done - The state we are in when the current level has been processed. This means that either we already removed a set of parentheses or we did not need to, since the first element wasn't enclosed in them.

此外，遇到一个（将一个新符号推入堆栈，哪个模型进入一个新的级别， code>）从其中弹出一个符号，哪个模型从一个级别离开，当 Before 之前，所有输入字符都会追加到结果 / strong>→ Inside 和 Inside →完成转换。

Additionally, encountering a ( pushes a new symbol onto the stack, which models entering a new level, and a ) pops the one symbol from it, which models leaving from a level. All input characters get appended onto the result except when the Before → Inside and Inside → Done transitions occur.

以下代码是将上述简单的翻译成Python：

The following code is a simple translation of the above into 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'

这篇关于删除表达式树及其每个子表达式树中第一个元素周围的括号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！