CS240 - Stacks and Queues Lab

Stacks and Queues Lab

Objectives

The goal of this lab is to gain experience with stack and queue data structures and their applications.

Introduction

In this lab, you will use stacks and queues to solve problems. To facilitate development, we provide the following ADT implementations for you to use:

Download all of these files to a working directory and use them to solve the problems in this lab. Here is the documentation for these classes:

    class ArrayStack
    |
    |  Implements a Last-In, First-Out (LIFO) data structure.
    |
    |      push(x)        Adds element x at the top of the stack
    |      pop()          Removes and returns element at top of the stack
    |      top()          Returns (but doesn't remove) element at top of stack
    |      is_empty()     Returns True if the stack is empty
    |      __len__()      Returns the number of items in the stack
    |

    class ArrayQueue
    |
    |  Implements a First-In, First-Out (FIFO) data structure.
    |
    |      enqueue(x)     Adds element x at the back of the queue
    |      dequeue()      Removes and returns element at front of the queue
    |      first()        Returns (but doesn't remove) element at front of queue
    |      is_empty()     Returns True if the queue is empty
    |      __len__()      Returns the number of items in the queue
    |

You should create a new Python file to contain the code you write in this lab. I suggest calling it "stack_lab.py" for now. Remember that you will need to import the above classes in your new code module before you can use them. Example:

    from t_array import Array
    from stack import ArrayStack
    from queue import ArrayQueue

At some point, you may wish to disable the turtle graphics to avoid the slowdown during testing. You can use the following line to do this:

    Array.visible = False

Finally, here are two Python string methods that you may find useful for this lab:

    str.isalpha()

        Returns True if all characters are alphabetic and there is at least one
        character, False otherwise.

    str.isnumeric()

        Returns True if all characters in the string are numeric characters and
        there is at least one character, False otherwise

Part 1 - Palindromes

Use a stack and queue to implement a more powerful version of the is_palindrome() function from Midterm 1. As a reminder, this function implements simple palindome verification. Here is the signature and docstring for that function:

    def is_palindrome(text):
        """ Return True if text is a palindrome, False otherwise.  A palindrome is a string
            that is identical to itself when reversed. For example, "madam", "dad", and
            "abba" are palindromes.  Note: the empty string is a palindrome, as is every
            string of length one.
        """

Pure iteration-based solutions to this problem require either A) 2n accesses (to reverse the string then compare every letter) or B) non-sequential access (directly comparing items from the beginning and end of the list). However, observe that if you add a certain sequence of elements to both a stack and a queue, you can then retrieve them from those data structures in opposite orders very easily due to the nature of the two structures. Exploit this fact to implement is_palindrome with exactly n sequential accesses to text, where n = len(text).

For this lab, you should make the function more flexible than the version you wrote for the midterm. Your lab solution should ignore whitespace and punctuation, and all comparisons should be case-insensitive. Include some tests in a main() function. Examples of valid palindromes:

""
"a"
"aa"
"aaa"
"aba"
"abba"
"Taco cat"
"Madam, I'm Adam"
"A man, a plan, a canal: Panama"
"Doc, note: I dissent. A fast never prevents a fatness. I diet on cod."

Part 2 - Postfix Evaluation

On Friday (9/26), we discussed postfix notation (sometimes called "Reverse Polish Notation" or "RPN") for explicitly specifying the operation order of a mathematical expression. Here is some examples of normal (infix) expressions followed by their postfix equivalents:

"1 + 2" == "1 2 +"
"3 - 1" == "3 1 -"
"2 * 3" == "2 3 *"
"3 + (4 * 5)" == "4 5 * 3 +"
"5 + ((1 + 2) * 4) - 3" == "5 1 2 + 4 * + 3 -"

We also discussed an algorithm for evaluating postfix expressions using a stack:

for each token in expression
1. if token is a number
  1. stack.push(token)
2. if token is an operator
  1. op2 = stack.pop()
  2. op1 = stack.pop()
  3. stack.push(op1 <op> op2)
return stack.pop()

Implement this algorithm by writing a function with the following signature:

    def eval_postfix(expr):
        """ Return the value of evaluating 'expr' as a postfix expression. All operands
            should be integer numbers, and all standard arithmetic operators (+, -, *, /)
            are supported. All operands and operators should be separated in 'expr' by a
            single space. If the the expression is invalid, the function should raise an
            EvalError.
        """

You may use the following definition for EvalError:

    class EvalError(Exception):
        pass

Include some tests in a main() function. Examples:

"1 2 +" = 3
"15 8 -" = 7
"2 3 *" = 6
"4 5 * 3 +" = 23
"5 1 2 + 4 * + 3 -" = 14

Testing (Optional)

Write some unit tests for the functions you wrote in this lab using the Python unittest module, as we practiced in a previous lab. Try injecting flaws into your implementations to make sure that your tests catch the flaws.

Alternatively, write your initial unit tests before writing your functions, iteratively fixing your code and your tests until your code passes all the tests. This is called test-driven development.

Submission

This lab will not be graded so there is nothing to submit. Make sure you keep a copy of your code for future reference. There may be a future homework based on this lab. If you would like to discuss your solution or any problems you encounter while working on this lab, please come to office hours or make an appointment.

CS 240