Description: For a given integer n > 1, the smallest integer d > 1 that divides n is a prime factor. We can find the prime factorization of n if we find d and then replace n by the quotient of n divided by d, repeating this until n becomes 1. Write a program that determines the prime factorization of n in this manner, but that displays the prime factors in descending order. (When you find a prime factor, push it on a stack) For example, if n is 3960 the prime factorization is 11 * 5 * 3 * 3 * 2 * 2 * 2

driver.cpp

#include using namespace std; #include "LStack.h"

void print(Stack st) { st.display(cout); }

int main() { Stack s; cout << "Stack created. Empty? " << boolalpha << s.empty() << endl;

cout << "How many elements to add to the stack? "; int numItems; cin >> numItems; for (int i = 1; i <= numItems; i++) s.push(100*i); cout << "Stack empty? " << s.empty()<< endl;

cout << "Contents of stack s (via print): "; print(s); cout << endl; cout << "Check that the stack wasn't modified by print: "; s.display(cout); cout << endl;

Stack t, u; t = u = s; cout << "Contents of stacks t and u after t = u = s (via print): "; cout << "u: "; print(u); cout << endl; cout << "t: "; print(t); cout << endl;

cout << "Top value in t: " << t.top()<< endl;

while (!t.empty()) { cout << "Popping t: " << t.top() << endl; t.pop(); } cout << "Stack t empty? " << t.empty()<< endl; cout << "Top value in t: " << t.top()<< endl; cout << "Trying to pop t: " << endl; t.pop(); }

LStack.cpp

#include using namespace std;

#include "LStack.h"

//--- Definition of Stack constructor Stack::Stack() : myTop(0) {}

//--- Definition of Stack copy constructor Stack::Stack(const Stack & original) { myTop = 0; if (!original.empty()) { // Copy first node myTop = new Stack::Node(original.top());

// Set pointers to run through the stacks linked lists Stack::NodePointer lastPtr = myTop, origPtr = original.myTop->next;

while (origPtr != 0) { lastPtr->next = new Stack::Node(origPtr->data); lastPtr = lastPtr->next; origPtr = origPtr->next; } } }

//--- Definition of Stack destructor Stack::~Stack() { // Set pointers to run through the stack Stack::NodePointer currPtr = myTop, // node to be deallocated nextPtr; // its successor while (currPtr != 0) { nextPtr = currPtr->next; delete currPtr; currPtr = nextPtr; } }

//--- Definition of assignment operator const Stack & Stack::operator=(const Stack & rightHandSide) { if (this !=& rightHandSide) // check that not st = st { this->~Stack(); // destroy current linked list if (rightHandSide.empty()) // empty stack myTop = 0; else { // copy rightHandSide's list // Copy first node myTop = new Stack::Node(rightHandSide.top());

// Set pointers to run through the stacks' linked lists Stack::NodePointer lastPtr = myTop, rhsPtr = rightHandSide.myTop->next;

while (rhsPtr != 0) { lastPtr->next = new Stack::Node(rhsPtr->data); lastPtr = lastPtr->next; rhsPtr = rhsPtr->next; } } } return *this; }

//--- Definition of empty() bool Stack::empty() const { return (myTop == 0); }

//--- Definition of push() void Stack::push(const StackElement & value) { myTop = new Stack::Node(value, myTop); }

//--- Definition of display() void Stack::display(ostream & out) const { Stack::NodePointer ptr; for (ptr = myTop; ptr != 0; ptr = ptr->next) out << ptr->data << endl; }

//--- Definition of top() StackElement Stack::top() const { if (!empty()) return (myTop->data); else { cerr << "*** Stack is empty " " -- returning garbage *** "; StackElement * temp = new(StackElement); StackElement garbage = *temp; // "Garbage" value delete temp; return garbage; } }

//--- Definition of pop() void Stack::pop() { if (!empty()) { Stack::NodePointer ptr = myTop; myTop = myTop->next; delete ptr; } else cerr << "*** Stack is empty -- can't remove a value *** "; }

LStack.h

#include using namespace std;

#ifndef LSTACK #define LSTACK

typedef int StackElement;

class Stack { public: /***** Function Members *****/ /***** Constructors *****/ Stack(); /*----------------------------------------------------------------------- Construct a Stack object. Precondition: None. Postcondition: An empty Stack object has been constructed (myTop is initialized to a null pointer). ------------------------------------------------------------------------*/

Stack(const Stack & original); //-- Same documentation as in Figure 7.8

/***** Destructor *****/ ~Stack(); /*------------------------------------------------------------------------ Class destructor

Precondition: None Postcondition: The linked list in the stack has been deallocated. ------------------------------------------------------------------------*/

/***** Assignment *****/ const Stack & operator= (const Stack & rightHandSide); /*------------------------------------------------------------------------ Assignment Operator Precondition: rightHandSide is the stack to be assigned and is received as a const reference parameter. Postcondition: The current stack becomes a copy of rightHandSide and a const reference to it is returned. ------------------------------------------------------------------------*/

bool empty() const; /*------------------------------------------------------------------------ Check if stack is empty. Precondition: None Postcondition: Returns true if stack is empty and false otherwise. -----------------------------------------------------------------------*/

void push(const StackElement & value); /*------------------------------------------------------------------------ Add a value to a stack.

Precondition: value is to be added to this stack Postcondition: value is added at top of stack provided there is space; otherwise, a stack-full message is displayed and execution is terminated. -----------------------------------------------------------------------*/

void display(ostream & out) const; /*------------------------------------------------------------------------ Display values stored in the stack.

Precondition: ostream out is open. Postcondition: Stack's contents, from top down, have been output to out. -----------------------------------------------------------------------*/

StackElement top() const; /*------------------------------------------------------------------------ Retrieve value at top of stack (if any).

Precondition: Stack is nonempty Postcondition: Value at top of stack is returned, unless the stack is empty; in that case, an error message is displayed and a "garbage value" is returned. -----------------------------------------------------------------------*/

void pop(); /*------------------------------------------------------------------------ Remove value at top of stack (if any).

Precondition: Stack is nonempty. Postcondition: Value at top of stack has been removed, unless the stack is empty; in that case, an error message is displayed and execution allowed to proceed. -----------------------------------------------------------------------*/

private: /*** Node class ***/ class Node { public: StackElement data; Node * next; //--- Node constructor Node(StackElement value, Node * link = 0) /*------------------------------------------------------------------- Precondition: None. Postcondition: A Node has been constructed with value in its data part and its next part set to link (default 0). -------------------------------------------------------------------*/ : data(value), next(link) {} };

typedef Node * NodePointer; /***** Data Members *****/ NodePointer myTop; // pointer to top of stack

}; // end of class declaration

#endif