// test_SLList.h.cpp // // 2014-08-13 //
// compile with C++11 compiler //
#include "SLList.h"
int main()
{
List< int > myLst;
myLst.push_front( 1 );
myLst.push_front( 2 );
myLst.push_front( 3 );
myLst.push_front( 9 );
myLst.push_front( 7 );
myLst.push_front( 6 );
myLst.push_back( 4 );
myLst.push_back( 5 );
myLst.push_back( 0 );
myLst.push_back( 8 );
myLst.print();
cout << "\nNote ... here ... testing post ++ increment ...\n";
for( auto &e : myLst ) cout << e++ << ' ';
cout << '\n';
List< int >::iterator i = myLst.begin(), end = myLst.end();
List< int >::const_iterator it = myLst.begin();
cout << "\nTesting iter's ... \n";
if( it == i ) cout << "iter's (addresses) are equal ...\n";
if( i == it ) cout << "iter's (addresses) are equal ...\n";
if( !(it != i) ) cout << "iter's (addresses) are equal ...\n";
if( !(i != it) ) cout << "iter's (addresses) are equal ...\n";
bubble_sort( i, end, MyCmpAscending<int>() );
cout << "\nAfter post ++ increment and then a bubble_sort... \n";
// NOTE: using const_iterator here ...
for( ; it != myLst.end() ; it++ )
cout << *it << ' ';
cout << "\nPress 'Enter' to continue/exit ... ";
cin.get();
}
// SLList.h // // 2014-08-13 //
// compile with C++11 compiler //
#ifndef SSLIST_H
#define SSLIST_H
#include <iostream>
#include <algorithm> // re. list std::swap ...
using namespace std;
template< typename T >
class List
{
struct Node
{
T val;
Node* next;
Node( const T& x, Node* next ) : val(x), next(next) {}
Node( const T& x ) : val(x), next(nullptr) {}
// implicit copy constructor, copy assignment and destructor
} ;
Node* head;
Node* tail;
size_t len;
public:
List() : head( nullptr ), tail(nullptr), len(0) {}
~List() { clear(); }
void clear()
{
Node* cur;
while( head )
{
cur = head;
head = head->next;
delete cur;
}
}
void push_front( const T& val )
{
Node* newNode = new Node( val, head );
head = newNode;
if( !len ) tail = head;
++len;
}
void push_back( const T& val )
{
Node* newNode = new Node( val, nullptr );
if( len ) tail->next = newNode;
else head = newNode;
tail = newNode;
++len;
}
void print() const
{
const Node* cur = head;
if( cur ) std::cout << "Printing the list: \n";
while( cur )
{
std::cout << cur->val << ' ';
cur = cur->next;
}
std::cout << std::endl;
}
class iterator : std::iterator< forward_iterator_tag, T >
{
friend List< T >;
Node* ptr;
public:
explicit iterator( Node* p = nullptr ) : ptr(p) {}
// implicit copy constructor, copy assignment and destructor
T& operator * () { return ptr->val; }
iterator & operator ++ () { ptr = ptr->next; return *this; }
iterator operator ++ (int) { iterator tmp = *this; ++*this; return tmp; }
bool operator == ( const iterator& other ) const
{
return ptr == other.ptr;
}
bool operator != ( const iterator& other) const
{
return ptr != other.ptr;
}
Node* get_ptr() const { return ptr; }
} ;
iterator begin() { return iterator(head); }
iterator end() { return iterator(nullptr); }
class const_iterator : std::iterator< forward_iterator_tag,
T, ptrdiff_t, const T*, const T& >
{
friend List< T >;
const Node* ptr;
public:
explicit const_iterator( const Node* p = nullptr ) : ptr(p) {}
// implicit copy constructor, copy assignment and destructor
// Note: this next ctor is 'vital' ... // comment out and compile to see why? //
const_iterator( const iterator& i) : ptr(i.ptr) {}
const T& operator* () const { return ptr->val; }
const_iterator& operator ++ () { ptr = ptr->next; return *this; }
const_iterator operator ++ (int)
{ const_iterator tmp = *this; ++*this; return tmp; }
bool operator == ( const const_iterator& other ) const
{
return ptr == other.ptr;
}
bool operator!= ( const const_iterator& other ) const
{
return ptr != other.ptr;
}
const Node* get_ptr() const { return ptr; }
} ;
const_iterator begin() const { return const_iterator(head); }
const_iterator end() const { return const_iterator(nullptr); }
friend bool operator == ( const iterator& a, const const_iterator& b )
{
return a.get_ptr() == b.get_ptr();
}
friend bool operator != ( const iterator& a, const const_iterator& b )
{
return a.get_ptr() != b.get_ptr();
}
friend bool operator == ( const const_iterator& a, const iterator& b )
{
return a.get_ptr() == b.get_ptr();
}
friend bool operator != ( const const_iterator& a, const iterator& b )
{
return a.get_ptr() != b.get_ptr();
}
} ;
// =========================================================
// This bubble sort IS USEFUL for SMALL data sets
// or when data is in a very near sorted state
// (1 or 2, or very few, elements out of order)
// i.e. only 1 or 2 or very few passes ... till sorted.
template < typename ForwardIter, typename Compare >
void bubble_sort( ForwardIter beg,
ForwardIter end, Compare comp )
{
ForwardIter prev = beg, left_el = beg, right_el = beg;
if( beg == end ) return; // empty or only one element ... //
bool aswap = true;
while( aswap )
{
aswap = false;
while( ++right_el != end )
{
prev = right_el;
// Note r,l order below when doing bubble_sort //
if( comp( *right_el, *left_el) )
{
std::swap( *left_el, *right_el );
aswap = true; // if NO swaps this pass then done .. //
}
++left_el;
}
end = prev; // --end;
left_el = right_el = beg; // start at beg if need a next loop
}
}
template< typename T >
struct MyCmpAscending // re. Ascending bubble_sort...
{
bool operator () ( const T& obj, const T& obj2 )
{
return obj < obj2;
}
} ;
// =========================================================
#endif
// test_MySLList.h.cpp //
#include "MySLList.h"
#include <iostream>
#include <string>
using namespace std;
void test_1()
{
MySLList< string > fruits;
fruits.push_back( "apples");
fruits.push_back( "oranges" );
fruits.push_back( "peaches" );
fruits.push_back( "pears" );
fruits.push_back( "grapes" );
MySLList< string >::const_iterator ptr = fruits.begin();
MySLList< string >::const_iterator end = fruits.end();
MySLList< string >::iterator pptr = fruits.begin();
MySLList< string >::iterator eend = fruits.end();
if( pptr == ptr ) cout << "equals\n";
else cout << "NOT equals\n";
cout << "They're all fruit ...\n";
while( ptr != end )
{
if( *ptr == "grapes" )
{
cout << "Yes ... " << *ptr << " are fruit."
<< endl;
break;
}
++ptr;
}
}
int main()
{
test_1();
cin.get();
}
// MySLList_Node.h //
#ifndef MYSLLIST_NODE_H
#define MYSLLIST_NODE_H
template< typename T > class MySLList; // forward declare
template< typename T > class MySLList_iterator; // forward declare
template< typename T > class const_MySLList_iterator; // forward declare
template < typename T >
class MySLList_Node
{
friend class MySLList< T >;
friend class MySLList_iterator< T >;
friend class const_MySLList_iterator< T >;
//MySLList_Node( const T& t, MySLList_Node< T >* next ) : elem(t), next(next) {}
MySLList_Node( const T& e ) : elem(e), next(0) {}
MySLList_Node( const T& e, MySLList_Node< T >* n ) : elem(e), next(n) {}
T elem;
MySLList_Node< T >* next;
} ;
#endif
// MySLList_iterator.h //
#ifndef MYSLLIST_ITERATOR_H
#define MYSLLIST_ITERATOR_H
#include <cassert>
template< typename T >
class MySLList_iterator : public std::iterator< std::forward_iterator_tag, T >
{
friend class MySLList< T >;
MySLList_Node< T >* ptr;
MySLList_iterator( MySLList_Node< T >* x ) : ptr(x) {}
public:
T& operator * () { return ptr->elem; }
//const T& operator * () const { return ptr->elem; }
MySLList_iterator< T >& operator ++ ();
MySLList_iterator< T > operator ++ (int)
{ MySLList_iterator< T > tmp = *this; ++*this; return tmp; }
bool operator != ( const MySLList_iterator< T >& other ) const;
bool operator == ( const MySLList_iterator< T >& other ) const { return !(*this != other); }
bool operator != ( const const_MySLList_iterator< T >& other ) const { return (ptr != other.get_ptr()); }
bool operator == ( const const_MySLList_iterator< T >& other ) const { return (ptr == other.get_ptr()); }
const MySLList_Node< T >* get_ptr() const { return ptr; };
} ;
/*
template< typename T >
T& MySLList_iterator< T >::operator * ()
{
return ptr->elem;
}
template< typename T >
const T& MySLList_iterator< T >::operator * () const
{
return ptr->elem;
}
*/
template< typename T >
MySLList_iterator< T >& MySLList_iterator< T >::operator ++ ()
{
assert( ptr != 0 );
ptr = ptr->next;
return *this;
}
template< typename T >
bool MySLList_iterator< T >:: operator != ( const MySLList_iterator< T >& other ) const
{
return this->ptr != other.ptr;
}
#endif
// const_MySLList_iterator.h //
#ifndef CONST_MYSLLIST_ITERATOR_H
#define CONST_MYSLLIST_ITERATOR_H
#include <cassert>
//#include "MySLList_iterator.h"
template< typename T >
class const_MySLList_iterator : public std::iterator<
std::forward_iterator_tag, T, ptrdiff_t, const T*, const T& >
{
friend class MySLList< T >;
const MySLList_Node< T >* ptr;
const_MySLList_iterator( MySLList_Node< T >* x ) : ptr(x) {}
public:
// this next ctor is 'vital ... comment it out and compile to see error message ... why ? //
const_MySLList_iterator< T >( const MySLList_iterator< T >& i ) : ptr(i.get_ptr()) {}
const MySLList_Node< T >* get_ptr() const { return ptr; };
//T& operator * () { return ptr->elem; }
const T& operator * () const { return ptr->elem; }
const_MySLList_iterator< T >& operator ++ ();
const_MySLList_iterator< T > operator ++ (int)
{ const_MySLList_iterator< T > tmp = *this; ++*this; return tmp; }
bool operator != ( const const_MySLList_iterator< T >& other ) const;
bool operator == ( const const_MySLList_iterator< T >& other ) const { return !(*this != other); }
bool operator != ( const MySLList_iterator< T >& other ) const { return (ptr != other.get_ptr()); }
bool operator == ( const MySLList_iterator< T >& other ) const { return (ptr == other.get_ptr()); }
} ;
/*
template< typename T >
T& const_MySLList_iterator< T >::operator * ()
{
return ptr->elem;
}
template< typename T >
const T& const_MySLList_iterator< T >::operator * () const
{
return ptr->elem;
}
*/
template< typename T >
const_MySLList_iterator< T >& const_MySLList_iterator< T >::operator ++ ()
{
assert( ptr != 0 );
ptr = ptr->next;
return *this;
}
template< typename T >
bool const_MySLList_iterator< T >:: operator != ( const const_MySLList_iterator< T >& other ) const
{
return this->ptr != other.ptr;
}
#endif
// MySLList.h //
#ifndef MYSLLIST_H
#define MYSLLIST_H
#include <iostream>
#include <string>
#include "MySLList_Node.h"
#include "MySLList_iterator.h"
#include "const_MySLList_iterator.h"
template< typename T >
class MySLList
{
public:
typedef MySLList_iterator< T > iterator;
MySLList() : head(0), tail(0) {}
~MySLList() { clear(); }
void push_front( const T& elem );
void push_back( const T& elem );
void clear();
bool empty() const { return head == 0; }
iterator begin() { return iterator( head ); }
iterator end() { return iterator( 0 ); }
typedef const_MySLList_iterator< T > const_iterator;
const_iterator begin() const { return const_iterator( head ); }
const_iterator end() const { return const_iterator( 0 ); }
private:
MySLList_Node< T > *head, *tail;
} ;
template< typename T >
void MySLList< T >::clear()
{
MySLList_Node< T >* ptr;
while( head )
{
ptr = head;
head = head->next;
std::cout << "Inside 'clear()' deleting " << ptr->elem << '\n';
delete ptr;
}
// Note: done while loop when head is 0 //
tail = 0;
}
template< typename T >
void MySLList< T >::push_front( const T& elem )
{
MySLList_Node< T >* newNode = new MySLList_Node< T >( elem, head );
if( !head ) tail = newNode;
head = newNode;
}
template< typename T >
void MySLList< T >::push_back( const T& elem )
{
MySLList_Node< T >* newNode = new MySLList_Node< T >( elem, 0 );
if( tail ) tail->next = newNode;
else head = newNode;
tail = newNode;
}
#endif
// test_SLList.h.cpp // // 2014-08-14 //
// needs C++11 compiler //
#define debugSLL 0
#include "SLList.h"
void tests_1()
{
using std::cout; using std::cin; using std::endl;
SLList< int > myLst;
// get some test data into the list ...
myLst.push_back( 3 );
myLst.push_back( 4 );
myLst.push_back( 5 );
myLst.push_front( 2 );
myLst.push_front( 1 );
myLst.push_front( 0 );
//SLList< int > myLst2 = myLst;
auto myLst2 = myLst;
cout << "Testing using iterator to print... \n";
cout << "Note: each element has value++ when done.\n";
SLList< int >::const_iterator i;
SLList< int >::iterator it;
for( it = myLst.begin(); it != myLst.end(); ++ it )
cout << (*it)++ << ' ';
cout << "\nTesting iter's ... \n";
if( it == i ) cout << "iter's (addresses) are equal ...\n";
if( i == it ) cout << "iter's (addresses) are equal ...\n";
if( !(it != i) ) cout << "iter's (addresses) are equal ...\n";
if( !(i != it) ) cout << "iter's (addresses) are equal ...\n";
cout << "\nPrinting with ... for( const auto e : myLst ) cout...\n";
for( const auto e : myLst ) cout << e << ' ';
cout << "\nmyLst2.print()... \n";
myLst2.print();
cout << endl;
while( myLst2.size() > 3 )
{
cout << "size = " << myLst2.size()
<< ", front = " << myLst2.front()
<< ", back = " << myLst2.back()
<< ", pop_front() ...\n";
myLst2.pop_front();
}
cout << endl;
while( !myLst2.empty() )
{
cout << "size = " << myLst2.size()
<< ", front = " << myLst2.front()
<< ", back = " << myLst2.back()
<< ", pop_back() ...\n";
myLst2.pop_back();
}
cout << "\nmyLst2.print() ...\n";
myLst2.print();
}
int main()
{
tests_1();
std::cout << "\nPress 'Enter' to continue/exit ... ";
std::cin.get();
}
// LISTNODE.H // // 2014-08-14 //
// needs C++11 compiler //
#ifndef LISTNODE_H
#define LISTNODE_H
//forward declaration of class SLList is required to announce that class
template< typename NODETYPE > class SLList;
template< typename NODETYPE >
class Node
{
friend class SLList< NODETYPE >;
NODETYPE data;
Node< NODETYPE > *nextPtr;
public:
// value ctor...
Node( const NODETYPE& info ) : data(info), nextPtr(nullptr)
{}
} ;
#endif
// SLList.h // // 2014-08-14 //
// needs C++11 compiler //
#ifndef SLLIST_H
#define SLLIST_H
#include "LISTNODE.H"
#include <iostream>
#include <stdexcept>
#ifndef debugSLL
#define debugSLL 0
#endif
template < typename NODETYPE >
class SLList
{
public:
//default constructor
explicit SLList(): firstPtr(nullptr), lastPtr(nullptr), len(0) {}
//destructor
~SLList()
{
clear();
#if debugSLL
std::cout << "dtor called ... all nodes 'cleared' ...\n";
#endif
}
void push_front( const NODETYPE& value )
{
Node< NODETYPE >* newPtr = getNewNode( value );
// faster running code if firstly handle most likely case ...
if( len )
{
newPtr->nextPtr = firstPtr;
firstPtr = newPtr;
}
else
{
lastPtr = firstPtr = newPtr;
}
++len;
}
void push_back( const NODETYPE& value )
{
Node< NODETYPE >* newPtr = getNewNode( value );
if( len )
{
lastPtr->nextPtr = newPtr;
lastPtr = newPtr;
}
else
{
lastPtr = firstPtr = newPtr;
}
++len;
}
const NODETYPE& front() const
{
if( !len )
throw std::out_of_range( "Error! List is empty, "
"so can NOT access front() ..." ) ;
// else ...
return firstPtr->data;
}
const NODETYPE& back() const
{
if( !len )
throw std::out_of_range( "Error! List is empty, "
"so can NOT access back() ..." ) ;
return lastPtr->data;
}
//return boolean to signify if operation is successful
bool pop_front()
{
if( len )
{
Node< NODETYPE >* curPtr = firstPtr;
firstPtr = firstPtr->nextPtr;
delete curPtr;
--len;
if( !len ) lastPtr = nullptr;
return true;
}
// else if reach here ...
return false;
}
//return boolean to signify if operation is successful
bool pop_back()
{
if( len )
{
Node< NODETYPE >* curPtr = firstPtr,
* prevPtr = nullptr;
while( curPtr->nextPtr )
{
prevPtr = curPtr;
curPtr = curPtr->nextPtr;
}
lastPtr = prevPtr;
if( lastPtr ) lastPtr->nextPtr = nullptr;
else firstPtr = nullptr;
delete curPtr;
--len;
//if( !len ) firstPtr = nullptr; // handled above //
}
// else if reach here ...
return false;
}
//returns true if SLList is empty
bool empty() const
{
return !len;
}
//display contents of SLList
void print() const
{
if( empty() ) //SLList is empty
{
#if debugSLL
std::cout << "The list is empty.\n\n";
#endif
return;
}
//continue by printing the list's contents
Node< NODETYPE >* currentPtr = firstPtr;
#if debugSLL
std::cout << "The list is: ";
#endif
while( currentPtr )
{
std::cout << currentPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
}
std::cout << std::endl;
}
// copy ctor ...
SLList< NODETYPE > ( const SLList< NODETYPE >& old )
{
firstPtr = lastPtr = nullptr;
len = 0;
//iterate over old ... and add copy of each to new list
Node< NODETYPE >* curPtr = old.firstPtr;
while( curPtr )
{
push_back( curPtr->data );
curPtr = curPtr->nextPtr;
}
}
// move copy ctor ...
SLList< NODETYPE > ( const SLList< NODETYPE >&& old )
{
firstPtr = old.firstPtr;
lastPtr = old.lastPtr;
len = old.len;
old.firstPtr = old.lastPtr = nullptr;
old.len = 0;
}
// overloaded assignment ...
SLList< NODETYPE >& operator = ( const SLList< NODETYPE >& old )
{
//check to see if the list is the same...
if( this != &old )
{
//first ensure the list being assigned to is empty ...
clear();
//iterate over old ... and add copy of each to new list
Node< NODETYPE >* curPtr = old.firstPtr;
while( curPtr )
{
push_back( curPtr->data );
curPtr = curPtr->nextPtr;
}
}
return *this;
}
// move overloaded assignment ...
SLList< NODETYPE >& operator = ( const SLList< NODETYPE >&& old )
{
//check to see if the list is the same...
if( this != &old )
{
clear();
firstPtr = old.firstPtr;
lastPtr = old.lastPtr;
len = old.len;
old.firstPtr = old.lastPtr = nullptr;
old.len = 0;
}
return *this;
}
// return a modifiable lvalue ...
NODETYPE& operator [] ( size_t index )
{
if( index >= len )
throw std::out_of_range( "Index out of range" ) ;
//is in valid range ...
size_t i = 0;
Node< NODETYPE >* curPtr = firstPtr;
while( i != index )
{
++i;
curPtr = curPtr->nextPtr;
}
return ( curPtr->data );
}
//returns non-modifiable rvalue
const NODETYPE& operator [] ( size_t index ) const
{
if( index >= len )
throw std::out_of_range( "Index out of range" ) ;
//is in valid range ...
size_t i = 0;
Node< NODETYPE >* curPtr = firstPtr;
while( i != index )
{
++i;
curPtr = curPtr->nextPtr;
}
return ( curPtr->data );
}
size_t size() const
{
return len;
}
void clear()
{
if( len ) //SLList is not empty
{
#if debugSLL
std::cout << "'clear()' called ... clearing nodes ...\n";
#endif
Node< NODETYPE > *curPtr = firstPtr;
Node< NODETYPE > *tmpPtr = nullptr;
while( curPtr )
{
tmpPtr = curPtr->nextPtr;
//std::cout << curPtr->data << '\n';
delete curPtr;
curPtr = tmpPtr;
--len;
}
firstPtr = lastPtr = nullptr;
}
}
class const_iterator;
class iterator : std::iterator< std::forward_iterator_tag, NODETYPE >
{
Node< NODETYPE >* ptr;
friend class SLList< NODETYPE >;
public:
iterator( Node< NODETYPE >* p=nullptr ) : ptr(p) {}
//const NODETYPE& operator * () const { return ptr->data; }
NODETYPE& operator * () { return ptr->data; }
iterator& operator ++ () { ptr = ptr->nextPtr; return *this; }
iterator& operator ++ ( int dummy ) { ptr = ptr->nextPtr; return *this; }
bool operator != ( const iterator& it ) const { return ptr != it.ptr; }
bool operator == ( const iterator& it ) const { return ptr == it.ptr; }
bool operator != ( const const_iterator& it ) const { return ptr != it.get_ptr(); }
bool operator == ( const const_iterator& it ) const { return ptr == it.get_ptr(); }
const Node< NODETYPE >* get_ptr() const { return ptr; }
} ;
iterator begin() { return iterator(firstPtr); }
iterator end() { return iterator(nullptr); }
class const_iterator : std::iterator< std::forward_iterator_tag,
NODETYPE, ptrdiff_t, const NODETYPE*, const NODETYPE& >
{
const Node< NODETYPE >* ptr;
friend class SLList< NODETYPE >;
public:
const_iterator( const Node< NODETYPE >* p=nullptr ) : ptr(p) {}
// Note: this next ctor is 'vital' ... // comment out and compile to see why? //
const_iterator( const iterator& i ) : ptr(i.ptr) {}
const NODETYPE& operator * () const { return ptr->data; }
//NODETYPE& operator * () { return ptr->data; }
const_iterator& operator ++ () { ptr = ptr->nextPtr; return *this; }
const_iterator operator ++ (int)
{ const_iterator tmp = *this; ++*this; return tmp; }
bool operator != ( const const_iterator& it ) const { return ptr != it.ptr; }
bool operator == ( const const_iterator& it ) const { return ptr == it.ptr; }
bool operator != ( const iterator& it ) const { return ptr != it.get_ptr(); }
bool operator == ( const iterator& it ) const { return ptr == it.get_ptr(); }
const Node< NODETYPE >* get_ptr() const { return ptr; }
} ;
const_iterator begin() const { return const_iterator(firstPtr); }
const_iterator end() const { return const_iterator(nullptr); }
private:
Node< NODETYPE >* firstPtr;
Node< NODETYPE >* lastPtr;
size_t len;
Node< NODETYPE >* getNewNode( const NODETYPE& value )
{
return new Node< NODETYPE >( value );
}
} ;
#endif
// testIfPalindromeViaStack.cpp // // 2014-08-14 //
// needs C++11 compiler //
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype> // for C++ ... but Note: C uses <ctype.h> //
#include "STACK.H"
using namespace std;
const string HEADER =
"This program tests if a string is a 'palindrome' ...\n";
const string ERROR_MSG =
"\nInput can not have any numeric characters"
", please try again.\n";
// some utilities used here ...
string takeInString( const string& msg = "" )
{
cout << msg << flush;
string val;
getline( cin, val );
return val;
}
int takeInChr( const std::string& msg = "" )
{
string reply = takeInString( msg );
if( reply.size() )
return reply[0];
// else ...
return 0;
}
bool more()
{
if( tolower( takeInChr( "More (y/n) ? " )) == 'n' )
return false;
// else ...
return true;
}
bool hasDigits( const string& toTest )
{
for( auto e : toTest )
if( isdigit(e) )
return true;
// else ... if reach here ...
return false;
}
int main()
{
cout << HEADER << endl;
do
{
string input;
for( ; ; )
{
input = takeInString( "Enter a line of text, without "
"any numbers in it, to be "
"tested:\n" );
if( !hasDigits( input ) )
break; // Ok good ... accept line with NO digits ... //
else
cout << ERROR_MSG << endl;
}
//convert all letters to lowercase ... using a [] lambda function here //
for_each( input.begin(), input.end(), [] (char& c) { c = tolower(c); } );
//after this is done, create two stacks ...
//'forward' and 'reverse', and ...
//use the STL list for the stack//
Stack< char > forwardStack,
backwardStack;
// now can populate 'forward' and 'backward' stacks
for( auto e : input )
// accept only alpha char's ...
if( isalpha(e) ) forwardStack.push( e );
std::cout << "Forward ... ";
forwardStack.print();
std::cout << "\n\n";
// now can populate ... 'backward' stacks
for( auto it = input.rbegin(); it != input.rend(); ++ it )
if( isalpha(*it) ) backwardStack.push( *it );
std::cout << "Backward ... ";
backwardStack.print();
std::cout << "\n\n";
//check to see if the stacks are equal
cout << "\n'" << input << "' is"
<< (forwardStack == backwardStack ? "" : " not")
<< " a palindrome.\n\n";
}
while( more() );
}
// STACK.H // // 2014-08-14 //
// needs a C++11 compiler //
// class definition using private inheritance of class SLList //
#ifndef Stack_h
#define Stack_h
#include "SLList.h"
template< typename STACKTYPE >
class Stack : private SLList< STACKTYPE >
{
public:
void push( const STACKTYPE& data )
{
this->push_front( data ) ;
}
const STACKTYPE& top() const
{
return this->top();
}
bool pop()
{
return this->pop_front();
}
bool operator == ( const Stack& other ) const
{
if( this->size() != other.size() ) return false;
// else ...
auto it = this->begin(), it2 = other.begin();
while( it != this->end() )
{
if( *it != *it2 ) return false;
++it, ++it2;
}
// if reach here ...
return true;
}
void print() const
{
std::cout << "The stack is: ";
/*
for( auto it = this->begin(); it != this->end(); ++it )
std::cout << *it << ' ';
*/
for( const auto e : *this )
std::cout << e << ' ';
}
} ;
#endif