<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 cf. pp. 60 McDowell, 6th Ed. What you Need to Know, Core data Structures, Algorithms, and Concepts
| Data Structures | Algorithms | Concepts  |
| 
Step1:  cf. 3 Stacks and Queues, Cracking the Coding Interview, 6th Ed., McDowell, stack uses LIFO - as in a stack of dinner plates, the most recent item added to the stack is the 1st item to be removed.
Step2:  cf. 3.6. Simple Balanced Parentheses
Step3:  Linked List
Advantages over arrays, 1. dynamic size 2. ease of insertion/deletion
Drawbacks; 1) random access not allowed, access elements sequentially, 2) extra memory space for pointer
<ASSISTANT_TASK:>
Python Code:
class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    
    def push(self, item):
        self.items.append(item)
        
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[len(self.items)-1]
    
    def size(self):
        return len(self.items)
s=Stack()
print(s.isEmpty())
s.push(4)
s.push('dog')
print(s.peek())
s.push(True)
print(s.size())
print(s.isEmpty())
s.push(8.4)
print(s.items)
print(s.pop())
print(s.pop())
print(s.size())
Explanation: cf. pp. 60 McDowell, 6th Ed. What you Need to Know, Core data Structures, Algorithms, and Concepts
| Data Structures | Algorithms | Concepts  |
| :-- | -- | :-- |
| Linked Lists | Breadth-First Search | Bit Manipulation  | 
| Trees, Tries, & Graphs | Depth-First Search | Memory (Stack vs. Heap)   |
| Stacks & Queues | Binary Search | Recursion |
| Heaps | Merge Sort | Dynamic Programming   |
| Vectors/ArrayLists | QuickSort | Big O Time & Space  |
| Hash Tables  | | |
http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementingaStackinPython.html
End of explanation
class Queue:
    def __init__(self):
        self.items = []
        
    def add(self,item):
        self.items.append( item )
    
    def remove(self):
        self.items.remove( self.items[0])
        
    def peek(self):
        return self.items[0]
    
    def isEmpty(self):
        return self.items == []
    
Explanation: cf. 3 Stacks and Queues, Cracking the Coding Interview, 6th Ed., McDowell, stack uses LIFO - as in a stack of dinner plates, the most recent item added to the stack is the 1st item to be removed.
End of explanation
def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0 
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index = index + 1
    
    if balanced and s.isEmpty():
        return True
    else:
        return False
    
            
print(parChecker('((()))'))
print(parChecker('(()'))
def parChekcer(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()
                if not matches(top,symbol):
                    balanced = False
        index = index + 1
    if balanced and s.isEmpty():
        return True
    else:
        return False
    
def matches(open,close):
    opens = "([{"
    closers = ")]}"
    return opens.index(open) == closers.index(close)
print(parChecker('{{([][])}()}') )
print(parChecker('[{()]'))
def divideBy2(decNumber):
    remstack = Stack()
    
    while decNumber >0:
        rem = decNumber % 2
        remstack.push(rem)
        decNumber = decNumber // 2
        
    binString = ""
    while not remstack.isEmpty():
        binString = binString + str(remstack.pop())
        
    return binString
print(divideBy2(42))
divideBy2(233)
def baseConverter(decNumber,base):
    digits = "0123456789ABCDEF"
    
    remstack=Stack()
    while decNumber >0:
        rem = decNumber % base
        remstack.push(rem)
        decNumber = decNumber // base
    
    newString = ""
    while not remstack.isEmpty():
        newString = newString + digits[remstack.pop()]
        
    return newString
print(baseConverter(25,2))
print(baseConverter(25,16))
print(baseConverter(25,8))
print(baseConverter(256,16))
print(baseConverter(26,26))
Explanation: cf. 3.6. Simple Balanced Parentheses
End of explanation
# Node class
class Node:
    # Function to initialize the node object
    def __init__(self,data):
        self.data = data # Assign data
        self.next= None  # Initialize 
                         # next as null
# Linked List class
class LinkedList:
    
    # Function to initialize the Linked
    # List object
    def __init__(self):
        self.head = None
                
    # This function prints contents of linked list
    # starting from head
    # traversal of a linked list 
    def printList(self):        
        temp = self.head
        while (temp):
            print temp.data
            temp = temp.next
# Start with the empty list
llist = LinkedList()
llist.head = Node(1)
second = Node(2)
third = Node(3)
llist.head.next = second; # Link 1st node with second
second.next = third
llist.printList()
class Node:
    def __init__(self,val):
        self.val = val
        self.next = None
        
class LinkedList:
    def __init__(self,val=None):
        if val is None:
            self.head = None
        else:
            self.head = Node(val)
    
    def insertEnd(self,val):
        temp = self.head
        while(temp.next): # check if temp has a next
            temp = temp.next # keep traversing
        temp.next = Node(val)
            
    def printList(self):
        temp = self.head
        while (temp): # stop when temp is a None, which could happen with next in Node
            print temp.val 
            temp = temp.next
            
llist = LinkedList(1)
llist.printList()
llist.insertEnd(2)
llist.printList()
llist.insertEnd(4)
llist.printList()
llist.insertEnd(2)
llist.printList()
llist.insertEnd(6)
llist.printList()
llist.insertEnd(7)
llist.printList()
Explanation: Linked List
Advantages over arrays, 1. dynamic size 2. ease of insertion/deletion
Drawbacks; 1) random access not allowed, access elements sequentially, 2) extra memory space for pointer
End of explanation
<END_TASK>