Skip to content

Commit a4aeb67

Browse files
author
bennwei
committed
update 12-17-2014
1 parent 8cbdde3 commit a4aeb67

File tree

9 files changed

+365
-0
lines changed

9 files changed

+365
-0
lines changed

‎ArrayQueue.py‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
class ArrayQueue(object):
2+
""" FIFO queue implementation using a Python list as underlying storage. """
3+
default_capacity = 10 # moderate capacity for all new queues
4+
5+
def __init__(self):
6+
""" made an empty queue. """
7+
self._data = [None] * ArrayQueue.default_capacity
8+
self._size = 0
9+
self._front = 0
10+
11+
def __len__(self):
12+
""" Return the number of elements in the queue. """
13+
return self._size
14+
15+
def is_empty(self):
16+
""" Return True if the queue is empty. """
17+
return self._size == 0
18+
19+
def first(self):
20+
""" Return (but do not remove) the element at the front of the queue. """
21+
if self.is_empty():
22+
raise ('Queue is empty')
23+
return self._data[self._front]
24+
25+
def dequeue(self):
26+
""" Remove and return the first element of the queue (i.e., FIFO). """
27+
if self.is_empty():
28+
raise ('Queue is empty')
29+
item_out = self._data[self._front]
30+
self._data[self._front] = None # help garbage collection
31+
self._front = (self._front + 1) % len(self._data) # implement a circular array. reset front position
32+
self._size -= 1
33+
return item_out
34+
35+
def enqueue(self, e):
36+
""" Add an element to the back of queue. """
37+
if self._size == len(self._data):
38+
self.resize(2*len(self._data)) # if queue is full, double the array size
39+
empty_position = (self._front + self._size) % len(self.data)
40+
self._data[empty_position] = e
41+
self._size += 1
42+
43+
def _resize(self, cap):
44+
""" Resize to a new list of capacity >= len(self)."""
45+
oldList = self._data # keep track of existing list
46+
self._data = [None] * cap # allocate list with new capacity
47+
walk = self._front
48+
for k in range(self._size): # only consider existing elements
49+
self._data[k] = oldList[walk]
50+
walk = (1+walk) % len(oldList)
51+
self._front = 0
52+
53+
54+
55+
56+
57+
58+

‎ArrayStack.py‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
class ArrayStack(object):
2+
""" LIFO Stack implementation using a Python list as underlying storage. """
3+
4+
def __init__(self):
5+
""" make an empty stack. """
6+
self._data = [] # non-public list instance
7+
8+
def __len__(self):
9+
"""Return the # of elements in the stack. """
10+
return len(self._data)
11+
12+
def is_empty(self):
13+
""" Return True is stack is empty. """
14+
return len(self._data) == 0
15+
16+
def push(self, e):
17+
""" Add element e to the top of the stack. """
18+
self._data.append(e) # new item stored at end of list
19+
20+
def top(self):
21+
""" Return (but do not remove) the element at the top of the stack.
22+
Raise Empty exception if the stack is empty.
23+
"""
24+
if self.is_empty():
25+
raise ('Stack is empty!')
26+
return self._data[-1] # the last item in the list
27+
28+
def pop(self):
29+
""" Remove and return the element from the top of the stack (i.e., LIFO)."""
30+
if self.is_empty():
31+
raise ('Stack is empty!')
32+
return self._data.pop()
33+
34+
35+
36+
37+
38+
39+
40+
41+
42+

