Program To Implement Expression Tree and Linked List in Python Assignment Solution.

Instructions

Objective

Write a python assignment program to implement expression tree and linked list.

Requirements and Specifications

Source Code

EXPRESSION TREE from myStack import MyStack from expressionTreeNode import ConstantNode from expressionTreeNode import OperatorNode # Class that implements an expression tree data structure class MyExpressionTree(object): # input is a string that contains an infix math expression that ends with an = symbol # levels keeps track of the number of levels or height of the tree # nodes is the stack used to build the tree def __init__(self, input): self.input = input self.levels = 0 self.nodes = MyStack() self.build() def getLevels(self): return self.levels def getInput(self): return self.input def getRootNode(self): return self.nodes.getTop() def resetInput(self, input): self.input = input self.levels = 0 self.build() def printInfo(self): info = '' info += 'Levels: ' + str(self.getLevels()) + '\n' info += 'Input: ' + str(self.getInput()) + '\n' print(info, end = '') print('InOrder Traversal: ', end = '') self.printInOrder(self.getRootNode()) print() print('PostOrder Traversal: ', end = '') self.printPostOrder(self.getRootNode()) print() print('PreOrder Traversal: ', end = '') self.printPreOrder(self.getRootNode()) print() print('Value of Tree: ', self.evaluate(self.getRootNode()), end = '') print() # recursive method that prints the expression tree using pre-order traversal # @param root: the rootNode of the expression tree def printPreOrder(self,root): print(root.prefix()) # recursive method that prints the expression tree using in-order traversal # @param root: the rootNode of the expression tree def printInOrder(self,root): print(root.infix()) # recursive method that prints the expression tree using post-order traversal # @param root: the rootNode of the expression tree def printPostOrder(self,root): print(root.postfix()) # recursive method to evaluate the expression tree # @param root: the rootNode of the expression tree def evaluate(self,root): return root.value() # builds the expression tree using the self.nodes MyStack attribute # Precondition: the expression tree was initialized with a valid infix expression # self.input # Postcondition: Using the helper methods infixToPostfix and isNumber, the nodes # stack is properly filled def build(self): s = MyExpressionTree.infixToPostfix(self.input) i = 0 while i < len(s): if s[i].isdigit() or s[i] == '.': nextOperand = "" while s[i] != '+' and s[i] != '-' and \ s[i] != '*' and s[i] != '/' and \ s[i] != ' ': nextOperand += s[i] i += 1 self.nodes.push(ConstantNode(float(nextOperand))) elif s[i] == ' ': i += 1 else: # the character is an operator c = s[i] right_node = self.nodes.getTop() self.nodes.pop() left_node = self.nodes.getTop() self.nodes.pop() self.nodes.push(OperatorNode(c, left_node, right_node)) self.levels += 1 i += 1 # Helper method that returns the post fix notation of the infix input string # Precondition: @param input: a string containing only numbers and the math # operations +,-,*,/ The string will be in infix notation, for example 2+3*5=, # each input expression will NOT contain any whitespace and ends with the = symbol # Postcondition: Assuming the input string is a valid infix expression, # the post fix expression of input is returned with each token separated by whitespace def infixToPostfix(input): # stack used to create postfix string stack = MyStack() postFixString = '' nextOperand = '' i = 0 while input[i] != '=': # get next operand and add it to the postfix string. if input[i].isdigit() or input[i] == '.': while input[i] != '+' and input[i] != '-' and \ input[i] != '*' and input[i] != '/' and \ input[i] != '=' and input[i] != '(' and \ input[i] != ')': nextOperand+=input[i] i+=1 postFixString+=nextOperand postFixString+=' ' nextOperand = '' elif input[i] == '(': stack.push(input[i]) i+=1 elif input[i] == ')': while stack.getTop() != '(': postFixString+=stack.getTop() postFixString+=" " stack.pop() # discard the left parenthesis stack.pop(); i+=1 else: # the character is an operator while int(stack.getCount()) !=0 and stack.getTop() != '(' and \ (MyExpressionTree.getPrecedence(stack.getTop()) >= MyExpressionTree.getPrecedence(input[i])): postFixString+=str(stack.getTop()) postFixString+=" " stack.pop() stack.push(input[i]) i+=1 #pop rest of operators on the stack while int(stack.getCount())>0: postFixString+=stack.getTop() postFixString+=" " stack.pop() return postFixString # Helper method that returns the precedence order of an arithmetic operator # Precondition: @param theOperator: one of the following characters + - * / # Postcondition: returns the precedence of the operator def getPrecedence(theOperator): SUB = 0 ADD = 0 DIV = 1 MULT = 1 precedence = 0 if theOperator == '-': precedence = SUB elif theOperator == '+': precedence = ADD elif theOperator == '/': precedence = DIV elif theOperator == '*': precedence = MULT return precedence # Helper method that determines if a string is a floating point number # Precondition: @param string: a string # Postcondition: returns true if the string is a valid floating point number, otherwise # returns false def isNumber(string): try: float(string) return True except ValueError: return False STACK from myLinkedList import MyNode from myLinkedList import MyLinkedList class MyStack(MyLinkedList): def __init__(self, first = None, last = None): MyLinkedList.__init__(self, first = None, last = None) # Returns the string representation of the linked list. def __str__(self): stack = "" if self.size == 0: stack += "...EMPTY STACK...count = " + str(self.size) else: currentNode = self.first while currentNode is not None: stack += str(currentNode.data) if currentNode.next is not None: stack += "\n" currentNode = currentNode.next #stack += "\nTOP = " + str(MyLinkedList.getFirst(self)) #stack += " BOTTOM = " + str(MyLinkedList.getLast(self)) #stack += " SIZE = " + str(self.size) return stack # returns the top element of the stack # Postcondition: Assuming the stack is not empty, the top element # of the stack is returned, else return false def getTop(self): if self.size != 0: return MyLinkedList.getFirst(self) else: return False # adds a new item to the stack # Postcondition: The parameter theItem is added to the top of the stack def push(self, theItem): MyLinkedList.addFirst(self, theItem) def getCount(self): return str(self.size) # removes the top element of the stack # Precondition: the stack is not empty # Postcondition: the top element of the stack is removed from stack and the # size is decremented by 1 def pop(self): if self.first is not None: temp = self.first self.first = self.first.next del temp self.size -= 1 LINKED LIST # Defintion of the node to be used in the linked list class MyNode(object): def __init__(self, data, next = None): """Instantiates a Node with default next of None""" self.data = data self.next = next class MyLinkedList(object): def __init__(self, first = None, last = None): # Node pointing to the first element self.first = first # Node pointing to the last element self.last = last # the number of elements in the list self.size = 0 # Returns the string representation of the linked list. def __str__(self): linkedList = "" if self.size == 0: linkedList += "...EMPTY LIST...count = " + str(self.size) else: currentNode = self.first while currentNode is not None: linkedList += str(currentNode.data) if currentNode.next is not None: linkedList += "->" currentNode = currentNode.next linkedList += " ...count = " + str(self.size) return linkedList # adds the parameter theItem to the first part of the list # Postcondition: first points to the new list, newItem is inserted at the # beginning of the list, count is incremented by 1 def addFirst(self, theItem): # create new node based on input parameter newNode = MyNode(theItem, self.first) self.first = newNode self.size += 1 if self.last is None: self.last = newNode # adds the parameter theItem to the last part of the list # Postcondition: first points to the new list, newItem is inserted at the # end of the list, count is incremented by 1 def addLast(self,theItem): newNode = MyNode(theItem) # if the list was empty then the first and last nodes are the same if self.first is None: first = newNode else: self.last.next = newNode self.last = newNode self.size += 1 # returns the first element of the list # Postcondition: Assuming the list is not empty, the first element # of the list is returned, else return None def getFirst(self): if self.first is not None: return self.first.data else: return None # returns the last element of the list # Postcondition: Assuming the list is not empty, the last element # of the list is returned, else return None def getLast(self): if self.last is not None: return self.last.data else: return None