Remove the parentheses around the very first element in an expression tree and in each of its sub-expression trees in Python
<p>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:</p>

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

<p>((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.</p>

<p>How do I do this?</p>

<p>EDIT: So far what I have is this:</p>

<pre><code>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)
</code></pre>

<p>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).</p>

<p>This can be viewed as a finite state machine (with three states) which you instantiate once per level, where each <code>(</code> symbol creates a new level. Alternatively, it is a deterministic <a href="https://en.wikipedia.org/wiki/Pushdown_automaton" rel="nofollow">pushdown automaton</a> 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:</p>

<ul>
<li><strong>Before</strong> - The state we are in immediately after entering a level. Encountering any characters except <code>)</code> transitions to some other state.</li>
<li><strong>Inside</strong> - The state we are in while inside parentheses that need to be removed. Entered by encoutering a <code>(</code> while in <strong>Before</strong>.</li>
<li><strong>Done</strong> - 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.</li>
</ul>

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

<p>The following code is a simple translation of the above into Python:</p>

<pre><code>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)
</code></pre>

<p>Testing the above out, we get:</p>

<pre><code>&gt;&gt;&gt; simplify('(12)3((45)6)')
'123(456)'
 &gt;&gt;&gt; simplify('((12)3)4(((5)67)8)')
'1234(5678)'
&gt;&gt;&gt; simplify('(AB)C')
'ABC'
&gt;&gt;&gt; simplify('((AB)C)')
'ABC'
</code></pre>

python algorithm tree expression