‎CircularQueue.py‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
# -*- coding: utf-8 -*-
2+
class CircularQueue:
3+
""" Queue implementation using circularly linked list for storage. """
4+
#-------------------------- nested Node class --------------------------
5+
class _Node:
6+
""" Lightweight, nonpublic class for storing a singly linked node. """
7+
__slots__ = '_element', '_next' # streamline memory usage
8+
9+
def __init__(self, element, next): # initialize node’s fields
10+
self._element = element # reference to user’s element
11+
self._next = next # reference to next node
12+
13+
#------------------------------- Queue methods -------------------------------
14+
def __init__(self):
15+
""" set a empty queue. """
16+
self._tail = None # will represent tail of queue
17+
self._size = 0 # number of queue elements
18+
19+
def __len__(self):
20+
return self._size
21+
22+
def is_empty(self):
23+
return self._size == 0
24+
25+
def first(self):
26+
if self.is_empty():
27+
raise ('Queue is empty.')
28+
head = self._tail._next
29+
return head._element
30+
31+
def dequeue(self):
32+
if self.is_empty():
33+
raise ('Queue is empty.')
34+
old_head = self._tail._next
35+
if self._size == 1: # removing only element
36+
self._tail = None # queue becomes empty
37+
else:
38+
self._tail._next = old_head._next # bypass the old head
39+
self._size -= 1
40+
return old_head._element
41+
42+
def enqueue(self, e):
43+
newest = self._Node(e, None) # node will be new tail node
44+
if self.is_empty():
45+
newest._next = newest # initialize circularly
46+
else:
47+
newest._next = self._tail._next # new node points to head
48+
self._tail._next = newest # old tail points to new node
49+
self._tail = newest
50+
self._size += 1
51+
52+
def rotate(self):
53+
""" Rotate front element to the back of the queue. """
54+
if self._size > 0:
55+
self._tail = self._tail._next # old head becomes new tail
56+
57+
58+
59+
60+
61+
62+
63+
64+
65+

‎LIFO.py‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
class ArrayStack(object):
2+
""" LIFO Stack implementation using a Python list as underlying storage. """
3+
4+
def __init__(self):
5+
""" make an empty stack. """
6+
self._data = [] # non-public list instance
7+
8+
def __len__(self):
9+
"""Return the # of elements in the stack. """
10+
return len(self._data)
11+
12+
def is_empty(self):
13+
""" Return True is stack is empty. """
14+
return len(self._data) == 0
15+
16+
def push(self, e):
17+
""" Add element e to the top of the stack. """
18+
self._data.append(e) # new item stored at end of list
19+
20+
def top(self):
21+
""" Return (but do not remove) the element at the top of the stack.
22+
Raise Empty exception if the stack is empty.
23+
"""
24+
if self.is_empty():
25+
raise ('Stack is empty!')
26+
return self._data[-1] # the last item in the list
27+
28+
def pop(self):
29+
""" Remove and return the element from the top of the stack (i.e., LIFO)."""
30+
if self.is_empty():
31+
raise ('Stack is empty!')
32+
return self._data.pop()
33+
34+
35+
36+
37+
38+
39+
40+
41+
42+

‎LIFO.pyc‎

1.85 KB
Binary file not shown.

‎LinkedQueue.py‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
# -*- coding: utf-8 -*-
2+
class LinedQueue:
3+
""" FIFO queue implementation using a singly linked list for storage. """
4+
#-------------------------- nested Node class --------------------------
5+
class _Node:
6+
""" Lightweight, nonpublic class for storing a singly linked node. """
7+
__slots__ = '_element', '_next' # streamline memory usage
8+
9+
def __init__(self, element, next): # initialize node’s fields
10+
self._element = element # reference to user’s element
11+
self._next = next # reference to next node
12+
13+
#------------------------------- Queue methods -------------------------------
14+
def __init__(self):
15+
""" Create an empty stack. """
16+
self._head = None # reference to the head node
17+
self._tail = None
18+
self._size = 0
19+
20+
def __len__(self):
21+
""" Return the number of elements in the Queue. """
22+
return self._size
23+
24+
def is_empty(self):
25+
""" Return True if the queue is empty. """
26+
return self._size == 0
27+
28+
def first(self):
29+
""" Return (but do not remove) the element at the front of queue.
30+
Raise Empty exception if the Queue is empty. """
31+
32+
if self.is_empty():
33+
raise ("Queue is empty")
34+
return self._head._element
35+
36+
def dequeue(self):
37+
""" Remove and return the first element of the queue (i.e., FIFO)."""
38+
if self.is_empty():
39+
raise ("Queue is empty.")
40+
answer = self._head._element
41+
self._head = self._head._next
42+
self.size -= 1
43+
if self.is_empty(): # special case as queue is empty
44+
self._tail = None # removed head had been the tail
45+
return answer
46+
47+
def enqueue(self, e):
48+
""" Add an element to the back of queue. """
49+
newest = self._Node(e, None) # node will be new tail node
50+
if self.is_empty():
51+
self._head = newest
52+
else:
53+
self._tail._next = newest
54+
self._tail = newest
55+
self._size += 1
56+
57+
58+
59+
60+
61+

