CSCI 132 Data Structures--Spring 2014

    Home | | Syllabus | | Assignments | | Lecture Notes

    Laboratory 3
    Due at the beginning of class, Wednesday, 2/12

    In today's lab you will practice using the Stack class that we implemented in class. You will also have a chance to make an Extended_stack class that adds to the functionality of the Stack class.

    The code that was presented in class and in the book is available in the directory:

      ~csci132/labs/lab3

    Start the lab as follows:

    • Copy the code for lab3 into your labs folder by typing:
        cp -r ~csci132/labs/lab3 labs/.
    • Change directories into your new lab3 directory by typing:
        cd labs/lab3
    • Type ls to verify that the lab3 directory contains the following files:
      • stack.h
      • stack.cc
      • primes.cc
      • extStackTest.cc
    • Start up an emacs window and open the file, primes.cc.

    1. Prime Factors

    Write a program that uses a Stack object to read in an integer and print out all its prime divisors in descending order. You should use the file, primes.cc, which has some declarations made for you. Keep in mind the following:
    • The smallest divisor greater than 1 of any integer is guaranteed to be a prime. (You can check if a factor evenly divides a number using the MOD operator (%)).
    • Once a factor is found, you need only find the divisors of your number/factor.
    • A given factor may divide the number more than once.
    • When a factor is found, push it onto the stack
    • After all factors have been found, print them in reverse order by accessing the stack. (Note: you will empty the stack in the process of printing out the values).
    You have been given several variables to start you off:
    • number is used to read in the number to be factored. The value of number should not change during the program.
    • factor should be used to hold the value of each potential factor as it is tested.
    • result should be used to hold the current number to be tested for the next prime factor, after division by factor . (I.e. result = result/factor )
    • primeStack is a stack to store each prime factor as it is found. Use error checking when you push a factor onto the stack.

    Sample output
    A sample run should look like the following: 

      Enter an integer: 
2100
The prime factors of 2100 are 
7 5 5 3 2 2

    Sample 2: 

      Enter an integer: 
17
The prime factors of 17 are 
17

    2. An Extended_stack class.

    In lecture we learned how to make a derived class from a base class. Here we will make a derived class called Extended_stack from the Stack class. The Extended_stack class will have four new methods: 

      void clear(void);
//Clear the stack so that it becomes an empty stack

bool full(void) const;
//Return true if stack is full

int size(void) const;
//Return the size of the stack.

int sum(void) const;
//Return the sum of all entries in the stack.
//If there are no entries in the stack, return zero.

    • Create a new file, called ext_stack.h. Write the specification for the class Extended_stack, which is derived from the Stack class, and has the above 4 public functions. Remember to include the file "stack.h" and to use the class declaration:
        class Extended_stack : public Stack {
        //class specification here
        };
    • Create a new file, called ext_stack.cc. In it, write the implementation of the four functions above (three of them are very short). Remember to include the "ext_stack.h" file.
    • Test your new class by compiling and running the extStackTest.cc file. Compile your program with the following command:
        g++ -g -Wall extStackTest.cc stack.cc ext_stack.cc -o extStackTest
      Note that there are 3 source files to compile.
    • Run extStackTest.

    Sample Output
    Your output should look as follows: 

      Pushing 0
Pushing 1
Pushing 2
Pushing 3
Pushing 4
Pushing 5
Pushing 6
Pushing 7
Pushing 8
Pushing 9

Full method works.

Size of stack is 10. size() method works.

Sum of stack entries is 45. sum() method works.

Clearing stack. 
Clear function works.

Testing sum() for empty stack.
Correct value of 0 returned.

    What To Turn In.

    • A printout of the primes.cc file
    • A printout of the ext_stack.h file
    • A printout of the ext_stack.cc file
    • Use the submit function to turn in the soft copy of each file. Type:
        ~csci132/bin/submit csci132 lab3

    Be sure that the file prologue for each file contains your name, course, lecture section, date and purpose of the program or a description of the contents of the file (e.g. specification of the Extended_stack class).

    Reminder.
    Be sure to save a copy of each file in your labs directory. It is your responsibility to keep the copies of all programs written for this course until your graded assignment is returned.

    Home | | Syllabus | | Assignments | | Lecture Notes