On Python please! Wirte the function of polish notation and reverse polish notat
ID: 3865688 • Letter: O
Question
On Python please! Wirte the function of polish notation and reverse polish notation. Test code is given at the end.
# Complete polish() and revPolish() below. Follow the instructions in the comments
# Submission
#
# - no change of function / class names
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
def mask(self, s):
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):
try:
a = float(expr)
return True
except:
return False
def _construct(self,expr):
expr=expr.strip()
if expr=="":
return None
elif self.isNumber(expr):
return self.treeNode(expr, None, None)
else:
s = self.mask(expr)
pos = s.find("+")
if pos<0:
pos=s.find("-")
if pos<0:
pos=s.find("*")
if pos<0:
pos=s.find("/")
if pos<0:
pos=s.find("^")
if pos<0 and (expr[0]=="(" and expr[len(expr)-1]==")"):
return self._construct(expr[1:len(expr)-1])
opr = expr[pos]
root = self.treeNode(opr, None, None)
root.lchild = self._construct(expr[:pos])
root.rchild = self._construct(expr[pos+1:])
return root
def constructTree(self, expr):
self.treeRoot = self._construct(expr)
def _polish(self, root):
# root is the root of an expression tree.
# The function returns its polish notation.
# See the psedocode in the lecture note
# ----- code ------
def polish(self):
#------ code -----
def _revPolish(self, root):
# Similar for the reverse polish notation
# ----- code ------
def revPolish(self):
#----- code ------
e = expressionTree()
expr =" (( 2+ 4*2)*5 + 1 / 3) + 3*(3 + 5/4) + 12 "
e.constructTree(expr)
print(e.polish())
# This should print ++*+2*425/13+*3+3/5412
print(e.revPolish())
# and 242*+5*13/+3354/+*12++
Explanation / Answer
Solution========================================
This can be done by slightly modifying the Preorder(Polish) and PostOrder(Reverse Polish) Tree Traversal techinques.
Code:
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
def mask(self, s):
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):
try:
a = float(expr)
return True
except:
return False
def _construct(self,expr):
expr=expr.strip()
if expr=="":
return None
elif self.isNumber(expr):
return self.treeNode(expr, None, None)
else:
s = self.mask(expr)
pos = s.find("+")
if pos<0:
pos=s.find("-")
if pos<0:
pos=s.find("*")
if pos<0:
pos=s.find("/")
if pos<0:
pos=s.find("^")
if pos<0 and (expr[0]=="(" and expr[len(expr)-1]==")"):
return self._construct(expr[1:len(expr)-1])
opr = expr[pos]
root = self.treeNode(opr, None, None)
root.lchild = self._construct(expr[:pos])
root.rchild = self._construct(expr[pos+1:])
return root
def constructTree(self, expr):
self.treeRoot = self._construct(expr)
def _polish(self, root):
# root is the root of an expression tree.
# The function returns its polish notation.
# See the psedocode in the lecture note
x=root.value+""
if root.lchild:
x+=self._polish(root.lchild)
if root.rchild:
x+=self._polish(root.rchild)
return x
def polish(self):
return self._polish(self.treeRoot)
def _revPolish(self, root):
# Similar for the reverse polish notation
x=""
if root != None:
x+=self._revPolish(root.lchild)
x+=self._revPolish(root.rchild)
x+=root.value
return x
def revPolish(self):
return self._revPolish(self.treeRoot)
e = expressionTree()
expr =" (( 2+ 4*2)*5 + 1 / 3) + 3*(3 + 5/4) + 12 "
e.constructTree(expr)
print(e.polish())
print(e.revPolish())
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.