$ mkdir ~/cs170/labs/lab21 $ cd ~/cs170/labs/lab21
After lab on Monday, you saw how we can use a queue to force our program to determine whether a path exists through a maze. However, we were doing really, really simple mazes. Today, I want to show you a hand trace of a slightly more complicated maze, so you can see how the algorithm works.
While it might sound like a dull activity, but determining if a string contains a set of balanced parentheses is a very important job. Emacs does this for you, so does Mathematica and even Microsoft Office. We need something like this in Emacs or Mathematica to help catch our silly errors, like forgetting to close a parenthesis on a nested function call, for example.
While it might seem like counting is the most straight forward approach to this, it is not a complete solution. The better solution is to use a stack to determine whether the parentheses are balanced or not.
In a file called parens.py, write a function called
is_balanced(a_string), which takes a single string as a
parameter. This function should return True if the
parentheses in the string are balanced, and False if they are
not. Your function will need to use a Stack to accomplish this, so
make sure you copy your stack class from last lab to this directory:
$ cd ~/cs170/labs/lab21 $ cp ../lab19/stack.py . $ cp ../lab19/linked_list.py .
>>> print(is_balanced("()"))
True
>>> print(is_balanced("(")))
False
>>> print(is_balanced(")("))
False
>>> print(is_balanced("(a)"))
True
>>> print(is_balanced("((()(((())))))"))
True
The algorithm for this is straight forward: When you see an open parenthesis, push it onto the stack. When you see a closing parenthesis, pop the stack. If you reach the end of the string and the stack is empty, you know the parenthesis are balanced. If you ever try to pop from an empty stack, or you reach the end of the string and the stack is not empty, you know the parentheses are not balanced.
Of course, we can use more than just traditional parentheses in
order to break up some mathematical equation. We commonly use
square brackets ("["), and sometimes even curly braces ("{") as
well. Write a function is_balanced_multi, which
accounts for all three of these tokens.
We have already learned about Radix Sort this semester. As a matter of fact, many of you felt it was one of the more straight forward sorting algorithms you have implemented so far. The technical term for the version of radix sort you implemented earlier in the semester was most significant digit (MSD) radix sort. This is because we started sorting by the most significant digit, and we were able to accomplish this recursively.
version of radix sort called least significant digit () radix sort. In this sort, we begin at the least significant digit (which is always the ones place), and continue from there. This sort can be done in a loop, using queues.
First, copy your queue definition from last lab into this directory
$ cd ~/cs170/labs/lab21 $ cp ../lab20/queue.py . $ cp ../lab20/linked_list.py .
Create a function radix_sort(a_list),
which takes a list of integers. This function should return a
sorted copy of the input list, using the LSD radix sort algorithm.
In radix sort, all of the integers are placed into one of several queues, always in the order they are encountered. The queue they are placed in is based on the digits place being examined. You will start from the least significant bit (the right most digit in the number), and place it into the appropriate queue based on that number. For example, for the first iteration of radix sort, the number 64 would be placed in a queue for the the digit '4', while the number 101 would be placed in the queue for the digit '1'.
After you have enqueued all of the items from the original list into the queues, you sequentially dequeue all of the queues in increasing order back into the main list. You will dequeue all of the numbers from the '0' queue into a list, then all of the numbers from the '1' queue, etc. You then repeat this process for the next digit in the numbers, until you run out of digits. The resulting list will be a sorted copy of the list.
>>> print(radix_sort([1, 2030, 122, 2, 1203, 333])) [1, 2, 122, 333, 1203, 2030]
For radix sort, you will want to create a list of 10 queues, one for each digit. All of these queues will start off empty. You could use a dictionary, but since you know the strings you have represent integers your sort will be faster if you use just a list.
If we were feeling a little "cheaty," we could convert each
of our numbers into a string to get a particular digit.
However, there is an easier way to do this. If you mod
(%) a number by 10, you will get the value in
the ones place of the number. And I can shift all of the
digits of a number to the left by dividing by a power of 10.
If we number the digits of a number, with 0 being the least significant digit, we can figure out the place value using the following equation:
\[ \left(\frac{number}{10 ^ {digit\_place}}\right) \mod 10 \]When you have put all of the values into the queues, you need to iterate over your list of queues, dequeueing them until they are empty. You will place the dequeued values into a list, so that you can process the next digits of them.
Just because this function uses a queue, it doesn't mean we cannot do this recursively. Rewrite the above function using recursion, instead of a loop.
When you have finished, create a tar file of your lab21 directory. To create a tar file, execute the
following commands:
cd ~/cs170/labs tar czvf lab21.tgz lab21/
To submit your activity, go
to inquire.roanoke.edu. You
should see an available assignment called Lab Assignment
21. Make sure you include a header
listing the authors of the file.
