Instructions
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