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

June 14, 2024
Martin Jonas
🇦🇺 Australia
Python
Dr. Martin Jonas, PhD in Computer Science from Southern Cross University, Australia. With 4 years of experience in Python assignments, I offer expert guidance and support to help you excel in your programming projects.
Key Topics
• Instructions
• Requirements and Specifications
Tip of the day
News

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

## Similar Samples

Discover the quality and expertise we bring to programming assignments by exploring our sample work. Each sample illustrates our proficiency in handling diverse programming challenges across various languages and topics. Let these examples showcase our commitment to helping you achieve academic success.