式ツリー内の最初の要素とその各部分式ツリー内の括弧を削除する

Question

目的は簡単化操作を実装することです。式ツリー内の最初の要素のまわりの括弧を削除します。その式はさまざまなカッコで囲まれた文字列入力として与えられます。これは、例えば、括弧の任意の数のために働くようにしなければならない：

（12）3（（45）6） - > 123（456）、（45

周り次いで12周りに括弧を除去（12 ）3）4（（（5）67）8） - > 1234（5678）の場合は、12、123、5、567の括弧を削除します。

どうすればよいですか？

EDIT：

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）になります。

Answer 1

これは、レベルごとに1回インスタンス化する有限状態マシン（3つの状態）とみなすことができます。ここでは、それぞれ(シンボルが新しいレベルを作成します。あるいは、2つの簡単な状態（進行中の状態と完了状態、どちらも明示的にモデル化していない）と現在のレベルのマシンの状態を表す3つのスタック記号を持つ確定的なpushdown automatonです。

• より前 - レベルに入る直後の状態。 )以外の文字に出会うと、他の状態に移行します。
• 内側 - 削除する必要のあるカッコ内の状態です。入り口は(で、の前にはの前に入ります。
• 完了 - 現在のレベルが処理された状態です。これは、最初の要素がそれらに囲まれていないので、すでに括弧のセットを削除したか、または不要にしたことを意味します。

さらに、(に遭遇すると、モデルは新しいレベルを入力スタックに新しいシンボルを押し、そして)はモデルレベルから出るそれから1つのシンボルを、ポップ。 →インサイドインサイド→前と完了遷移が発生したときにすべての入力文字が除い結果に付加ます。

次のコードは、簡単な上記の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'