Question

Problem 3: Printing Expression Trees (15 points) Modify the function printexp given in chapter 6.7 your book (and hw6_tools.py) so that the parentheses are not printed around an operand if the operand consists only of a number. Note that the function printexp doesn't actually print the expression, it returns a string. The following function call on the expression tree created for problem 1 should result in the exact fully parenthesized expression we gave you. print (printexp (expTree))

# Problem 3

def printexp(tree):
sVal = ""
if tree:
sVal = '(' + printexp(tree.getLeftChild())
sVal = sVal + str(tree.getRootVal())
sVal = sVal + printexp(tree.getRightChild())+')'
return sVal

#### Functions and classes to help with Homework 6

#### You should not make any changes to the functions and classes in this file,
#### but you should understand what they do and how they work.

import sys

### This function will be re-defined in hw6.py. However, it is needed for ExpTree,
### so it is redefined here as well. Do not modify this function, modify the
### one in hw6.py!
def printexp(tree):
sVal = ""
if tree:
sVal = '(' + printexp(tree.getLeftChild())
sVal = sVal + str(tree.getRootVal())
sVal = sVal + printexp(tree.getRightChild())+')'
return sVal

class ExpTree:
def __init__(self,key):
self.key = key
self.leftChild = None
self.rightChild = None

def setRightChild(self, child):
self.rightChild = child
def setLeftChild(self, child):
self.leftChild = child
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild

def setRootVal(self,obj):
self.key = obj
def getRootVal(self):
return self.key

def __str__(self):
sVal = printexp(self)
return sVal

class Graph:
def __init__(self):
self.vertices = {}
self.numVertices = 0

def addVertex(self,key):
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertices[key] = newVertex
return newVertex

def getVertex(self,n):
if n in self.vertices:
return self.vertices[n]
else:
return None

def __contains__(self,n):
return n in self.vertices

def addEdge(self,f,t,cost=0):
if f not in self.vertices:
nv = self.addVertex(f)
if t not in self.vertices:
nv = self.addVertex(t)
self.vertices[f].addNeighbor(self.vertices[t],cost)

def getVertices(self):
return list(self.vertices.keys())

def __iter__(self):
return iter(self.vertices.values())

class Vertex:
def __init__(self,num):
self.id = num
self.connectedTo = {}
self.color = 'white'
self.dist = sys.maxsize
self.pred = None
self.disc = 0
self.fin = 0

# def __lt__(self,o):
# return self.id < o.id

def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr] = weight

def setColor(self,color):
self.color = color

def setDistance(self,d):
self.dist = d

def setPred(self,p):
self.pred = p

def setDiscovery(self,dtime):
self.disc = dtime

def setFinish(self,ftime):
self.fin = ftime

def getFinish(self):
return self.fin

def getDiscovery(self):
return self.disc

def getPred(self):
return self.pred

def getDistance(self):
return self.dist

def getColor(self):
return self.color

def getConnections(self):
return self.connectedTo.keys()

def getWeight(self,nbr):
return self.connectedTo[nbr]

def __str__(self):
return str(self.id) + ":color " + self.color + ":disc " + str(self.disc) + ":fin " + str(self.fin) + ":dist " + str(self.dist) + ":pred \n\t[" + str(self.pred)+ "]\n"

def getId(self):
return self.id

class PriorityQueue:
def __init__(self):
self.heapArray = [(0,0)]
self.currentSize = 0

def buildHeap(self,alist):
self.currentSize = len(alist)
self.heapArray = [(0,0)]
for i in alist:
self.heapArray.append(i)
i = len(alist) // 2
while (i > 0):
self.percDown(i)
i = i - 1