‎LinkedStack.py‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
# -*- coding: utf-8 -*-
2+
class LinkedStack(object):
3+
""" LIFO Stack implementation using a singly linked list for storage. """
4+
#-------------------------- nested Node class --------------------------
5+
class _Node:
6+
""" Lightweight, nonpublic class for storing a singly linked node. """
7+
__slots__ = '_element', '_next' # streamline memory usage
8+
9+
def __init__(self, element, next): # initialize node’s fields
10+
self._element = element # reference to user’s element
11+
self._next = next # reference to next node
12+
13+
#------------------------------- stack methods -------------------------------
14+
def __init__(self):
15+
""" Create an empty stack. """
16+
self._head = None # reference to the head node
17+
self._size = 0
18+
19+
def __len__(self):
20+
""" Return the number of elements in the stack. """
21+
return self._size
22+
23+
def is_empty(self):
24+
""" Return True if the stack is empty. """
25+
return self._size == 0
26+
27+
def push(self, e):
28+
""" Add element e to the top of the stack. """
29+
self._head = self._Node(e, self._head) # create and link a new node
30+
self.size += 1
31+
32+
def top(self):
33+
""" Return (but do not remove) the element at the top of the stack.
34+
Raise Empty exception if the stack is empty. """
35+
36+
if self.is_empty():
37+
raise ("Stack is empty")
38+
return self._head._element
39+
40+
def pop(self):
41+
""" Remove and return the element from the top of the stack (i.e., LIFO). """
42+
if self.is_empty():
43+
raise ("Stack is empty")
44+
answer = self._head._element
45+
self._head = self._head._next # bypass the former top node
46+
self.size -= 1
47+
return answer
48+
49+
50+
51+
52+
53+
54+
55+
56+
57+
58+
59+

‎html_tag_match.py‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
# -*- coding: utf-8 -*-
2+
from ArrayStack import ArrayStack
3+
def html_Tag_match(html):
4+
""" Return True if all HTML tags are properly match; False otherwise."""
5+
S = ArrayStack()
6+
j = html.find('<') # find first ’<’ character (if any)
7+
while j != -1:
8+
k = html.find('>', j+1) # find next ’>’ character
9+
if k == -1:
10+
return False # invalid tag
11+
tag = html[j+1:k] # strip away < >
12+
if not tag.startswith('/'): # this is opening tag
13+
S.push(tag)
14+
else: # this is closing tag
15+
if S.is_empty():
16+
return False # nothing to match with
17+
if tag[1:] != S.pop():
18+
return False # mismatched delimiter
19+
j = html.find('<', k+1) # find next ’<’ character (if any)
20+
21+
return S.is_empty() # were all opening tags matched?

‎parentheses_match.py‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
from ArrayStack import ArrayStack
2+
def parentheses_match(expr):
3+
""" Return True if all delimiters are properly match; False otherwise."""
4+
left = '({[' # opening delimiters
5+
right = ')}]' # respective closing delims
6+
7+
S = ArrayStack()
8+
for c in expr:
9+
if c in left:
10+
S.push(c) # push left delimiter on stack
11+
elif c in right:
12+
if S.is_empty(): # nothing to match with
13+
return False
14+
if right.index(c) != left.index(S.pop()):
15+
return False # mismatched
16+
return S.is_empty() # were all symbols matched?
17+

0 commit comments

Comments
 (0)