Remove Redundant Parenthesis in an Arithmetic Expression-CodePudding

I'm trying to remove redundant parentheses from an arithmetic expression. For example, if I have the expression (5 ((2*3))), I want the redundant parenthesis between (2*3) removed. The output that I want is (5 (2*3)).

I'm getting this arithmetic expression from performing an inorder traversal on an expression tree. The final string that I get after performing the traversal is ((5) (((2)*(3)))). I used re.sub('\((\d )\)', r'\1', <traversal output string>) to remove the parenthesis between the numbers like (5) to 5. But I'm still confused on how I should approach to remove parenthesis among sub expressions (((2*3)) in this case).

Here is what my inorder traversal function looks like

    def inorder(tree):
        # return string of inorder traversal of tree with parenthesis
        s = ''
        if tree != None:
            s  = '('
            s  = ExpTree.inorder(tree.getLeftChild())
            s  = str(tree.getRootVal())
            s  = ExpTree.inorder(tree.getRightChild())
            s  = ')'

        return re.sub('\((\d )\)', r'\1', s)

Any guidance on how I should approach to solve this problem would be appreciated!

CodePudding user response：

Instead of adding the parenthesis around the parent/root expression, one option is to add the parentheses before and after recursing down on each of the left and right children. If those children are leaves, meaning they do not have children, do not add parentheses.

In practice, this might look something like this:

def inorder(tree):
    # return string of inorder traversal of tree with parenthesis
    s = ''
    # Add left subtree, with parentheses if it is not a leaf
    left = tree.getLeftChild()
    if left is not None:
        if left.isLeaf():
            s  = ExpTree.inorder(left)
        else:
            s  = '('   ExpTree.inorder(left)   ')'

    # Add root value
    s  = str(tree.getRootVal())

    # Add right subtree, with parentheses if it is not a leaf
    right = tree.getRightChild()
    if right is not None:
        if right.isLeaf():
            s  = ExpTree.inorder(right)
            else:
                s  = '('   ExpTree.inorder(right)   ')'
    return s

This means that a tree with a single node, 5, will become just "5", and the following tree

will become "5 (2*3)".