CSC148H - Assignment 1

Preamble

This assignment is due 5 October 2009 at 10:00am. No late assignments will be accepted.
Solutions should be clearly written, well documented, and conform to the PEP 8 style guide.
To submit the assignment, log in to the Mark Us webpage. You should be able to submit the required files. Your user name and password is the same as the CDF user name and password. Make sure you can log in as soon as possible, especially if you were late to enroll in the course. You may submit files as often as you like; the most recent version (submitted before Oct. 5, 10:00am) will be the one graded. Frequent submissions are encouraged.
For parts 2 and 3, you are free to use the stack and queue implementations written in lecture (although you will have to submit them with the rest of your code). For part 1, you may NOT use linkedlist.py from lecture.

Part 1 (20%)

For this part you will implement the Stack and Queue ADTs discussed in lecture using a singly linked list instead of a Python list. Fill in the missing code in llstack.py and llqueue.py. Additionally, we provide node.py which you should use in your implementations and submit, but should not alter. If an operation on either the stack or queue cannot be performed, you should raise an exception with an appropriate error message.
Note that the efficiency of your solution will be taken into account; you should not have to iterate over the entire contents of a linked list to perform any operations. Such solutions will not receive full marks.

Part 2 (35%)

In this part, you will write a function to produce a set of instructions to move numbers from one queues to another using a stack.
There are two queues; A and B. Queue B had the numbers 0, 1, ..., (N-2), (N-1) enqueued into it according to the order given by queue_b_contents. You would like to move the contents of queue B to queue A such that the are enqueued into queue A according to the order given by queue_a_goal (which will be some permutation of queue_b_contents), subject to the following constraints:

You are allowed to dequeue from queue B, but are not allowed to enqueue to queue B.
You are allowed to enqueue from queue A, but are not allowed to dequeue to queue A.
You are only allowed to use a single stack S as temporary storage.

From these constraints, it is clear that there are only three types of operations you can perform:

Move an item from the front of queue B onto the stack. ('QUEUE_B => STACK')
Move an item directly from queue B to queue A. ('QUEUE_B => QUEUE_A')
Move an item from the top of the stack to queue A. ('STACK => QUEUE_A')

Your task is to write a function two_queues_one_stack which takes two lists (queue_a_goal and queue_b_contents, respectively) and returns a sequence of operations to get the desired ordering on queue A, using only the three valid operations, or None if it is not possible. If there are multiple instruction sequences which result in the correct order on queue A, return the shortest one.
two_queues_one_stack should return a list of strings, where each string is one of ['STACK => QUEUE_A', 'QUEUE_B => QUEUE_A', 'QUEUE_B => STACK'].
Consider the following example:
queue_a_goal = [0,1,3,2]
queue_b_contents = [0,1,2,3]
In this case, the following sequence of operations will result in the correct ordering in queue A:
['QUEUE_B => QUEUE_A', 'QUEUE_B => QUEUE_A', 'QUEUE_B => STACK', 'QUEUE_B => QUEUE_A', 'STACK => QUEUE_A']
Initial State:
queueA = []
queueB = [0,1,2,3]
stack = []
'QUEUE_B => QUEUE_A'
queueA = [0]
queueB = [1,2,3]
stack = []
'QUEUE_B => QUEUE_A'
queueA = [0,1]
queueB = [2,3]
stack = []
'QUEUE_B => STACK'
queueA = [0,1]
queueB = [3]
stack = [2]
'QUEUE_B => QUEUE_A'
queueA = [0,1,3]
queueB = []
stack = [2]
'STACK => QUEUE_A'
queueA = [0,1,3,2]
queueB = []
stack = []
So the correct sequence of instructions was ['QUEUE_B => QUEUE_A', 'QUEUE_B => QUEUE_A', 'QUEUE_B => STACK', 'QUEUE_B => QUEUE_A', 'STACK => QUEUE_A'].
Complete the method two_queues_one_stack(queue_a_goal, queue_b_contents) in part2.py.

Part 3 (45%)

As mentioned in lecture, stacks are used by compilers to parse the source code of your programs. For this part, you will be writing a function to parse through a document similiar to HTML, and return it in a more useful form.
A 148 Markup Language (148ML) document constists of opening tags (of the form <TAG>, where TAG, the label, is any non-empty sequence of upper and lower case letters), closing tags (of the form </TAG> where, again, TAG, the label, is any sequence of upper and lower case letters) and words (any sequence of upper and lower case letters). Opening and closing tags must be properly balanced.
You task is to write a function which takes as input the lines of a 148ML file, and outputs a more structured version as a list which contains strings (for words) and lists (for matching tags, and everything in between).
Consider the following example:
This is a document <title> Example </title> done
In this sample document, there is one pair of tags. Since the two title tags match, we will move them and everything between them to their own list, and return the following sequence of strings: ['This','is','a','document',['<title>', 'Example', '</title>'], 'done'].
Now consider this more complex example.
<html>
<head> <title> Example </title> </head>
<body> quiet <CAPSLOCK> LOUD </CAPSLOCK> quiet </body>
</html>
Here, there are 5 pairs of matching tags: html, head, title, body and CAPSLOCK. The head, title, body and CAPSLOCK tags all appear within the html tags, and the title and CAPSLOCK tags appear within the head and body tags, respectively. Converting this to our nested list structure, and we get:
[['<html>', ['<head>', ['<title>', 'Example', '</title>'], '</head>'], ['<body>', 'quiet', ['<CAPSLOCK>', 'LOUD', '</CAPSLOCK>'], 'quiet', '</body>'], '</html>']]
Note that the lists have the same nesting structure as the tags, and that all whitespace has been stripped.
Starter code is provided in parser.py, as well as the second example. If the input document is malformed (words or tag labels which contain non alphabetic characters, unbalanced tags, etc.) you should raise a ParseError exception with an appropriate error message. Solutions which do not use a stack will receive no marks.

What to Submit

For Part 1: llstack.py llqueue.py node.py
For Part 2: part2.py
For Part 3: parser.py
Note that although you are not required to submit tests for your code, you should test them; much of the marking will be done by automatically running your code on a variety of test cases.