PIC 10b Fall 2000 HW #4

Homework FAQ.

Solution Set.

Due date: Nov. 14. Lecture 2's due time is:  8:00pm 
=========         Lecture 1's due time is:  10pm.

Reading Assignment: Reading in Sedgewick. Finish Ch4, 5.1, 5.2 Savitch Ch12
===================
        
Files to submit:   pic10bhw4file1.h   -contains Stack class interface
=================                 
                   pic10bhw4file2.cpp -contains Stack class implementation   
                   pic10bhw4file3.cpp -driver program.

HW3 Purpose: Write a program to check if an input string uses [,],(,) 
============ in a valid C++ way. The educational purpose is to gain familiarity
             with stacks and templates.

Specification:
==============
Suppose you are trying to tell if a given file is a valid C++ program, but
are only concerned with the symbols [], () ignoring all other symbols. 
Then the string [()][] might occur in some C++ program.
For instance, it could occur in the assignment:
a[myfun()]=a[2].
Similarly ([()][])()[] might occur, for instance, in

myfun2(a[myfun3()],a[2]);
myfun4();
a[4]=5;

The following sequences however would never occur ([)], [[]), [())][]... since
it never happens in C++ that we open a ( and [ and then close the [ with
a ] before we close the ( with a ). Also in C++ our brackets and parentheses 
always match. Your job on this assignment is to write a Stack class
with templates and then use the Stack class in your driver program
to check if a user supplied input uses [], () in a legal C++ way.
The template for your Stack class should look like:

template <class Item>

Your Stack class should support the following member functions:

Stack(int s); //constructor creates a stack whose array has s many Item's.

~Stack(); //destructor frees up memory used by Stack's array.

void push(Item i); // pushes the Item onto the top of the Stack.

Item pop(); // pops one Item from the Stack. 

Item peek(); // returns the tops Item on the Stack but does not delete
             // delete it from the stack.

bool empty() const; //returns true if Stack empty.

bool full() const; //returns true if Stack full.



The private data for the Stack class should be:

int top; // array index of top of Stack.

int maxSize; // how many elements the Stack's array can hold.

Item *array; // where Items stored in Stack.

Your driver program should have at least two auxiliary functions:

int GetInput(char input[]); //get a string of less than 256 characters
                          //from the user and stores them in input. 
                          //the int returned how many characters
                          //till the first carriage return

bool CheckValid(const char input[], int size); //checks if the characters
                         // in the array input use () and [] in a legitimate
                         // C++ way. The length of input is size.


Point Breakdown for HW4
=======================
If the submit program didn't collect your file
because you misnamed it or you did not follow
the required formatting instructions in the syllabus
you will get a 0 without an opportunity for a regrade.

If your driver program doesn't test something as described above, 
then you won't receive credit for it.

How well your code is commented.........1pt.
Stack class has interface  
      as described......................1pt.
Stack implements interface correctly....2pt.
Driver program has two auxiliary
functions  as described.................1pt.
GetInput works correctly................1pt.
CheckValid works correctly..............1pt.
Program runs correctly..................1pt.
============================================
Total...................................8pts


Bonus (2pts): Will discuss bonus in my office Wednesday Nov. 8. at 2pm. 
              Your job is to write programs for 4.48 and 4.52 in Sedgewick.
              The interface should be put in a file:

              pic10bhw4file4.h

              The implementation in a file:

              pic10bhw4file5.cpp

              and the driver in the file: 

              pic10bhw4file6.cpp