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

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python