On python please! Don\'t change other functions. Test code is given at the end.

Question

On python please!  Don't change other functions. Test code is 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):

def isNumber(s):

#s must be a non-empty string

#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

Explanation / Answer

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):

def isNumber(s):

#s must be a non-empty string

#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

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.