def percDown(self,i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapArray[i][0] > self.heapArray[mc][0]:
tmp = self.heapArray[i]
self.heapArray[i] = self.heapArray[mc]
self.heapArray[mc] = tmp
i = mc

def minChild(self,i):
if i*2 > self.currentSize:
return -1
else:
if i*2 + 1 > self.currentSize:
return i*2
else:
if self.heapArray[i*2][0] < self.heapArray[i*2+1][0]:
return i*2
else:
return i*2+1

def percUp(self,i):
while i // 2 > 0:
if self.heapArray[i][0] < self.heapArray[i//2][0]:
tmp = self.heapArray[i//2]
self.heapArray[i//2] = self.heapArray[i]
self.heapArray[i] = tmp
i = i//2

def add(self,k):
self.heapArray.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)

def delMin(self):
retval = self.heapArray[1][1]
self.heapArray[1] = self.heapArray[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapArray.pop()
self.percDown(1)
return retval

def isEmpty(self):
if self.currentSize == 0:
return True
else:
return False

def decreaseKey(self,val,amt):
# this is a little wierd, but we need to find the heap thing to decrease by
# looking at its value
done = False
i = 1
myKey = 0
while not done and i <= self.currentSize:
if self.heapArray[i][1] == val:
done = True
myKey = i
else:
i = i + 1
if myKey > 0:
self.heapArray[myKey] = (amt,self.heapArray[myKey][1])
self.percUp(myKey)

def __contains__(self,vtx):
for pair in self.heapArray:
if pair[1] == vtx:
return True
return False

def dijkstra(aGraph,start):
pq = PriorityQueue()
start.setDistance(0)
pq.buildHeap([(v.getDistance(),v) for v in aGraph])
while not pq.isEmpty():
currentVert = pq.delMin()
for nextVert in currentVert.getConnections():
newDist = currentVert.getDistance() \
+ currentVert.getWeight(nextVert)
if newDist < nextVert.getDistance():
nextVert.setDistance( newDist )
nextVert.setPred(currentVert)
pq.decreaseKey(nextVert,newDist)

Answer 1

Explanation in code comment :

rest of the code is same, only the printexp is modified as asked

CODE :

# Problem 3
"""
def printexp(tree):
sVal = ""
if tree:
sVal = '(' + printexp(tree.getLeftChild())
sVal = sVal + str(tree.getRootVal())
sVal = sVal + printexp(tree.getRightChild())+')'
return sVal
"""
#### Functions and classes to help with Homework 6
#### You should not make any changes to the functions and classes in this file,
#### but you should understand what they do and how they work.

import sys

### This function will be re-defined in hw6.py. However, it is needed for ExpTree,
### so it is redefined here as well. Do not modify this function, modify the
### one in hw6.py!

"""
EXPLANATION : Instead of adding braces whenever each node is calculated , we only need to add braces
whenever an expression is being evaluated and after traversal of left and right child
Hence by addding the condition of adding braces before and after the evaulted expression
for a given tree only when non numeric data is encountered solves the problem
EX : Simplify the tree for one root and 2 child nodes
*
/ \
2 5
the output would be (2*5)
Hence first left child call is made - sVal = 2
then again left and right call for node 2 are made and returned
Then node data is added - sVal = 2*
then right child call is made - sVal = 2*5
then again left and right call for node 5 are made and returned
then we add braces before and after sVal - (sVal) = (2*5)
"""
def printexp(tree):
sVal = ""
if tree:
sVal = printexp(tree.getLeftChild())
sVal = sVal + str(tree.getRootVal())
sVal = sVal + printexp(tree.getRightChild())
if not str(tree.getRootVal()).isnumeric():
sVal = '(' + sVal + ')'
return sVal

class ExpTree:
def __init__(self,key):
self.key = key
self.leftChild = None
self.rightChild = None
  
def setRightChild(self, child):
self.rightChild = child
def setLeftChild(self, child):
self.leftChild = child
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
  
def setRootVal(self,obj):
self.key = obj
def getRootVal(self):
return self.key
  
def __str__(self):
sVal = printexp(self)
return sVal

class Graph:
def __init__(self):
self.vertices = {}
self.numVertices = 0
  
def addVertex(self,key):
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertices[key] = newVertex
return newVertex
  
def getVertex(self,n):
if n in self.vertices:
return self.vertices[n]
else:
return None
  
def __contains__(self,n):
return n in self.vertices

def addEdge(self,f,t,cost=0):
if f not in self.vertices:
nv = self.addVertex(f)
if t not in self.vertices:
nv = self.addVertex(t)
self.vertices[f].addNeighbor(self.vertices[t],cost)

def getVertices(self):
return list(self.vertices.keys())

def __iter__(self):
return iter(self.vertices.values())

class Vertex:
def __init__(self,num):
self.id = num
self.connectedTo = {}
self.color = 'white'
self.dist = sys.maxsize
self.pred = None
self.disc = 0
self.fin = 0
  
# def __lt__(self,o):
# return self.id < o.id
  
def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr] = weight
  
def setColor(self,color):
self.color = color
  
def setDistance(self,d):
self.dist = d
  
def setPred(self,p):
self.pred = p
  
def setDiscovery(self,dtime):
self.disc = dtime
  
def setFinish(self,ftime):
self.fin = ftime
  
def getFinish(self):
return self.fin
  
def getDiscovery(self):
return self.disc
  
def getPred(self):
return self.pred
  
def getDistance(self):
return self.dist
  
def getColor(self):
return self.color
  
def getConnections(self):
return self.connectedTo.keys()
  
def getWeight(self,nbr):
return self.connectedTo[nbr]
  
def __str__(self):
return str(self.id) + ":color " + self.color + ":disc " + str(self.disc) + ":fin " + str(self.fin) + ":dist " + str(self.dist) + ":pred \n\t[" + str(self.pred)+ "]\n"
  
def getId(self):
return self.id
  

class PriorityQueue:
def __init__(self):
self.heapArray = [(0,0)]
self.currentSize = 0
  
def buildHeap(self,alist):
self.currentSize = len(alist)
self.heapArray = [(0,0)]
for i in alist:
self.heapArray.append(i)
i = len(alist) // 2
while (i > 0):
self.percDown(i)
i = i - 1

def percDown(self,i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapArray[i][0] > self.heapArray[mc][0]:
tmp = self.heapArray[i]
self.heapArray[i] = self.heapArray[mc]
self.heapArray[mc] = tmp
i = mc
  
def minChild(self,i):
if i*2 > self.currentSize:
return -1
else:
if i*2 + 1 > self.currentSize:
return i*2
else:
if self.heapArray[i*2][0] < self.heapArray[i*2+1][0]:
return i*2
else:
return i*2+1
  
def percUp(self,i):
while i // 2 > 0:
if self.heapArray[i][0] < self.heapArray[i//2][0]:
tmp = self.heapArray[i//2]
self.heapArray[i//2] = self.heapArray[i]
self.heapArray[i] = tmp
i = i//2

def add(self,k):
self.heapArray.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)
  
def delMin(self):
retval = self.heapArray[1][1]
self.heapArray[1] = self.heapArray[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapArray.pop()
self.percDown(1)
return retval

def isEmpty(self):
if self.currentSize == 0:
return True
else:
return False

def decreaseKey(self,val,amt):
# this is a little wierd, but we need to find the heap thing to decrease by
# looking at its value
done = False
i = 1
myKey = 0
while not done and i <= self.currentSize:
if self.heapArray[i][1] == val:
done = True
myKey = i
else:
i = i + 1
if myKey > 0:
self.heapArray[myKey] = (amt,self.heapArray[myKey][1])
self.percUp(myKey)

def __contains__(self,vtx):
for pair in self.heapArray:
if pair[1] == vtx:
return True
return False

def dijkstra(aGraph,start):
pq = PriorityQueue()
start.setDistance(0)
pq.buildHeap([(v.getDistance(),v) for v in aGraph])
while not pq.isEmpty():
currentVert = pq.delMin()
for nextVert in currentVert.getConnections():
newDist = currentVert.getDistance() \
+ currentVert.getWeight(nextVert)
if newDist < nextVert.getDistance():
nextVert.setDistance( newDist )
nextVert.setPred(currentVert)
pq.decreaseKey(nextVert,newDist)

rl2 = ExpTree(5)
rr2 = ExpTree(2)
rr1 = ExpTree('-')
ll3 = ExpTree(1)
lr3 = ExpTree(2)
lr2 = ExpTree('/')
ll2 = ExpTree(3)
ll1 = ExpTree('+')
r = ExpTree('*')
r.setLeftChild(ll1)
r.setRightChild(rr1)
ll1.setLeftChild(ll2)
ll1.setRightChild(lr2)
lr2.setLeftChild(ll3)
lr2.setRightChild(lr3)
rr1.setLeftChild(rl2)
rr1.setRightChild(rr2)
print(str(r))

ktuzzy Spyder (Python 3.J) Eile Edit Searh So un Debug Consales Projects Tools View Help Var able espkre NameType Size 15 inport sys 18nnat This function will be re-defined in hiv6.py. Mowever, it is needed for. ExpTree 19 ### so it is redefined here as well. Do not modify this function, modify the 2022# one in hit.py! 23 EXPLANATIONInstead ot adding braces whenever each nade is calculated, we only need to add braces 24 whenever an expression is being evaluated and after traversal of left and right child 25 Hence by addding the condition of adding braces before and after the evaulted cxpression 26 for a given tree only whern nn numeric data is encountered solves the problen 27EX Simplify the tree for one root and 2 child nodes 28 Vaniab e explorer Fle xp orer Hal Fython corsle 29 31 the output would be (2*5) Hence first left child call is nade- sVal -2 32 then again left and right call for node 2 are made and returned Then node data is added sVal 2 then right child call is nade -sVal -25 then again left and right call for node 5 are made and returned then we add braces before and after sVal (sVal)(2*5) ile "C:/Users/Rogue/Desktop/knapsack.py", line 53, in str sVal - printexp(self) ile "C:/Users/Rogue/Desktop/knapsack.py", line 24, in printexp sVal - printexp(tree.eetleftChildo) 36 37 38 39 def printexp(tree): 40 sWal ile "C:/Users/Rogue/Desktop/knapsack.py", line 24, in printexp sVal - printexp(tree.eetleftChildo) 41 if tree sVal-printexp(tree.getLeftchild)> sVal sValstr(tree.EctRootval)) sVal - sVal printexp tree-getRightChild)) if not str(tree.getRootVal()).isnuneric(): ile "C:/Users/Rogue/Desktop/knapsack.py", line 27, in printexp if not tree.zetRootVal) isnuneric 13 AttributeError: 'int' object has no attribute 'isnumeric' 7 return sVa In [23] 58 class ExpTree In L23]: Desktop runt i le('C:/users/Rogue/Desktop/knapsack.py., wcir-C:/Users/Rague/ 51 definit(self,key) 52 sels.key- key self.leftChild -None self.rightchild None 53 In [24] Python console Hatcry log Permissiccrs RW End-af-lines: CHLF Encading: UI-B Line: 38 Column: 5 Memory 53% 1003 AM O Typc here to searc 5/30/2019

ktuzzy Spyder (Python 3.J) Eile Edit Searh So un Debug Consales Projects Tools View Help Var able espkre NameType Size 58 class ExpTree 51 def-init-(self,key); self.key -key self.leftchild None self.rightChild-None 52 53 56 def setRightChild(self, child): self.rightChild-child 58 def setLeftChild(self, child): self.leftchild- child 60 der getRightChild(sel) return self.rightChild 62 def getLeftchild(self) return self.leftChild 57 61 Vaniab e explorer Fle xp orer Hal 63 Fython corsle 64 65 def setRootVal self,obj): self.key obi 67 def getRootVal(seLf) return self.key File"C:/users/Rogue/Desktop/knapsack.ру", line sVal-printexp(tree.getLeftchildo) 24, in printexp det str (self): File"C:/Users/Rogue/Desktop/knapsack.ру", sVal-printexp(tree.getLeftchildo) line 24, in printexp sVal-printexp(self) return sVal 72 73 File ·C:/users/Rogue/Desktop/knapsack.py", line 27, in printexp if not tree.getRootval().isnuneric: 75 class Graph 76 def init (selt): self.vertices seU'nunvertices- AttributeError:int' object has no attribute 'isnumeric 79 In 23 se def addVertex(seげ.key): self.nunVertices sel.numVertices 1 neWertex Vertex key) self.vertices[key] neVertex 81 In [23]: run rile(.C:/users/Rogue/Desktop/knapsack.ру. wd1r'C:/Users/Rogue/ Desktop) 92 84 return newvertex 85 In L24j: Desktop runt i le('C:/users/Rogue/Desktop/knapsack.ру", wcir-'с:/Users/Rague/ 86 def getVertex(seLf,n) 87 if n in self.vertices return self.vertices[n] 93 In [25 89 Python console Hatcry log Permissiccrs RW End-af-lines: CHLF Encading: UI-B Line: 3 Column: 5 Memory: 34% 1005 AM ENG 5/30/2019 O Typc here to searc ^ dyp

ktuzzy Spyder (Python 3.J) Eile Edit Searh So un Debug Consales Projects Tools View Help Var able espkre Crapeack.py X Natrie. Type . Size 75 class Graph 76 definit(self): self.vertices O selj.numVertices-숍 73 80 def addVertex(sel,key) 81 seLf.nunVertices - self.numVertices 1 ne㎸ertex-vertex(key) sels.vertices[key] newvertex 83 94 return nevertex 86 der getvertex(sel,n) it n in self.vertices: return self.vertices [n] clse: Vaniab e explorer Fle xp orer Hal 83 Fython corsle 96 return None 92 der _contains__(self,n): return n in self.vertices 93 File "C:/Users/Rogue/Desktop/knapsack.py ine 24, in printexp sVal-printexp(tree.getLeftchildo) 95 def addEdge(sel,r,t,cost-0) 96 it t not in self.vertices: nv-self.addvertex(f) if t not in self.vertices nv - self addVertex(t) self.vertices[f].addWeighbor(self.vertices[t],cost) File "C:/Users/Rogue/Desktop/knapsack.py ine 24, in printexp sVal-printexp(tree.getLeftchildo) File "C:/users/Rogue/Desktop/knapsack.ру", line 27, in printexp if not tree.getRootval().isnuneric: 180 1e1 102 def getVertices (self): return list(self.vertices.keys()) AttributeError:int' object has no attribute 'isnumeric 183 1e4 les det iter (self) : In 23 return iter(self.vertices.values)) 186 107 In [23]: run rile(.C:/users/Rogue/Desktop/knapsack.ру. wd1r'C:/Users/Rogue/ Desktop) 108 189 class Vertex 110 def-init-(self,num); self.id-nun self.connectedTo- self.colorwhite self.dist- sys.maxsize self.pred - None In L24]: runfile( C:/Users/Rogue /Desktop/knapsack.py, wdir-'C:/Users/Rague/ Desktop 113 114 In [25 115 Python console Hatcry log Permissiccrs RW End-af-lines: CHLF Encading: UI-B Line: 3 Column: 5 Memory- 53% 1005 AM O Typc here to searc 5/30/2019

ktuzzy Spyder (Python 3.J) Eile Edit Searh So un Debug Consales Projects Tools View Help Var able espkre NameType Size 90 return None 91 92 det -contains return n in (self,n): self.vertices 93 94 95 def addEdge(selt,t,t,cost-) if f not in self.vertices: nv-sely.addvertex( it t not in self.vertices: nv -self.addvertex(t) sels.vertices.addeighbor(self.vertices[t],cost) 96 97 98 180 101 eetVertices(self) return list(self.vertices, keys)) Vaniab e explorer Fle xp orer Hal 102 103 104 def Fython corsle 185 defiter (selfp): e6 return iter self.vertices,values)) 107 File "C:/Users/Rogue/Desktop/knapsack.py ine 24, in printexp sVal-printexp(tree.getLeftchildo) 188 189 class Vertex: 1 def init (seL, num) self.idnum self.connectedTo- self.colorhite self.dist sys.maxsize sels.pred None self.disc - seげ. fin-e File "C:/Users/Rogue/Desktop/knapsack.py ine 24, in printexp sVal-printexp(tree.getLeftchildo) 112 113 File ·C:/users/Rogue/Desktop/knapsack.py", line 27, in printexp if not tree.getRootval().isnuneric: 115 116 AttributeError:int' object has no attribute 'isnumeric 118 119 #def-Lt-(self,o): return self. id<o.id In 23 120 121 In [23]: run rile(.C:/users/Rogue/Desktop/knapsack.ру. wd1r'C:/Users/Rogue/ Desktop) 122 def addNeighbor (self,nbr,weight-B): self.connectedTo[nbrweight 123 124 def setColor(selt,colar) f.color color In L24j: Desktop runt i le('C:/users/Rogue/Desktop/knapsack.py., wcir-'с:/Users/Rague/ 126 127 128 def setDistance(self,d): self.dist d In [25 Python console Hatcry log Permissiccrs RW End-af-lines: CHLF Encading: UI-B Line: 3 Column: 5 Memory: 34% 10:03 AM O Typc here to searc 5/30/2019

ktuzzy Spyder (Python 3.J) Eile Edit Searh So un Debug Consales Projects Tools View Help Var able espkre NameType Size 129 self.dist d 131 def setPred (sel,p): 132 self-pred-p 133 134 def setDiscovery(sely,dtime): self.disc-dtime 135 136 137 def setFinish(sels, rtin) self.tin ttine 133 139 140 def getFinish(sel: 141 return self.fin Vaniab e explorer Fle xp orer Hal 142 143 def getDiscovery(sel) return self.dist Fython corsle 144 145 146 147 def getPred (self): return self-pred File "C:/Users/Rogue/Desktop/knapsack.py ine 24, in printexp sVal-printexp(tree.getLeftchildo) 148 149 def getDistance(self) return self.dist 158 File"C:/Users/Rogue/Desktop/knapsack.ру", sVal-printexp(tree.getLeftchildo) line 24, in printexp 151 152 def getColor(selJ 153 return self.color File "C:/users/Rogue/Desktop/knapsack.ру", line 27, in printexp if not tree.getRootval().isnuneric: 155 def getConnections(selJ) 156 return self.connectedTo.keys) AttributeError:int' object has no attribute 'isnumeric 157 158 def geteight(sels,nbr) 159 return self.connectedToIntr亅 In 23 160 161 def str_(self): 162 163 In [231: runfile(C:/Users/Roeue/Desktop/knapsack. py, wdir-'C:/Users/Rogue/ Desktop) return str(self.id) + .:color " + self.color + ":disc " + str(self,disc) + ":fin " + str(self.tin) + ":dist . 164 def getId(sel 165 return self.id In L24j: Desktop runt i le('C:/users/Rogue/Desktop/knapsack.py., wcir-'с:/Users/Rague/ 166 167 168 class PriorityQueue 169 definit (self) In [25 Python console Hatcry log Permissiccrs RW End-af-lines: CHLF Encading: UI-B Line: 3 Column: 5 Memory- 53% 1003 AM O Typc here to searc 5/30/2019

ktuzzy Spyder (Python 3.J) Eile Edit Searh So un Debug Consales Projects Tools View Help Var able espkre Crapeack.py X NameType Size 167 168 class PriorityQueue 169 def-init-(self); 179 self.heapArray- I(a,e) self.currentsize-う 172 def buildHeap(self,alist) self.currentsizelen(alist) sels.heapArray [(,0)1 tori in alist self.heaprray.append(i) i -len(alist) / 2 while ( > ): self.percDown (1) i- 1 174 175 176 178 179 Vaniab e explorer Fle xp orer Hal 180 181 Fython corsle 182 183 def pereDown(self,i): 184 while (i * 2)にself.currentSize: 185 mc-self.mǐnChild(i) if self.heapArrey[i][e] > self.heapArray[mc][] tnp sels.heapArray[i] self.heapArrayLi]-self.heapArrayLnc] self.heaphrray[nc]tp File "C:/Users/Rogue/Desktop/knapsack.py ine 24, in printexp sVal-printexp(tree.getLeftchildo) 186 187 183 File "C:/Users/Rogue/Desktop/knapsack.py ine 24, in printexp sVal-printexp(tree.getLeftchildo) 189 190 191 File "C:/users/Rogue/Desktop/knapsack.ру", line 27, in printexp if not tree.getRootval().isnuneric: 192 def minchild(self,i): if i*2 self.currentSize: 194 return -1 AttributeError:int' object has no attribute 'isnumeric 195 196 197 if i 21 self.currentSize: return i*2 In 23 193 if self.heapArray[i 21fe1< self.heapArray[i 2 11101: return i2 In [23]: run rile(.C:/users/Rogue/Desktop/knapsack.ру. wd1r'C:/Users/Rogue/ Desktop) 199 200 201 202 return i 241 203 In L24j: Desktop runt i le('C:/users/Rogue/Desktop/knapsack.ру", wcir-'с:/Users/Rague/ 284 def percUp(self,i): while ǐ // 2 > 0; it self.heapArrayLiJleseLf.heapArraylil2jLe] tmp self.heapArray[L//2] 206 In [25 Python console Hatcry log Permissiccrs RW End-af-lines: CHLF Encading: UI-B Line: 38 Column: 5 Merncry- 53% ENG 100 AM 5/30/2019 O Typc here to searc

ktuzzy Spyder (Python 3.J) Eile Edit Searh So un Debug Consales Projects Tools View Help Var able espkre Natrie. Type . Size 199 it self.heapårrayLi2JLe< self.heapArrayLi21] eturn i*2 else: 280 eturi i 2+1 283 204 def percUp(self,i) hile i f2 > : if self.heapArrey[i][e] < self.heapArray[i//2][9]: tnp sels.heapArray[i//21 self-heapArrayli//2] -self.heaparrayliļ self.heaphrray[i] tmp i i//2 286 207 208 289 211 def add(self,k): self.heapArray, append (k) se .currentSize-selt.currentSize + 1 self.percUp(self.currentsize) Vaniab e explorer Fle xp orer Hal 212 213 Fython corsle 214 215 216 217 def delMin(self): retvel- self.heaprray[1]1] self,heapArray [1self.heapArrayIself.currentsizel self.currentSize -seLcrrentSize1 self.heapArray.pop) self.percDown (1) File"C:/Users/Rogue/Desktop/knapsack.ру", sVal-printexp(tree.getLeftchildo) line 24, in printexp 219 220 File"C:/Users/Rogue/Desktop/knapsack.ру", sVal-printexp(tree.getLeftchildo) line 24, in printexp 221 223 return retval File "C:/users/Rogue/Desktop/knapsack.ру", line 27, in printexp if not tree.getRootval().isnuneric: 225 def isEnpty(self): 226 it self.currentsize: return True clse: AttributeError:int' object has no attribute 'isnumeric 227 228 229 return False In 23 231 def decreaseKey (self,val,ant): 232# this is a litt Le wierd, but we need to tind the heap thing to decrease by 233 Looking at its value 234 In [23]: run rile(.C:/users/Rogue/Desktop/knapsack.ру. wd1r'C:/Users/Rogue/ Desktop) done - False 235 In L24j: Desktop runt i le('C:/users/Rogue/Desktop/knapsack.py., wcir-'с:/Users/Rague/ 236 while not done and ǐにself.currentSize: it self.heapArrayliļ[1] --val: doneTrue 237 233 In [25 Python console Hatcry log Permissiccrs RW End-af-lines: CHLF Encading: UI-B Line: 3 Column: 5 Memory- 53% 10:03 AM O Typc here to searc 5/30/2019

ktuzzy Spyder (Python 3.J) Eile Edit Searh So un Debug Consales Projects Tools View Help Var able espkre Crapeack.py X NameType Size Natrie ▲ def decreaseKey(self,val, ant): 232this is a little wierd, but we need to find the heop thing to decrease by 233# looking at its value 234 done False 235 236 237 while not done and 1 ← seL.currentSize: if self.heapA ray[1 [1]val: done True 238 239 248 nyKey i 241 243 self.heapArray[myKey(ant,self.heapArray[myKey1]) self.percUp (mykey) Vaniab e explorer Fle xp orer Hal 245 Fython corsle 246 247 def_contains_(self,vtx): or pair in self.heapArray: 249 File "C:/Users/Rogue/Desktop/knapsack.py ine 24, in printexp sVal-printexp(tree.getLeftchildo) return True return False 251 252 File"C:/Users/Rogue/Desktop/knapsack.ру", sVal-printexp(tree.getLeftchildo) line 24, in printexp 254 def dijkstra(aGraph, start): pq PriotyQueue) start.setDistance(8) pq.buildHcap v.eetDistance),v) for v in aGraph]) thile nat pq.isEmpty() currentVert pq.delMin) for nextvert in currentvert.getonnections) neDist-currentvert.getDistance) currentvert.getihleight(nextvert) if newDistnextvert.eetDistance) File "C:/users/Rogue/Desktop/knapsack.ру", line 27, in printexp if not tree.getRootval().isnuneric: 256 257 AttributeError:int' object has no attribute 'isnumeric 261 In 23 262 263 In [23]: run rile(.C:/users/Rogue/Desktop/knapsack.ру. wd1r'C:/Users/Rogue/ Desktop) 264 nextVert.setDistance newDist) nextvert.setPred(currentvert) pq decreaseKcy(nextvert,newDist) 265 266 267 In L24j: Desktop runt i le('C:/users/Rogue/Desktop/knapsack.py., wcir-'с:/Users/Rague/ 268 269 r12 -ExpTree(5) 27 rr2 -ExpTree(2) In [25 222 113-FrenTrer(1 Python console Hatcry log Permissiccrs RW End-af-lines: CHLF Encading: UI-B Line: 38 Column: 5 Merncry- 53% 10:03 AM O Typc here to searc 5/30/2019

ktuzzy Spyder (Python 3.J) Eile Edit Searh So un Debug Consales Projects Tools View Help Var able espkre Natrie. Type . Size return True return False 251 252 253 254 def dijkstra(aGraph,start): pq PriorityQueue) start.setDistance() pq.buildHeap ([(v.getoistance(),v) for 낱 in aGraph]》 while not pq.isEmpty): currentVert pa.de Min) for nextWert in currentVert.getconnections(): newDist- currentvert.eetDistance() +currentVert.gight (nextVert) if nenDistくnextvert, getDistance() 257 258 260 261 262 263 Vaniab e explorer Fle xp orer Hal 264 nextVert, setDistance( newOist) nextVert.setPred(currentVert) pq . decreaseKey (nextVert, neNDǐ st ) Fython corsle 265 266 267 268 File "C:/Users/Rogue/Desktop/knapsack.py ine 24, in printexp sVal-printexp(tree.getLeftchildo) 269 rl2ExpTree(5) 270 rr2 ExpTree(2) 271 rr1 -ExpTre) 272 113ExpTree(1) 273 1r3 ExpTree(2) File"C:/Users/Rogue/Desktop/knapsack.ру", sVal-printexp(tree.getLeftchildo) line 24, in printexp File "C:/users/Rogue/Desktop/knapsack.ру", line 27, in printexp if not tree.getRootval().isnuneric: 275 112 ExpTree(3) 276 111 ExpTree) 277 r-ExpTree('·') 278 r.setLeftchild(ll1) 279 r.setRightChild(rr1) 280 111.setlettChild(112) 281 111.setRightchild(lr2) 282 1r2,setLeftChild(113) 283 Ir2.setRightChild(Ir3) 284rrl.setLeftChild(rl2) 285rr1,setRightChild(rr2) 286 print (str(r)) AttributeError:int' object has no attribute 'isnumeric In 23 In [23]: run rile(.C:/users/Rogue/Desktop/knapsack.ру. wd1r'C:/Users/Rogue/ Desktop) In L24j: Desktop runt i le('C:/users/Rogue/Desktop/knapsack.py., wcir-'с:/Users/Rague/ 287 299 In [25 290 Python console Hatcry log Permissiccrs RW End-af-lines: CHLF Encading: UI-B Line: 38 Column: 5 Merncry- 53% 1003 AM O Typc here to searc 5/30/2019

| In [23]: runfile("C:/users/Rogue/Desktop/knapsack . py', wdr="c:/Users/Rogue/ Desktop') In [24]: runfile("C:/Users/Rogue/Desktop/knapsack·py ', Desktop') wdr= 'C:/Users/Rogue/