The goal of this assignment is to reinforce using stacks in C++ programs. Specif
ID: 3862227 • Letter: T
Question
The goal of this assignment is to reinforce using stacks in C++ programs. Specifically, the assignment is to do problem 17 on page 392 of the text. Use the STL stack class, sequence4.h, and sequence_exam4.cpp.
File for sequence4.h
http://pastebin.com/qFkP33cs
File for sequence_exam4.cpp
http://pastebin.com/PmmDz8iH
Promblem 17 is as follows
Here's a new idea for implementing the sequence class from section 3.2. Instead of the items being stored on a linked list they will be stored using two stacks as private member variables with the following:
1. The bottom of the first stack is the beginning of the sequence.
2. The elements of the sequence continue up to the top of the first stack.
3. The next element of the sequence is then the top of the second stack.
4. And the elements of the sequence is then the top of the sequence then continues down to the bottom of the second sequence (which is the end of the sequence)
5. If there is a current element, then that element is at the top of the first stack.
You should delete the CAPACITY constant, but don't change any of the prototypes for any of the public member functions.
All of the public memeber functions should take constant time with one exception. Which one takes linear time?
NOTE: If you use a correctly written stack class for your two private memeber variables, then you do not need to write you own assignment operator, copy constructor or destructor. The reason for this is that C++ provides automatic versions of all three of these items, and the automatic versions call the respective functions for each of the member variables of the new class.
Explanation / Answer
Here is the updated file for sequenc4.h. With templates, we get linker issues when we define the functions in a separate .cpp file Thats why I have put in .h file itelf. All test cases from sequence4_exam.cpp have passed . You only need the sequence4.h file to test it. Comments are in the code. Please do rate the answer if it helped . Thanks
------------------------------------------------------------
sequence4.h
// FILE: sequence4.h
// CLASS PROVIDED: sequence
// TYPEDEFS and MEMBER CONSTANTS for the sequence class:
// typedef ____ size_type
// sequence::size_type is the data type of any variable that keeps track of
// how many items are in a sequence.
//
// CONSTRUCTOR for the sequence class:
// sequence( )
// Postcondition: The sequence has been initialized as an empty sequence.
//
// MODIFICATION MEMBER FUNCTIONS for the sequence class:
// void start( )
// Postcondition: The first item on the sequence becomes the current item
// (but if the sequence is empty, then there is no current item).
//
// void advance( )
// Precondition: is_item returns true.
// Postcondition: If the current item was already the last item in the
// sequence, then there is no longer any current item. Otherwise, the new
// current item is the item immediately after the original current item.
//
// void insert(const value_type& entry)
// Postcondition: A new copy of entry has been inserted in the sequence
// before the current item. If there was no current item, then the new entry
// has been inserted at the front of the sequence. In either case, the newly
// inserted item is now the current item of the sequence.
//
// void attach(const value_type& entry)
// Postcondition: A new copy of entry has been inserted in the sequence after
// the current item. If there was no current item, then the new entry has
// been attached to the end of the sequence. In either case, the newly
// inserted item is now the current item of the sequence.
//
// void remove_current( )
// Precondition: is_item returns true.
// Postcondition: The current item has been removed from the sequence, and the
// item after this (if there is one) is now the new current item.
//
// CONSTANT MEMBER FUNCTIONS for the sequence class:
// size_type size( ) const
// Postcondition: The return value is the number of items in the sequence.
//
// bool is_item( ) const
// Postcondition: A true return value indicates that there is a valid
// "current" item that may be retrieved by activating the current
// member function (listed below). A false return value indicates that
// there is no valid current item.
//
// value_type current( ) const
// Precondition: is_item( ) returns true.
// Postcondition: The item returned is the current item in the sequence.
//
// VALUE SEMANTICS for the sequence class:
// Assignments and the copy constructor may be used with sequence objects.
#ifndef _STACK_SEQUENCE_H_
#define _STACK_SAVITCH_SEQUENCE_H_
#include <cstdlib> // Provides size_t
#include <stack>
namespace stack_sequence_4
{
template <typename T>
class sequence
{
public:
// TYPEDEFS and MEMBER CONSTANTS
typedef std::size_t size_type;
// CONSTRUCTOR
sequence( );
// MODIFICATION MEMBER FUNCTIONS
void start( );
void advance( );
void insert(const T& entry);
void attach(const T& entry);
void remove_current( );
// CONSTANT MEMBER FUNCTIONS
size_type size( ) const;
bool is_item( ) const;
T current( ) const;
private:
std::stack<T> first;
std::stack<T> second;
};
template <typename T>
sequence<T>::sequence()
{
//initialize with empty stacks as no data is there
first=std::stack<T>();
second=std::stack<T>();
}
template <typename T>
sequence<T>::size_type sequence<T>::size() const
{
//at any point of time, some are on first and some are on 2nd,
//so the total of these stack size will be the number of elements
//in sequence
return first.size()+second.size();
}
template <typename T>
void sequence<T>::start()
{
//when we start we want any elements we have in first stack to all
//go into second and just put one element(if exists) from second to first stack
while(first.size()>0)
{
second.push(first.top());
first.pop();
}
if(!second.empty()) //if there is atleast one element, get that, its the 1st of sequence
{
first.push(second.top());
second.pop();
}
}
template <typename T>
T sequence<T>::current() const
{
//always first stack's top gives the current element
return first.top();
}
template <typename T>
bool sequence<T>::is_item() const
{
//since first stack's top shows current element, return whether there is an item in
//first stack or not
return !first.empty();
}
template <typename T>
void sequence<T>::remove_current()
{
if(!first.empty()) //pop out the current element if it exists
first.pop();
if(!second.empty()) //now we need to get next element from the second stack, check if its empty
{
first.push(second.top());
second.pop();
}
else //second is empty , so no more next element, dump all element from first onto second . So
//we now dont have any current element since we are clearing out first
{
while(first.size()>0)
{
second.push(first.top());
first.pop();
}
}
}
template <typename T>
void sequence<T>::insert(const T &entry)
{
T new_copy=entry; //make a copy of the entry to be inserted before current
if(!first.empty()) //if there any current item, first get it out of first and put it on second
{
second.push(first.top());
first.pop();
}
//now we put out new entry and that becomes current since its on top
first.push(new_copy);
}
template <typename T>
void sequence<T>::attach(const T&entry)
{
T new_copy=entry; //make a copy of the entry
first.push(new_copy); //simply push onto stack first, and since its on top , it will be current item
}
template <typename T>
void sequence<T>::advance()
{
//the next item (if any) to current is always on second stack
if(!second.empty()) //is there a next item?
{
first.push(second.top()); //just get the next item and push it on first
second.pop();
}
else //if next item is not there, we should no longer have a current item , so dump everythign from first onto second
{
while(first.size()>0)
{
second.push(first.top());
first.pop();
}
}
}
}
#endif
output of program
Running tests for Chapter 3 sequence Class
START OF TEST 1:
Testing insert, attach, and the constant member functions (50 points).
Starting with an empty sequence.
Testing that size() returns 0 ... Passed.
Testing that is_item() returns false ... Passed.
I'll call start() and look at the items one more time...
All tests passed for this sequence.
I am now using attach to put 10 into an empty sequence.
Testing that size() returns 1 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
I am now using insert to put 10 into an empty sequence.
Testing that size() returns 1 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
I am now using attach to put 10,20,30 in an empty sequence.
Then I move the cursor to the start and insert 5.
Testing that size() returns 4 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
I am now using attach to put 10,20,30 in an empty sequence.
Then I move the cursor to the start, advance once, and insert 15.
Testing that size() returns 4 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [1] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
I am now using attach to put 10,20,30 in an empty sequence.
Then I move the cursor to the start and attach 15 after the 10.
Testing that size() returns 4 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [1] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
All tests of this first function have been passed.
Test 1 got 50 points out of a possible 50.
END OF TEST 1.
START OF TEST 2:
Testing situations where the cursor goes off the sequence (25 points).
Using attach to put 20 and 30 in the sequence, and then calling
advance, so that is_item should return false ... passed.
Inserting 10, which should go at the sequence's front.
Then calling advance three times to run cursor off the sequence ... passed.
All tests of this second function have been passed.
Test 2 got 25 points out of a possible 25.
END OF TEST 2.
START OF TEST 3:
Testing remove_current (25 points).
Using attach to build a sequence with 10,30.
Insert a 20 before the 30, so entire sequence is 10,20,30.
Testing that size() returns 3 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [1] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
Remove the 20, so entire sequence is now 10,30.
Testing that size() returns 2 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [1] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
Remove the 30, so entire sequence is now just 10 with no cursor.
Testing that size() returns 1 ... Passed.
Testing that is_item() returns false ... Passed.
I'll call start() and look at the items one more time...
All tests passed for this sequence.
Set the cursor to the start and remove the 10.
Testing that size() returns 0 ... Passed.
Testing that is_item() returns false ... Passed.
I'll call start() and look at the items one more time...
All tests passed for this sequence.
Using attach to build another sequence with 10,30.
Insert a 20 before the 30, so entire sequence is 10,20,30.
Testing that size() returns 3 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [1] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
Remove the 20, so entire sequence is now 10,30.
Testing that size() returns 2 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [1] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
Set the cursor to the start and remove the 10,
so the sequence should now contain just 30.
Testing that size() returns 1 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
Remove the 30 from the sequence, resulting in an empty sequence.
Testing that size() returns 0 ... Passed.
Testing that is_item() returns false ... Passed.
I'll call start() and look at the items one more time...
All tests passed for this sequence.
Build a new sequence by inserting 30, 10, 20 (so the sequence
is 20, then 10, then 30). Then remove the 20.
Testing that size() returns 2 ... Passed.
Testing that is_item() returns true ... Passed.
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
I'll call start() and look at the items one more time...
The cursor should be at item [0] of the sequence
(counting the first item as [0]). I will advance the cursor
to the end of the sequence, checking that each item is correct...Passed.
All tests passed for this sequence.
All tests of this third function have been passed.
Test 3 got 25 points out of a possible 25.
END OF TEST 3.
If you submit the Chapter 3 sequence to Dora now, you will have
100 points out of the 100 points from this test program.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.