Programming Project #4 Solution

GStack Class

You are to code a template stack class, GStack<class T, a generic class from which an stack object can be created to work with one specific type Your GStack class should store it’s data in an object of type List<T, a class provided by the C++ STL.




Your stack class should provide operations indicated in the specification below (you will need to provide a class StackException) :




// creates an empty stack

GStack();




// Determines whether this stack is empty.

// return True if this stack is empty; otherwise returns false

bool isEmpty() const;




// Adds an item to the top of this stack.

// Postcondition: If the insertion is successful, newItem is on the top of this stack.

// Throws a StackException If the item cannot be placed on this stack.

void push(const T& newItem) throw(StackException);




// Removes the top of this stack.

// Postcondition: If this stack is not empty, the item that was added most

// recently is removed. If this stack is empty a StackException is thrown.

void pop() throw(StackException);




// Retrieves and removes the top of this stack.

// Postcondition: If this stack is not empty, the item that was added most

// recently is removed, and stackTop contains the item

// If this stack is empty, a StackException is thrown

void pop(T& stackTop) throw(StackException);




// Retrieves the top of this stack.

// Postcondition: If this stack is not empty, stackTop contains the item

// that was added most recently. If this stack is empty, a StackException is thrown.

void getTop(T& stackTop) const throw(StackException);




The Application

 
You are to write an application which will be used to add together very large numbers.




The largest magnitute of integers is limited, so we are not able to add 18,274,364,583,929,273,748,459,595,684,373 and 8,129,498,165,026,350,236

since integer variables cannot hold such large values, let alone their sum. The problems can be solved if we treat these numbers as a group of digits, store the digits on two stacks, and then perform addition by popping digits from the stacks, and placing the digits of the sum on a third stack.




The algorithm follows (variables in bold):




read the first number and //numbers must be read as strings, as they may be to large to fit in a numerical type variable

push the digits (left to right ) on to stack1

 

read the second number

push the digits on to stack2




initialize column_result to 0




while at least one stack is not empty

if stack1 is not empty

pop a value from stack1

 

if stack2 is not empty

pop a value from stack2




column_result += sum of popped values




push the ‘unit’ digit of column_result on sum_stack




if column_result 9

column_result = ten’s digit (the carry)

else

column_result = 0

end while

 

if column_result is not zero

push column result on sum_stack




while sum_stack is not empty

pop sum_stack

display popped value







Your application should be interactive, that is, accept two numbers to be added from the user, and output the result.

Additionally, your application responsible for ‘catching’ any exception that might be thrown by the Stack class. That is, each push, pop or top call should be enclosed

in a try/catch structure which outputs a helpful debugging.




I suggest you test your stack class (with method updates) PRIOR to using it in the application. That way, you can debug your stack without the complexity of the application code. Then when debugging the application, you know that the stack is functioning correctly.




Submit your stack class source code and your application source. Again, if you are in the daytime section, please provide a listing of both files and a disk. If you are in the online section, send the source code as an email attachment.