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>I would be providing a general idea as to how to go about solving the problem and then you can implement it in any language easily( <em>especially python</em> ).</p>

<p>Just traverse the given string (<em>say</em> <code>str</code> ).</p>

<p>Keep a stack <code>leftstk</code> of integers and whenever you encounter a <code>(</code>, just push the index to the <code>leftstk</code>.</p>

<p>Keep track of the number of <code>(</code> found say <code>leftbrackets</code> and <code>)</code> found say <code>righttbrackets</code> </p>

<p>Whenever a <code>)</code> is found , you remove the corresponding <code>(</code> if and only if <code>leftbrackets &gt;= righttbrackets</code>, and the equality holds only for the first time only when the condition get true using equality, meaning the condition <code>leftbrackets == righttbrackets</code> must not be used after first time it is evaluated to be true , and then the condition <code>leftbrackets &gt; righttbrackets</code> must be used.</p>

<p>For example if in <code>((12)3)4(((5)67)8)</code> we use the equality condition second time, then we end up removing brackets from <code>5678</code> also, which is not required.</p>

<p>You can easily find the position of corresponding <code>(</code>, by using the stack <code>leftstk</code>.</p>

python algorithm tree expression