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```