In Python , create a parser that produces a parse tree composed of \"nodes\", fo
ID: 3844447 • Letter: I
Question
In Python, create a parser that produces a parse tree composed of "nodes", for the following grammar:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Sample BNF Grammar for expressions. Note: this grammar avoids left recursion
;; making it easier to support LL recursive descent parsing.
;;
;; <expr> ::- <term> ADD <expr>
;; | <term>
;;
;; <term> ::- <factor> MULTIPLY <term>
;; | <factor>
;;
;; <factor> ::- LPAREN <expr> RPAREN
;; | NUM
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Write test code to iterate through the parse tree in post order outputting a reverse-polish descriptive string for the parse tree. For example.
Given input: "(5 + 3) * 8" without the quotes, the output should be "5 3 + 8 *" without the quotes.
Given input: "5 + 3 * 8" without the quotes, the output should be "5 3 8 * +" without the quotes.
Explanation / Answer
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
def insertLeft(self,newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRight(self,newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
def setRootVal(self,obj):
self.key = obj
def getRootVal(self):
return self.key
def postorder(self):
if self != None:
postorder(self.getLeftChild())
postorder(self.getRightChild())
print(self.getRootVal())
def buildParseTree(fpexp):
fplist = fpexp.split()
pStack = Stack()
eTree = BinaryTree('')
pStack.push(eTree)
currentTree = eTree
for i in fplist:
if i == '(':
currentTree.insertLeft('')
pStack.push(currentTree)
currentTree = currentTree.getLeftChild()
elif i not in ['+', '-', '*', '/', ')']:
currentTree.setRootVal(int(i))
parent = pStack.pop()
currentTree = parent
elif i in ['+', '-', '*', '/']:
currentTree.setRootVal(i)
currentTree.insertRight('')
pStack.push(currentTree)
currentTree = currentTree.getRightChild()
elif i == ')':
currentTree = pStack.pop()
else:
raise ValueError
return eTree
print("(5+3)*8: ")
pt = buildParseTree("( ( 5 + 3 ) * 8 )")
pt.postorder()
print(" 5+3*8: ")
pt = buildParseTree("( 5 + ( 3 * 8 ) )")
pt.postorder()
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.