-
Notifications
You must be signed in to change notification settings - Fork 0
/
Common_data_structures_class.py
189 lines (164 loc) · 5.17 KB
/
Common_data_structures_class.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
# -*- coding: utf-8 -*-
"""
Created on Wed Jan 24 19:21:12 2018
@author: Tirtha
"""
class Stack:
"""
Stack data structure using list
"""
def __init__(self,value):
"""
Class initializer: Produces a stack with a single value or a list of values
"""
self._items = []
if type(value)==list:
for v in value:
self._items.append(v)
self._height = len(value)
else:
self._items.append(value)
self._height = 1
def pop(self):
if self._height == 0:
print ("Stack is empty. Nothing to pop.")
return None
else:
self._height -=1
return self._items.pop()
def push(self,value):
self._height +=1
self._items.append(value)
def isEmpty(self):
return self._height==0
def draw(self):
if self.isEmpty():
pass
return None
else:
n=self._height
print('['+str(self._items[n-1])+']')
for i in range(n-2,-1,-1):
print(" | ")
print('['+str(self._items[i])+']')
###==============================================================================================
class Queue:
"""
Queue data structure using list
"""
def __init__(self,value):
"""
Class initializer: Produces a queue with a single value or a list of values
"""
self._items = []
if type(value)==list:
for v in value:
self._items.append(v)
self._length = len(value)
else:
self._items.append(value)
self._length = 1
def dequeue(self):
if self._length == 0:
print ("Queue is empty. Nothing to dequeue.")
return None
else:
self._length -=1
return self._items.pop(0)
def enqueue(self,value):
self._length +=1
self._items.append(value)
def isEmpty(self):
return self._length==0
def draw(self):
if self.isEmpty():
pass
return None
else:
n=self._length
for i in range(n-1):
print('['+str(self._items[i])+']-',end='')
print('['+str(self._items[n-1])+']')
###=================================================================================
class Tree:
"""
Recursive definition of Tree class plus various helper functions/methods
"""
def __init__(self, value, children):
"""
Class initializer: Produces a single root node having a specific string value;
children is a list of references to the root of the children branches.
Note th children are trees themselves, hence the recursion.
"""
self._value = value
self._children = children
def strep(self):
"""
Generates a string representation of the tree
"""
text = ""
text+=str(self._value)
for child in self._children:
text+='['
text+=child.strep()
text+=']'
return text
def get_value(self):
return self._value
def children(self):
for child in self._children:
yield child
def num_nodes(self):
result = 1
for child in self._children:
result+=child.num_nodes()
return result
def num_leaves(self):
if len(self._children)==0:
return 1
else:
result=0
for child in self._children:
result += child.num_leaves()
return result
def height(self):
height=0
for child in self._children:
height = max(height,child.height()+1)
return height
###================================================================================
class Arithmatic (Tree):
def __init__(self, value, children):
Tree.__init__(self, value, children)
def strexp(self):
if len(self._children)==0:
return str(self._value)
else:
text='('
text+=self._children[0].strexp()
text+=str(self._value)
text+=self._children[1].strexp()
text+=')'
return text
def evaluate_exp(self):
if len(self._children)==0:
if ('.' in self._value):
return float(self._value)
else:
return int(self._value)
else:
function = self._value
left_value = self._children[0].evaluate_exp()
right_value = self._children[1].evaluate_exp()
if function=='+':
return left_value+right_value
if function=='-':
return left_value-right_value
if function=='*':
return left_value*right_value
if function=='/':
return left_value/right_value
if function=='%':
return left_value%right_value
if function=='^':
return left_value**right_value