Nyhoff, ADTs, Data Structures and Problem Solving with C++, Second Edition,
© 2005 Pearson Education, Inc. All rights reserved. 0-13-140909-3
Figure 7.2 Conversion from Base Ten to Base Two |
/*--------------------------------------------------------------
This program uses a stack to convert the base-ten representation
of a positive integer entered as input to base two, which is
then output.
---------------------------------------------------------------------*/
#include <iostream>
using namespace std;
#include "Stack.h" // our own -- <stack> for STL version
int main()
{
unsigned number, // the number to be converted
remainder; // remainder when number is divided by 2
Stack stackOfRemainders; // stack of remainders
char response; // user response
do
{
cout << "Enter positive integer to convert: ";
cin >> number;
while (number != 0)
{
remainder = number % 2;
stackOfRemainders.push(remainder);
number /= 2;
}
cout << "Base-two representation: ";
while ( !stackOfRemainders.empty() )
{
remainder = stackOfRemainders.top();
stackOfRemainders.pop();
cout << remainder;
}
cout << endl;
cout << "\nMore (Y or N)? ";
cin >> response;
}
while (response == 'Y' || response == 'y');
}
|
Figure 7.3 Class Declaration for a Stack Type |
/*-- Stack.h ---------------------------------------------------
This header file defines a Stack data type.
Basic operations:
constructor: Constructs an empty stack
empty: Checks if a stack is empty
push: Modifies a stack by adding a value at the top
top: Accesses the top stack value; leaves stack
unchanged
pop: Modifies stack by removing the value at the
top
display: Displays all the stack elements
Class Invariant:
1. The stack elements (if any) are stored in positions
0, 1, . . ., myTop of myArray.
2. -1 <= myTop < STACK_CAPACITY
--------------------------------------------------------------*/
#include <iostream>
using namespace std;
#ifndef STACK
#define STACK
const int STACK_CAPACITY = 128;
typedef int StackElement;
class Stack
{
public:
/***** Function Members *****/
private:
/***** Data Members *****/
StackElement myArray[STACK_CAPACITY];
int myTop;
};
#endif
|
Figure 7.4A Completed Stack.h File |
/*-- Stack.h ---------------------------------------------------
This header file defines a Stack data type.
Basic operations:
constructor: Constructs an empty stack
empty: Checks if a stack is empty
push: Modifies a stack by adding a value at the top
top: Retrieves the top stack value; leaves stack unchanged
pop: Modifies stack by removing the value at the top
display: Displays all the stack elements
Class Invariant:
1. The stack elements (if any) are stored in positions
0, 1, . . ., myTop of myArray.
2. -1 <= myTop < STACK_CAPACITY
--------------------------------------------------------------*/
#include <iostream>
#ifndef STACK
#define STACK
const int STACK_CAPACITY = 128;
typedef int StackElement;
class Stack
{
public:
/***** Function Members *****/
/***** Constructor *****/
Stack();
/*----------------------------------------------------------
Construct a Stack object.
Precondition: None.
Postcondition: An empty Stack object has been constructed
(myTop is initialized to -1 and myArray is an array
with STACK_CAPACITY elements of type StackElement).
-----------------------------------------------------------*/
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:
/***** Data Members *****/
StackElement myArray[STACK_CAPACITY];
int myTop;
}; // end of class declaration
#endif
|
Figure 7.4B Stack.cpp File |
/*-- Stack.cpp-----------------------------------------------------------
This file implements Stack member functions.
-------------------------------------------------------------------------*/
#include <iostream>
using namespace std;
#include "Stack.h"
//--- Definition of Stack constructor
Stack::Stack()
: myTop(-1)
{}
//--- Definition of empty()
bool Stack::empty() const
{
return (myTop == -1);
}
//--- Definition of push()
void Stack::push(const StackElement & value)
{
if (myTop < STACK_CAPACITY - 1) //Preserve stack invariant
{
++myTop;
myArray[myTop] = value;
}
else
{
cerr << "*** Stack full -- can't add new value ***\n"
"Must increase value of STACK_CAPACITY in Stack.h\n";
exit(1);
}
}
//--- Definition of display()
void Stack::display(ostream & out) const
{
for (int i = myTop; i >= 0; i--)
out << myArray[i] << endl;
}
//--- Definition of top()
StackElement Stack::top() const
{
if ( !empty() )
return (myArray[myTop]);
else
{
cerr << "*** Stack is empty "
" -- returning garbage value ***\n";
return *(new StackElement);
}
}
//--- Definition of pop()
void Stack::pop()
{
if ( !empty() )
myTop--;
else
cerr << "*** Stack is empty -- "
"can't remove a value ***\n";
}
|
Figure 7.5 Stack Test Program |
/*---------------------------------------------------------------------
Driver program to test the Stack class.
----------------------------------------------------------------------*/
#include <iostream>
#include <iomanip>
using namespace std;
#include "Stack.h"
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(i);
cout << "Stack contents:\n";
s.display(cout);
cout << "Stack empty? " << s.empty() << endl;
cout << "Top value: " << s.top() << endl;
while (!s.empty())
{
cout << "Popping " << s.top() << endl;
s.pop();
}
cout << "Stack empty? " << s.empty() << endl;
cout << "Top value: " << s.top() << endl;
cout << "Trying to pop: " << endl;
s.pop();
}
|
Figure 7.6A DStack.h File |
/*-- DStack.h ---------------------------------------------------
This header file defines a Stack data type.
Basic operations:
constructor: Constructs an empty stack
empty: Checks if a stack is empty
push: Modifies a stack by adding a value at the top
top: Accesses the top stack value; leaves stack
unchanged
pop: Modifies stack by removing the value at the
top
display: Displays all the stack elements
Class Invariant:
1. The stack elements (if any) are stored in positions
0, 1, . . ., myTop of myArray.
2. -1 <= myTop < myCapacity
--------------------------------------------------------------*/
#include <iostream>
using namespace std;
#ifndef DSTACK
#define DSTACK
typedef int StackElement;
class Stack
{
public:
/***** Function Members *****/
/***** Constructors *****/
Stack(int numElements = 128);
/*----------------------------------------------------------
Construct a Stack object.
Precondition: None.
Postcondition: An empty Stack object has been constructed
(myTop is initialized to -1 and myArray is an array
with numElements (default 128) elements of type
StackElement).
-----------------------------------------------------------*/
Stack(const Stack & original);
/*----------------------------------------------------------
Copy Constructor
Precondition: original is the stack to be copied and
is received as a const reference parameter.
Postcondition: A copy of original has been constructed.
-----------------------------------------------------------*/
/***** Destructor *****/
~Stack();
/*----------------------------------------------------------
Class destructor
Precondition: None
Postcondition: The dynamic array in the stack has been
deallocated.
-----------------------------------------------------------*/
/***** Assignment *****/
Stack & operator= (const Stack & original);
/*----------------------------------------------------------
Assignment Operator
Precondition: original is the stack to be assigned and
is received as a const reference parameter.
Postcondition: The current stack becomes a copy of
original and a 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:
/***** Data Members *****/
int myCapacity, // capacity of stack
myTop; // top of stack
StackElement * myArray; // dynamic array to store elements
}; // end of class declaration
#endif
|
Figure 7.6B DStack.cpp File |
/*-- DStack.cpp---------------------------------------------------------- This file implements Stack member functions. -------------------------------------------------------------------------*/ #include <iostream> #include <cassert> #include <new> using namespace std; #include "DStack.h" //--- Definition of Stack constructor Stack::Stack(int numElements) { assert (numElements > 0); // check precondition myCapacity = numElements; // set stack capacity // allocate array of this capacity myArray = new(nothrow) StackElement[myCapacity]; if (myArray != 0) // memory available myTop = -1; else { cerr << "Inadequate memory to allocate stack \n" " -- terminating execution\n"; exit(1); } // or assert(myArray != 0); } //--- Definition of Stack copy constructor Stack::Stack(const Stack & original) : myCapacity(original.myCapacity), myTop(original.myTop) { //--- Get new array for copy myArray = new(nothrow) StackElement[myCapacity]; // allocate array in copy if (myArray != 0) // check if memory available // copy original's array member into this new array for (int pos = 0; pos < myCapacity; pos++) myArray[pos] = original.myArray[pos]; else { cerr << "*Inadequate memory to allocate stack ***\n"; exit(1); } } //--- Definition of Stack destructor Stack::~Stack() { delete [] myArray; } //--- Definition of assignment operator Stack & Stack::operator=(const Stack & original) { if (this != &original) // check that not st = st { //-- Allocate a new array if necessary if (myCapacity != original.myCapacity) { delete[] myArray; // destroy previous array myCapacity = original.myCapacity; // copy myCapacity myArray = new StackElement[myCapacity]; if (myArray == 0) // check if memory available { cerr << "*** Inadequate memory ***\n"; exit(1); } } //--- Copy original's array into this myArray for (int pos = 0; pos < myCapacity; pos++) myArray[pos] = original.myArray[pos]; myTop = original.myTop; // copy myTop member } return *this; } //--- Definition of empty() bool Stack::empty() const { return (myTop == -1); } //--- Definition of push() void Stack::push(const StackElement & value) { if (myTop < myCapacity - 1) //Preserve stack invariant { ++myTop; myArray[myTop] = value; } else { cerr << "*** Stack full -- can't add new value ***\n" "Must increase value of STACK_CAPACITY in Stack.h\n"; exit(1); } } //--- Definition of display() void Stack::display(ostream & out) const { for (int i = myTop; i >= 0; i--) out << myArray[i] << endl; } //--- Definition of top() StackElement Stack::top() const { if ( !empty() ) return (myArray[myTop]); else { cerr << "*** Stack is empty " " -- returning garbage value ***\n"; return *(new StackElement); } } //--- Definition of pop() void Stack::pop() { if ( !empty() ) myTop--; else cerr << "*** Stack is empty -- " "can't remove a value ***\n"; } |
Figure 7.10 Test Program for DStack Class |
/*---------------------------------------------------------------------
Driver program to test the Stack class.
----------------------------------------------------------------------*/
#include <iostream>
#include <iomanip>
using namespace std;
#include "DStack.h"
void print(Stack st)
{ st.display(cout); }
int main()
{
int cap;
cout << "Enter stack capacity: ";
cin >> cap;
Stack s(cap);
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(i);
cout << "Stack empty? " << s.empty() << endl;
cout << "Contents of stack s (via print):\n";
print(s); cout << endl;
cout << "Check that the stack wasn't modified by print:\n";
s.display(cout); cout << endl;
Stack t, u;
t = u = s;
cout << "Contents of stacks t and u after t = u = s (via print):\n";
cout << "u:\n"; print(u); cout << endl;
cout << "t:\n"; 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 << "\nNow try to retrieve top value from t." << endl;
cout << "Top value in t: " << t.top() << endl;
cout << "\nTrying to pop t: " << endl;
t.pop();
}
|
Figure
7.11 Linked-List-Based
|
class Stack
{
public:
/***** Function Members *****/
// Prototypes same as in preceding section
private:
/*** Node class ***/
class Node
{
public:
StackElement data;
Node * next;
//--- Node constructor
Node(StackElement value, Node * link = 0)
/*------------------------------------------------------
Precondition: value is received
Postcondition: A Node has been constructed with value
in its data part and itb 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
|
Figure 7.12 LStack.cpp Implementation |
//--- LStack.cpp ------------------------------------------------- #include <new> 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 stack's 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 Stack & Stack::operator=(const Stack & original) { myTop = 0; if (original.empty()) return *this; if (this != &original) // check that not st = st { this->~Stack(); // destroy current linked list // 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; } } 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 ***\n"; return *(new StackElement); // "Garbage" value } } //--- 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 ***\n"; } |
Figure 7.12C Driver Program for Linked List Implementation of Stack |
/*---------------------------------------------------------------------
Driver program to test the Stack class.
----------------------------------------------------------------------*/
#include <iostream>
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(i);
cout << "Stack empty? " << s.empty() << endl;
cout << "Contents of stack s (via print):\n";
print(s); cout << endl;
cout << "Check that the stack wasn't modified by print:\n";
s.display(cout); cout << endl;
Stack t, u;
t = u = s;
cout << "Contents of stacks t and u after t = u = s (via print):\n";
cout << "u:\n"; print(u); cout << endl;
cout << "t:\n"; 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 << "\nNow try to retrieve top value from t." << endl;
cout << "Top value in t: " << t.top() << endl;
cout << "\nTrying to pop t: " << endl;
t.pop();
}
|
Figure 7.15 Converting Infix to Postfix |
/*--------------------------------------------------------------------------
Convert infix expressions to postfix.
Input: An infix expression and user responses
Output: The postfix expression
--------------------------------------------------------------------------*/
#include <iostream> // <<, >>, cout, cin
#include <string> // string, ==, find, npos
#include <cassert> // assert()
#include <cctype> // alnum()
using namespace std;
#include "DStack.h" // Stack class with StackElement = char
string postfix(string exp);
int main()
{
string exp; // infix expression
cout << "NOTE: Enter # for infix expression to stop.\n";
for (;;)
{
cout << "\nInfix expression? ";
getline(cin, exp);
if (exp == "#") break;
cout << "Postfix expression is " << postfix(exp) << endl;
}
}
string postfix(string exp)
/*-------------------------------------------------------------------------
Function to convert an infix expression exp to postfix.
Precondition: exp is received
Postcondition: postfix expression corresponding to exp is returned
or an error message displayed if an error was found in exp.
-------------------------------------------------------------------------*/
{
char token, // character in exp
topToken; // token on top of opStack
Stack opStack; // stack of operators
string RPNexp; // postfix expression
const string BLANK = " ";
for (int i = 0; i < exp.length(); i++)
{
token = exp[i];
switch(token)
{
case ' ' : break; // do nothing -- skip blanks
case '(' : opStack.push(token);
break;
case ')' : for (;;)
{
assert (!opStack.empty());
topToken = opStack.top();
opStack.pop();
if (topToken == '(') break;
RPNexp.append(BLANK + topToken);
}
break;
case '+' : case '-' :
case '*' : case '/': case'%':
for (;;)
{
if (opStack.empty() ||
opStack.top() == '(' ||
(token == '*' || token == '/' || token == '%') &&
(opStack.top() == '+' || opStack.top() == '-'))
{
opStack.push(token);
break;
}
else
{
topToken = opStack.top();
opStack.pop();
RPNexp.append(BLANK + topToken);
}
}
break;
default : // operand
RPNexp.append(BLANK + token);
for(;;)
{
if ( !isalnum(exp[i+1]) ) break; // end of identifier
i++;
token = exp[i];
RPNexp.append(1, token);
}
}
}
// Pop remaining operators on the stack
for (;;)
{
if (opStack.empty()) break;
topToken = opStack.top();
opStack.pop();
if (topToken != '(')
{
RPNexp.append(BLANK + topToken);
}
else
{
cout << " *** Error in infix expression ***\n";
break;
}
}
return RPNexp;
}
|
Figure |
|
|
Figure |
|
|
Figure |
|
|
Figure |
|
|
Figure |
|
|
Figure |
|
|
Figure |
|
|