Hey guys! I\'ve completed a bit of this assignment and I need some help getting
ID: 3789340 • Letter: H
Question
Hey guys! I've completed a bit of this assignment and I need some help getting the rest! I've completed the main.cpp (driver) file and the stack.h (specification) file and just need some help getting the implementation file (stack.cpp) Any help would be appreciated! I'll provide some guidelines and the code I've got including some input files that will be run through the program!
Here are the guidelines
||||||||||||||||||||||||||||||||||||||||||||||||
This Stack class uses a dynamically allocated one-dimensional array to store data values (integers) that
have been pushed onto the stack object. When the client code attempts to push another integer onto a
full stack, your Push operation should invoke the Resize() function which attempts to double the
capacity of the stack and then add the new data value to the resized stack array. In Resize() a new array
(that holds twice as many integers) is dynamically allocated, data from the old stack array is copied into
the new larger stack array, the old stack array is deallocated, and the new data value is pushed onto the
new array.
It is recommended to create an Empty Framework of function definitions that compiles first –
before adding any code to any function.
Some functions such as the constructor Stack(), destructor ~Stack(), Push() and Pop() are critical
operations that must be functional in order to test other operations ( Size(), Capacity(), Max(), Min(),
etc.).
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
And here is the main.cpp file ( I tried to comment as much as I could)
||||||||||||||||||||||||||||||||||||||||||||||||||||||||
#include
#include
#include
#include
#include "stack.h"
using namespace std;
int main(int argc, char* argv[])
{
ifstream inputs; // Input file for commands
char op; // Hold operation and optional char input
int value; // Value input from file
string comment; // Holds comment from file
Stack* sPtr = NULL; // Will point to TemplateQ object
// Output usage message if one input file name is not provided
if (argc != 2)
{
cout << "Usage: project03 ";
return 1;
}
// Attempt to open input file -- terminate if file does not open
inputs.open(argv[1]);
if (!inputs)
{
cout << "Error - unable to open input file" << endl;
return 1;
}
// Input and echo header comment from file
getline(inputs, comment); // Input and echo the comment appearing in the test file
cout << endl << '#' << comment << endl;
// Process commands from input file
inputs >> op; // Attempt to input first command
while (inputs)
{
switch (op) // Process operation input from file
{
case '#': // Test file comment
getline(inputs, comment); // Input and echo the comment appearing in the test file
cout << '#' << comment << endl;
break;
case 'c': // Parameterized Constructor
inputs >> value;
cout << endl << "Stack(" << value << ")";
try
{
sPtr = new Stack(value); // Attempt to create a stack object with array size value
cout << " -- completed" << endl;
}
catch ( std::bad_alloc )
{
cout << "Failed : Terminating now..." << endl;
return 1;
}
break;
case '+': // Push
inputs >> value;
cout << "Push(" << value << ") -- ";
try
{
sPtr->Push(value);
cout << "completed";
}
catch (StackFull)
{
cout << "Failed Full Stack";
}
catch (...)
{
cout << "operation failed" << endl;
}
cout << endl;
break;
case '-': // Pop
cout << "Pop() -- ";
try
{
sPtr->Pop();
cout << "completed";
}
catch (StackEmpty)
{
cout << "Failed Empty Stack";
}
catch (...)
{
cout << "operation failed" << endl;
}
cout << endl;
break;
case 'f': // IsFull
cout << "IsFull() -- ";
try
{
if (sPtr->IsFull())
cout << "true";
else
cout << "false";
}
catch ( ... )
{
cout << "operation failed";
}
cout << endl;
break;
case 'e': // IsEmpty
cout << "IsEmpty() -- ";
try
{
if (sPtr->IsEmpty())
cout << "true";
else
cout << "false";
}
catch ( ... )
{
cout << "operation failed";
}
cout << endl;
break;
case 'm': // Make Empty
cout << "MakeEmpty() -- ";
try
{
sPtr->MakeEmpty();
cout << "completed" << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case 'p': // Print Stack
cout << "Print() -- ";
sPtr->Print();
break;
case 't': // Top of Stack
try
{
cout << "Top() -- " << sPtr->Top() << endl;
}
catch (StackEmpty)
{
cout << "Top() -- Failed Empty Stack" << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case '>': // Max value within Stack
try
{
cout << "Max() -- " << sPtr->Max() << endl;
}
catch (StackEmpty)
{
cout << "Max() -- Failed Empty Stack" << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case '<': // Min value within Stack
try
{
cout << "Min() -- " << sPtr->Min() << endl;
}
catch (StackEmpty)
{
cout << "Min() -- Failed Empty Stack" << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case '?': // Peek(n) Stack
inputs >> value;
try
{
cout << "Peek(" << value << ") -- " << sPtr->Peek(value) << endl;
}
catch (StackInvalidPeek)
{
cout << "Peek(" << value << ") -- Failed Invalid Peek" << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case 's': // Size of Stack
cout << "Size() -- ";
try
{
cout << sPtr->Size() << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case 'z': // Capacity of Stack
cout << "Capacity() -- ";
try
{
cout << sPtr->Capacity() << endl;
}
catch (...)
{
cout << "operation failed" << endl;
}
break;
case 'd': // Destructor
cout << "~Stack() -- ";
try
{
delete sPtr;
sPtr = NULL;
cout << "completed" << endl << endl;
}
catch (...)
{
cout << "operation failed" << endl << endl;
}
break;
default: // Error
cout << "Error - unrecognized operation '" << op << "'" << endl;
cout << "Terminating now..." << endl;
return 1;
break;
}
inputs >> op; // Attempt to input next command
}
return 0;
} // End main()
||||||||||||||||||||||||||||||||||||||||||||||||||
Here is the stack specification file(again with comments)
||||||||||||||||||||||||||||||||||||||||||||||||||
#include
using namespace std;
#ifndef STACK_H
#define STACK_H
class StackEmpty
{
// Exception class - throw an object of this type when stack is empty
// Hint: there is no code for exception classes
};
class StackFull
{
// Exception class - throw an object of this type when stack is full
};
class StackInvalidPeek
{
// Exception class - throw an object of this type when invalid peek position is used
};
class Stack // Models stack of integers ADT implemented as a dynamically allocated array
{
private:
int* array; // Points to the stack array
int num; // Holds max number of elements that may be stored in stack array
int top; // Holds the index of the top data value stored on the stack
void Resize(int n); // Attempts to increase size of stack array to 2*num and then push n onto stack
// If unable to resize, throw StackFull exception
public:
Stack(int n); // Parameterized constructor dynamically allocates an empty stack array
// that may hold no more than n elements and initializes other private variables
~Stack(); // Destructor deallocates all dynamically-allocated memory
// associated with the object
void Push(int n); // Pushes integer n onto top of stack. If stack is full, attempts to
// resize stack and then push n. If unable to resize, throws StackFull exception.
void Pop(); // Removes top integer from stack
// If stack is empty, throws StackEmpty exception
bool IsEmpty() const; // Returns true if stack is empty; false otherwise
bool IsFull() const; // Returns true if stack is full; false otherwise
void MakeEmpty(); // Removes all items from stack leaving an empty, but usable stack with capacity num
// If stack is already empty, MakeEmpty() does nothing
int Top() const; // Returns value of top integer on stack WITHOUT modifying the stack
// If stack is empty, throws StackEmpty exception
int Size() const; // Returns number of items on stack WITHOUT modifying the stack
int Max() const; // Returns value of largest integer on stack WITHOUT modifying the stack
// If stack is empty, throws StackEmpty
int Min() const; // Returns value of smallest integer on stack WITHOUT modifying the stack
// If stack is empty, throws StackEmpty
int Peek(unsigned int n) const; // Returns stack value n levels down from top of stack. Peek(0) = Top()
// If position n does not exist, throws StackInvalidPeek
int Capacity() const; // Returns total num of elements that maybe stored in stack array
//reminder to self- dont modify the print code, and dont place it in stack.cpp
void Print() const // Writes stack contents to stdout, separated by a space, followed by endl
{
int index = top;
cout << "Top { ";
while (index != -1)
{
cout << array[index] << " ";
index--;
}
cout << "} Bottom" << endl;
} // End Print()
}; // End Class Stack
#endif
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Then all that is needed is the implementation file
But here are the inputs that will be run through the program
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
# p03input1.txt -- Test: Stack(), Push(), Pop(), Top(), ~Stack()
# Test: Stack(), Push(), Pop(), Top(), ~Stack()
c 8
p
t
+ 5
+ 10
+ 15
p
t
+ 20
+ 25
+ 30
p
t
-
-
p
+ 35
+ 40
t
+ 45
t
p
-
-
-
-
-
-
-
-
p
t
d
# Test: Stack(), Push(), Pop(), Top(), ~Stack()
c 4
p
-
t
d
|||||||||||||||||||||
# p03input2.txt -- Test IsFull(), IsEmpty(), MakeEmpty()
# Size(), Capacity()
# Test IsFull(), IsEmpty(), MakeEmpty()
c 8
e
f
+ 5
+ 10
+ 15
+ 20
+ 25
+ 30
p
e
f
m
p
e
f
+ 35
+ 40
+ 45
+ 50
p
e
f
-
-
-
p
e
f
m
p
e
f
d
# Test Size()
c 6
p
s
+ 5
+ 10
p
s
+ 15
+ 20
p
s
+ 25
+ 30
p
s
-
-
-
p
s
-
-
-
p
s
d
# Test Capacity()
c 2
z
+ 5
z
+ 10
z
+ 15
z
+ 20
z
+ 25
z
+ 30
z
p
-
-
-
z
p
-
-
-
z
p
d
||||||||||||||||||||||||||
# p03input3.txt -- Test Min(), Max(), Peek(...)
# Test Min() and Max()
c 8
<
>
+ 5
+ 30
+ 15
+ 20
+ 50
+ 10
p
<
>
+ 20
+ 50
+ 5
p
<
>
-
-
-
p
<
>
-
-
-
p
<
>
d
# Test Peek(n)
c 8
? 0
+ 5
+ 30
+ 15
+ 20
+ 50
+ 10
p
? 0
? 1
? 2
? 3
? 4
? 5
? 6
p
-
-
-
p
? 0
? 1
? 2
? 5
p
-
-
-
p
? 0
? 1
? 2
? 3
? 4
? 5
+ 25
+ 9
+ 8
p
? 0
? 1
? 2
? 3
? 4
? 5
d
|||||||||||||||||||||||||
This isnt a project so there is no due date, but any quick help would be appreciated! Thank you!
Explanation / Answer
Hey!
As per the question provided by you, I can guess that my information will help you t know Pointers and dynamic memory allocation, which can lead you to further study the project.
All variables, arrays, structures and unions that we worked with so far are statically allocated, meaning that whenever an appropriate scope is entered (e.g. a function is invoked) an amount of memory dependent on the data types and sizes is allocated from the stack area of the memory. When the program goes out of the scope (e.g. when a function returns), this memory is returned back to the stack. There is an alternative way of allocating memory, more precisely, from the heap part of the memory. In this case, the user makes specific calls to capture some amount of memory and continues to hold that memory unless it is explicitly (i.e., by distinguished calls) returned back to the heap. Such memory is said to be dynamically allocated.
In order to exemplify the usefulness of dynamic memory allocation, suppose that there are two types of foomatic collections: the first type refers to an array of ten integers, whereas the second type refers to an array of ten million integers. A foomatic chain is made from a combination of one million collections of first type and few (say, ten) collections of the second type. Such a chain demands a total memory capable of holding 110 million integers. Assuming that an integer is of size 32 bits, this amounts to a memory of 440 Megabytes. A modern personal computer usually has enough memory to accommodate this data.
It is a foomatic convention to treat both types of collection uniformly, i.e., our plan is to represent both by a single data type. Think of the difference between you and me. I am the instructor (synonymously the president) of the class, whereas students are only listeners (synonymous with citizens). A president is the most important person in a society, he requires microphones, computers, bla bla bla. Still, both the president and each citizen are of the same data type called human.
So a foollection is a foomatic human capable of representing a collection of either type. If we plan to handle it using a structure with an array (or union), we must prepare for the bigger collections. The definition goes like this:
Now irrespective of what a foollection data actually stores, it requires memory for ten million and one integers. (Think of each of you being given a PA system and a computer in the class.) A foomatic chain then requires over 40,000 Gigabytes of memory. This is sheer waste of space, since only 440 Megabytes suffice. Moreover, no personal computer I have heard of comes with so much memory including hard disks.
What is the way out? Let us plan to redefine foollection in the following way:
I have replaced the static array by a pointer. We will soon see that a pointer can be allocated memory from the heap and that the amount of memory to be allocated to each pointer can be specified during the execution of the program. Thus the data pointer in a foollection variable is assigned exactly as much memory as is needed. (It is as if when I come to the classroom, the run-time system gives me a PA system and a computer, whereas a student is given only a comfortable chair.) Now each collection requires, in addition to the actual data array, the space for an int variable and for a pointer, typically demanding 4 bytes each. So a foomatic chain requires a space overhead of slightly more than 8 Megabytes, i.e., a chain with all foomatic abstractions now fits in a memory of size less than 450 Megabytes. My computer has this much space.