On python please! Construct the expression tree. Code functions "_construct" and "constructTree". Don't change other functions. Test code and its output are given at the end. Thank you very much!

### EX7_21 # Complete constructTree below. Follow the instructions in the comment # Submission # - file name = EX7_21.py, # - no change of function / class names # - upload in Vocareum until 7/25(tue)

class expressionTree: class treeNode: def __init__(self, value, lchild, rchild): self.value, self.lchild, self.rchild = value, lchild, rchild

def __init__(self): self.treeRoot = None

#utility functions for constructTree def mask(self, s): # The function empties the inside of every outermost parentheses pair # and return it as a string # # e.g. s = ( 2 + 3^2 -(2-4)) + 2 - (-1 + 1/7) # It returns ( ) + 2 - ( ) # nestLevel = 0 masked = list(s) for i in range(len(s)): if s[i]==")": nestLevel -=1 elif s[i]=="(": nestLevel += 1 if nestLevel>0 and not (s[i]=="(" and nestLevel==1): masked[i]=" " return "".join(masked)

def isNumber(self, expr): #returns True if it's convertible to float, else False if len(expr)==0 or not isinstance(expr, str): print("type mismatch error: isNumber") return "type mismatch error: isNumber" #--- function code starts ---# try: float(expr) return True

except ValueError: return False #--- function code ends ---#

def _construct(self,expr): # First strip expr # If isNumber(expr) is true, it's a leaf. # Otherwise # - do s = mask(expr) # - find an operator of the lowest precedence in s # - If there is no operator in s, # and s[0]="(", s[len(s)-1]=")" # remove the outermost parenthese and pass the rest # to _constrct recursively # - otherwise pos = position of the discovered operator # pass expr[:pos] and expr[pos+1:] # to _constrct recursively # - Create a new treeNode # - Connect the three to return the root expr=expr.strip() if expr=="": return None elif self.isNumber(expr): return self.treeNode(expr, None, None) else: #--- code the rest ----

#Build the expression tree at self.treeRoot def constructTree(self, expr): # code one line to set self.treeRoot using _construct

# To check your constructTree e = expressionTree() expr =" 5*(2 / (3-1)) - (-1)*( 4 - 5*( 6- 3^(2-5) ) ) + 5 " e.constructTree(expr)

# The pseudo code in the lecture notes modified def getExpr(root): TL, TR = root.lchild, root.rchild if TL==None and TR==None: r = str(root.value) if float(r)<0: return "(" + r + ")" else: return r else: if TL==None: L = "" elif (root.value=="*" or root.value=="/" or root.value=="^") and (TL.value=="+" or TL.value=="-"): L = "(" + getExpr(TL) + ")" else: L = getExpr(TL) if TR==None: R = "" elif (root.value=="*" or root.value=="/" or root.value=="^") and (TR.value=="+" or TR.value=="-"): R = "(" + getExpr(TR) + ")" else: R = getExpr(TR) return L + str(root.value) + R print(getExpr(e.treeRoot)) ## This should print #5*2/(3-1)-(-1)*(4-5*(6-3^(2-5)))+5