diff options
Diffstat (limited to 'chapter7')
| -rw-r--r-- | chapter7/calc.cxx | 101 | ||||
| -rw-r--r-- | chapter7/calc.exe | bin | 0 -> 123748 bytes | |||
| -rw-r--r-- | chapter7/calc.o | bin | 0 -> 112994 bytes | |||
| -rw-r--r-- | chapter7/ch7files-stack.zip | bin | 0 -> 9653 bytes | |||
| -rw-r--r-- | chapter7/node2.h | 204 | ||||
| -rw-r--r-- | chapter7/node2.template | 128 | ||||
| -rw-r--r-- | chapter7/parens.cxx | 54 | ||||
| -rw-r--r-- | chapter7/parens.exe | bin | 0 -> 99658 bytes | |||
| -rw-r--r-- | chapter7/parens.o | bin | 0 -> 73250 bytes | |||
| -rw-r--r-- | chapter7/stack1.h | 79 | ||||
| -rw-r--r-- | chapter7/stack1.template | 41 | ||||
| -rw-r--r-- | chapter7/stack2.h | 78 | ||||
| -rw-r--r-- | chapter7/stack2.template | 59 |
13 files changed, 744 insertions, 0 deletions
diff --git a/chapter7/calc.cxx b/chapter7/calc.cxx new file mode 100644 index 0000000..795617a --- /dev/null +++ b/chapter7/calc.cxx @@ -0,0 +1,101 @@ +// FILE: calc.cxx
+// Basic calculator program that takes a fully parenthesized arithmetic
+// expression as input, and evaluates the arithmetic expression.
+// The purpose is to illustrate a fundamental use of stacks.
+
+#include <cctype> // Provides isdigit
+#include <cstdlib> // Provides EXIT_SUCCESS
+#include <cstring> // Provides strchr
+#include <iostream> // Provides cout, cin, peek, ignore
+#include <stack> // Provides the stack template class
+using namespace std;
+
+// PROTOTYPES for functions used by this demonstration program:
+double read_and_evaluate(istream& ins);
+// Precondition: The next line of characters in the istream ins is a fully
+// parenthesized arithmetic expression formed from non-negative numbers and
+// the four operations + - * /.
+// Postcondition: A line has been read from the istream ins, and this line has
+// been evaluated as an arithmetic expression. The value of the expression has
+// been returned by the function.
+
+void evaluate_stack_tops(stack<double>& numbers, stack<char>& operations);
+// Precondition: The top of the operations stack contains + - * or /, and the
+// numbers stack contains at least two numbers.
+// Postcondition: The top two numbers have been popped from the number stack,
+// and the top operation has been popped from the operation stack. The two
+// numbers have been combined using the operation (with the second number
+// popped as the left operand). The result of the operation has then been
+// pushed back onto the numbers stack.
+
+
+int main( )
+{
+ double answer;
+
+ cout << "Type a fully parenthesized arithmetic expression:" << endl;
+ answer = read_and_evaluate(cin);
+ cout << "That evaluates to " << answer << endl;
+
+ return EXIT_SUCCESS;
+}
+
+
+double read_and_evaluate(istream& ins)
+// Library facilities used: cstring, iostream, stack
+{
+ const char DECIMAL = '.';
+ const char RIGHT_PARENTHESIS = ')';
+
+ stack<double> numbers;
+ stack<char> operations;
+ double number;
+ char symbol;
+
+ // Loop continues while istream is not �bad� (tested by ins) and next character isn�t newline.
+ while (ins && ins.peek( ) != '\n')
+ {
+ if (isdigit(ins.peek( )) || (ins.peek( ) == DECIMAL))
+ {
+ ins >> number;
+ numbers.push(number);
+ }
+ else if (strchr("+-*/", ins.peek( )) != NULL)
+ {
+ ins >> symbol;
+ operations.push(symbol);
+ }
+ else if (ins.peek( ) == RIGHT_PARENTHESIS)
+ {
+ ins.ignore( );
+ evaluate_stack_tops(numbers, operations);
+ }
+ else
+ ins.ignore( );
+ }
+
+ return numbers.top( );
+}
+
+void evaluate_stack_tops(stack<double>& numbers, stack<char>& operations)
+// Library facilities used: stack
+{
+ double operand1, operand2;
+
+ operand2 = numbers.top( );
+ numbers.pop( );
+ operand1 = numbers.top( );
+ numbers.pop( );
+ switch (operations.top( ))
+ {
+ case '+': numbers.push(operand1 + operand2);
+ break;
+ case '-': numbers.push(operand1 - operand2);
+ break;
+ case '*': numbers.push(operand1 * operand2);
+ break;
+ case '/': numbers.push(operand1 / operand2);
+ break;
+ }
+ operations.pop( );
+}
diff --git a/chapter7/calc.exe b/chapter7/calc.exe Binary files differnew file mode 100644 index 0000000..6d9a552 --- /dev/null +++ b/chapter7/calc.exe diff --git a/chapter7/calc.o b/chapter7/calc.o Binary files differnew file mode 100644 index 0000000..d8095aa --- /dev/null +++ b/chapter7/calc.o diff --git a/chapter7/ch7files-stack.zip b/chapter7/ch7files-stack.zip Binary files differnew file mode 100644 index 0000000..2e25458 --- /dev/null +++ b/chapter7/ch7files-stack.zip diff --git a/chapter7/node2.h b/chapter7/node2.h new file mode 100644 index 0000000..a161683 --- /dev/null +++ b/chapter7/node2.h @@ -0,0 +1,204 @@ +// FILE: node2.h (part of the namespace main_savitch_6B)
+// PROVIDES: A template class for a node in a linked list, and list manipulation
+// functions. The template parameter is the type of the data in each node.
+// This file also defines a template class: node_iterator<Item>.
+// The node_iterator is a forward iterators with two constructors:
+// (1) A constructor (with a node<Item>* parameter) that attaches the iterator
+// to the specified node in a linked list, and (2) a default constructor that
+// creates a special iterator that marks the position that is beyond the end of a
+// linked list. There is also a const_node_iterator for use with
+// const node<Item>* .
+//
+// TYPEDEF for the node<Item> template class:
+// Each node of the list contains a piece of data and a pointer to the
+// next node. The type of the data (node<Item>::value_type) is the Item type
+// from the template parameter. The type may be any of the built-in C++ classes
+// (int, char, ...) or a class with a default constructor, an assignment
+// operator, and a test for equality (x == y).
+// NOTE:
+// Many compilers require the use of the new keyword typename before using
+// the expression node<Item>::value_type. Otherwise
+// the compiler doesn't have enough information to realize that it is the
+// name of a data type.
+//
+// CONSTRUCTOR for the node<Item> class:
+// node(
+// const Item& init_data = Item(),
+// node* init_link = NULL
+// )
+// Postcondition: The node contains the specified data and link.
+// NOTE: The default value for the init_data is obtained from the default
+// constructor of the Item. In the ANSI/ISO standard, this notation
+// is also allowed for the built-in types, providing a default value of
+// zero. The init_link has a default value of NULL.
+//
+// NOTE about two versions of some functions:
+// The data function returns a reference to the data field of a node and
+// the link function returns a copy of the link field of a node.
+// Each of these functions comes in two versions: a const version and a
+// non-const version. If the function is activated by a const node, then the
+// compiler choses the const version (and the return value is const).
+// If the function is activated by a non-const node, then the compiler choses
+// the non-const version (and the return value will be non-const).
+// EXAMPLES:
+// const node<int> *c;
+// c->link( ) activates the const version of link returning const node*
+// c->data( ) activates the const version of data returning const Item&
+// c->data( ) = 42; ... is forbidden
+// node<int> *p;
+// p->link( ) activates the non-const version of link returning node*
+// p->data( ) activates the non-const version of data returning Item&
+// p->data( ) = 42; ... actually changes the data in p's node
+//
+// MEMBER FUNCTIONS for the node<Item> class:
+// const Item& data( ) const <----- const version
+// and
+// Item& data( ) <----------------- non-const version
+// See the note (above) about the const version and non-const versions:
+// Postcondition: The return value is a reference to the data from this node.
+//
+// const node* link( ) const <----- const version
+// and
+// node* link( ) <----------------- non-const version
+// See the note (above) about the const version and non-const versions:
+// Postcondition: The return value is the link from this node.
+//
+// void set_data(const Item& new_data)
+// Postcondition: The node now contains the specified new data.
+//
+// void set_link(node* new_link)
+// Postcondition: The node now contains the specified new link.
+//
+// FUNCTIONS in the linked list toolkit:
+// template <class Item>
+// void list_clear(node<Item>*& head_ptr)
+// Precondition: head_ptr is the head pointer of a linked list.
+// Postcondition: All nodes of the list have been returned to the heap,
+// and the head_ptr is now NULL.
+//
+// template <class Item>
+// void list_copy
+// (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr)
+// Precondition: source_ptr is the head pointer of a linked list.
+// Postcondition: head_ptr and tail_ptr are the head and tail pointers for
+// a new list that contains the same items as the list pointed to by
+// source_ptr. The original list is unaltered.
+//
+// template <class Item>
+// void list_head_insert(node<Item>*& head_ptr, const Item& entry)
+// Precondition: head_ptr is the head pointer of a linked list.
+// Postcondition: A new node containing the given entry has been added at
+// the head of the linked list; head_ptr now points to the head of the new,
+// longer linked list.
+//
+// template <class Item>
+// void list_head_remove(node<Item>*& head_ptr)
+// Precondition: head_ptr is the head pointer of a linked list, with at
+// least one node.
+// Postcondition: The head node has been removed and returned to the heap;
+// head_ptr is now the head pointer of the new, shorter linked list.
+//
+// template <class Item>
+// void list_insert(node<Item>* previous_ptr, const Item& entry)
+// Precondition: previous_ptr points to a node in a linked list.
+// Postcondition: A new node containing the given entry has been added
+// after the node that previous_ptr points to.
+//
+// template <class Item>
+// size_t list_length(const node<Item>* head_ptr)
+// Precondition: head_ptr is the head pointer of a linked list.
+// Postcondition: The value returned is the number of nodes in the linked
+// list.
+//
+// template <class NodePtr, class SizeType>
+// NodePtr list_locate(NodePtr head_ptr, SizeType position)
+// The NodePtr may be either node<Item>* or const node<Item>*
+// Precondition: head_ptr is the head pointer of a linked list, and
+// position > 0.
+// Postcondition: The return value is a pointer that points to the node at
+// the specified position in the list. (The head node is position 1, the
+// next node is position 2, and so on). If there is no such position, then
+// the null pointer is returned.
+//
+// template <class Item>
+// void list_remove(node<Item>* previous_ptr)
+// Precondition: previous_ptr points to a node in a linked list, and this
+// is not the tail node of the list.
+// Postcondition: The node after previous_ptr has been removed from the
+// linked list.
+//
+// template <class NodePtr, class Item>
+// NodePtr list_search
+// (NodePtr head_ptr, const Item& target)
+// The NodePtr may be either node<Item>* or const node<Item>*
+// Precondition: head_ptr is the head pointer of a linked list.
+// Postcondition: The return value is a pointer that points to the first
+// node containing the specified target in its data member. If there is no
+// such node, the null pointer is returned.
+//
+// DYNAMIC MEMORY usage by the toolkit:
+// If there is insufficient dynamic memory, then the following functions throw
+// bad_alloc: the constructor, list_head_insert, list_insert, list_copy.
+
+#ifndef MAIN_SAVITCH_NODE2_H
+#define MAIN_SAVITCH_NODE2_H
+#include <cstdlib> // Provides NULL and size_t
+#include <iterator> // Provides iterator and forward_iterator_tag
+
+namespace main_savitch_6B
+{
+ template <class Item>
+ class node
+ {
+ public:
+ // TYPEDEF
+ typedef Item value_type;
+ // CONSTRUCTOR
+ node(const Item& init_data=Item( ), node* init_link=NULL)
+ { data_field = init_data; link_field = init_link; }
+ // MODIFICATION MEMBER FUNCTIONS
+ Item& data( ) { return data_field; }
+ node* link( ) { return link_field; }
+ void set_data(const Item& new_data) { data_field = new_data; }
+ void set_link(node* new_link) { link_field = new_link; }
+ // CONST MEMBER FUNCTIONS
+ const Item& data( ) const { return data_field; }
+ const node* link( ) const { return link_field; }
+ private:
+ Item data_field;
+ node *link_field;
+ };
+
+ // FUNCTIONS to manipulate a linked list:
+ template <class Item>
+ void list_clear(node<Item>*& head_ptr);
+
+ template <class Item>
+ void list_copy
+ (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);
+
+ template <class Item>
+ void list_head_insert(node<Item>*& head_ptr, const Item& entry);
+
+ template <class Item>
+ void list_head_remove(node<Item>*& head_ptr);
+
+ template <class Item>
+ void list_insert(node<Item>* previous_ptr, const Item& entry);
+
+ template <class Item>
+ std::size_t list_length(const node<Item>* head_ptr);
+
+ template <class NodePtr, class SizeType>
+ NodePtr list_locate(NodePtr head_ptr, SizeType position);
+
+ template <class Item>
+ void list_remove(node<Item>* previous_ptr);
+
+ template <class NodePtr, class Item>
+ NodePtr list_search(NodePtr head_ptr, const Item& target);
+
+}
+
+#include "node2.template"
+#endif
diff --git a/chapter7/node2.template b/chapter7/node2.template new file mode 100644 index 0000000..6b3a56a --- /dev/null +++ b/chapter7/node2.template @@ -0,0 +1,128 @@ +// FILE: node2.template
+// IMPLEMENTS: The functions of the node template class and the
+// linked list toolkit (see node2.h for documentation).
+//
+// NOTE:
+// Since node is a template class, this file is included in node2.h.
+// Therefore, we should not put any using directives in this file.
+//
+// INVARIANT for the node class:
+// The data of a node is stored in data_field, and the link in link_field.
+
+#include <cassert> // Provides assert
+#include <cstdlib> // Provides NULL and size_t
+
+namespace main_savitch_6B
+{
+ template <class Item>
+ void list_clear(node<Item>*& head_ptr)
+ // Library facilities used: cstdlib
+ {
+ while (head_ptr != NULL)
+ list_head_remove(head_ptr);
+ }
+
+ template <class Item>
+ void list_copy(
+ const node<Item>* source_ptr,
+ node<Item>*& head_ptr,
+ node<Item>*& tail_ptr
+ )
+ // Library facilities used: cstdlib
+ {
+ head_ptr = NULL;
+ tail_ptr = NULL;
+
+ // Handle the case of the empty list
+ if (source_ptr == NULL)
+ return;
+
+ // Make the head node for the newly created list, and put data in it
+ list_head_insert(head_ptr, source_ptr->data( ));
+ tail_ptr = head_ptr;
+
+ // Copy rest of the nodes one at a time, adding at the tail of new list
+ source_ptr = source_ptr->link( );
+ while (source_ptr != NULL)
+ {
+ list_insert(tail_ptr, source_ptr->data( ));
+ tail_ptr = tail_ptr->link( );
+ source_ptr = source_ptr->link( );
+ }
+ }
+
+ template <class Item>
+ void list_head_insert(node<Item>*& head_ptr, const Item& entry)
+ {
+ head_ptr = new node<Item>(entry, head_ptr);
+ }
+
+ template <class Item>
+ void list_head_remove(node<Item>*& head_ptr)
+ {
+ node<Item> *remove_ptr;
+
+ remove_ptr = head_ptr;
+ head_ptr = head_ptr->link( );
+ delete remove_ptr;
+ }
+
+ template <class Item>
+ void list_insert(node<Item>* previous_ptr, const Item& entry)
+ {
+ node<Item> *insert_ptr;
+
+ insert_ptr = new node<Item>(entry, previous_ptr->link( ));
+ previous_ptr->set_link(insert_ptr);
+ }
+
+ template <class Item>
+ std::size_t list_length(const node<Item>* head_ptr)
+ // Library facilities used: cstdlib
+ {
+ const node<Item> *cursor;
+ std::size_t answer;
+
+ answer = 0;
+ for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
+ ++answer;
+
+ return answer;
+ }
+
+ template <class NodePtr, class SizeType>
+ NodePtr list_locate(NodePtr head_ptr, SizeType position)
+ // Library facilities used: cassert, cstdlib
+ {
+ NodePtr cursor;
+ SizeType i;
+
+ assert(0 < position);
+ cursor = head_ptr;
+ for (i = 1; (i < position) && (cursor != NULL); ++i)
+ cursor = cursor->link( );
+ return cursor;
+ }
+
+ template <class Item>
+ void list_remove(node<Item>* previous_ptr)
+ {
+ node<Item> *remove_ptr;
+
+ remove_ptr = previous_ptr->link( );
+ previous_ptr->set_link(remove_ptr->link( ));
+ delete remove_ptr;
+ }
+
+ template <class NodePtr, class Item>
+ NodePtr list_search(NodePtr head_ptr, const Item& target)
+ // Library facilities used: cstdlib
+ {
+ NodePtr cursor;
+
+ for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
+ if (target == cursor->data( ))
+ return cursor;
+ return NULL;
+ }
+}
diff --git a/chapter7/parens.cxx b/chapter7/parens.cxx new file mode 100644 index 0000000..c388ed6 --- /dev/null +++ b/chapter7/parens.cxx @@ -0,0 +1,54 @@ +// FILE: parens.cxx
+// A small demonstration program for a stack.
+#include <cstdlib> // Provides EXIT_SUCCESS
+#include <iostream> // Provides cin, cout
+#include <stack> // Provides stack
+#include <string> // Provides string
+using namespace std;
+
+// PROTOTYPE for a function used by this demonstration program
+bool is_balanced(const string& expression);
+// Postcondition: A true return value indicates that the parentheses in the
+// given expression are balanced. Otherwise, the return value is false.
+
+int main( )
+{
+ string user_input;
+
+ cout << "Type a string with some parentheses:\n";
+ getline(cin, user_input);
+
+ if (is_balanced(user_input))
+ cout << "Those parentheses are balanced.\n";
+ else
+ cout << "Those parentheses are not balanced.\n";
+
+ cout << "That ends this balancing act.\n";
+ return EXIT_SUCCESS;
+}
+
+bool is_balanced(const string& expression)
+// Library facilities used: stack, string
+{
+ // Meaningful names for constants
+ const char LEFT_PARENTHESIS = '(';
+ const char RIGHT_PARENTHESIS = ')';
+
+ stack<char> store; // Stack to store the left parentheses as they occur
+ string::size_type i; // An index into the string
+ char next; // The next character from the string
+ bool failed = false; // Becomes true if a needed parenthesis is not found
+
+ for (i = 0; !failed && (i < expression.length( )); ++i)
+ {
+ next = expression[i];
+ if (next == LEFT_PARENTHESIS)
+ store.push(next);
+ else if ((next == RIGHT_PARENTHESIS) && (!store.empty( )))
+ store.pop( ); // Pops the corresponding left parenthesis.
+ else if ((next == RIGHT_PARENTHESIS) && (store.empty( )))
+ failed = true;
+ }
+
+ return (store.empty( ) && !failed);
+}
diff --git a/chapter7/parens.exe b/chapter7/parens.exe Binary files differnew file mode 100644 index 0000000..094d044 --- /dev/null +++ b/chapter7/parens.exe diff --git a/chapter7/parens.o b/chapter7/parens.o Binary files differnew file mode 100644 index 0000000..a06a15f --- /dev/null +++ b/chapter7/parens.o diff --git a/chapter7/stack1.h b/chapter7/stack1.h new file mode 100644 index 0000000..d6ea8fe --- /dev/null +++ b/chapter7/stack1.h @@ -0,0 +1,79 @@ +// FILE: stack1.h (part of the namespace main_savitch_7A)
+// TEMPLATE CLASS PROVIDED: stack<Item>
+//
+// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the stack<Item> class:
+// The template parameter, Item, is the data type of the items in the stack,
+// also defined as stack<Item>::value_type. It may be any of the C++ built-in
+// types (int, char, etc.), or a class with a default constructor, a copy
+// constructor, and an assignment operator. The definition
+// stack<Item>::size_type is the data type of any variable that keeps track of
+// how many items are in a stack. The static const CAPACITY is the
+// maximum capacity of a stack for this first stack implementation.
+// NOTE:
+// Many compilers require the use of the new keyword typename before using
+// the expressions stack<Item>::value_type and stack<Item>::size_type.
+// Otherwise the compiler doesn't have enough information to realize that it
+// is the name of a data type.
+//
+// CONSTRUCTOR for the stack<Item> template class:
+// stack( )
+// Postcondition: The stack has been initialized as an empty stack.
+//
+// MODIFICATION MEMBER FUNCTIONS for the stack<Item> class:
+// void push(const Item& entry)
+// Precondition: size( ) < CAPACITY.
+// Postcondition: A new copy of entry has been pushed onto the stack.
+//
+// Item pop( )
+// Precondition: size( ) > 0.
+// Postcondition: The top item of the stack has been removed.
+//
+// CONSTANT MEMBER FUNCTIONS for the stack<Item> class:
+// bool empty( ) const
+// Postcondition: Return value is true if the stack is empty.
+//
+// size_type size( ) const
+// Postcondition: Return value is the total number of items in the stack.
+//
+// Item top( )
+// Precondition: size( ) > 0.
+// Postcondition: The return value is the top item of the stack but the
+// stack is unchanged. This differs slightly from the STL stack (where
+// the top function returns a reference to the item on top of the stack).
+//
+// VALUE SEMANTICS for the stack<Item> class:
+// Assignments and the copy constructor may be used with stack<Item>
+// objects.
+
+#ifndef MAIN_SAVITCH_STACK1_H
+#define MAIN_SAVITCH_STACK1_H
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_7A
+{
+ template <class Item>
+ class stack
+ {
+ public:
+ // TYPEDEFS AND MEMBER CONSTANT -- See Appendix E if this fails to compile.
+ typedef std::size_t size_type;
+ typedef Item value_type;
+ static const size_type CAPACITY = 30;
+ // CONSTRUCTOR
+ stack( ) { used = 0; }
+ // MODIFICATION MEMBER FUNCTIONS
+ void push(const Item& entry);
+ void pop( );
+ // CONSTANT MEMBER FUNCTIONS
+ bool empty( ) const { return (used == 0); }
+ size_type size( ) const { return used; }
+ Item top( ) const;
+ private:
+ Item data[CAPACITY]; // Partially filled array
+ size_type used; // How much of array is being used
+ };
+}
+
+#include "stack1.template" // Include the implementation.
+#endif
+
diff --git a/chapter7/stack1.template b/chapter7/stack1.template new file mode 100644 index 0000000..ad311c2 --- /dev/null +++ b/chapter7/stack1.template @@ -0,0 +1,41 @@ +// FILE: stack1.template
+// TEMPLATE CLASS IMPLEMENTED: stack<Item> (see stack1.h for documentation)
+// This file is included in the header file, and not compiled separately.
+// INVARIANT for the stack class:
+// 1. The number of items in the stack is in the member variable used.
+// 2. The actual items of the stack are stored in a partially-filled
+// array data[0]..data[used-1]. The stack elements appear from the
+// bottom (at data[0]) to the top (at data[used-1]).
+
+#include <cassert> // Provides assert
+
+namespace main_savitch_7A
+{
+ template <class Item>
+ const typename stack<Item>::size_type stack<Item>::CAPACITY;
+
+ template <class Item>
+ void stack<Item>::push(const Item& entry)
+ // Library facilities used: cassert
+ {
+ assert(size( ) < CAPACITY);
+ data[used] = entry;
+ ++used;
+ }
+
+ template <class Item>
+ void stack<Item>::pop( )
+ // Library facilities used: cassert
+ {
+ assert(!empty( ));
+ --used;
+ }
+
+ template <class Item>
+ Item stack<Item>::top( ) const
+ // Library facilities used: cassert
+ {
+ assert(!empty( ));
+ return data[used-1];
+ }
+}
diff --git a/chapter7/stack2.h b/chapter7/stack2.h new file mode 100644 index 0000000..739f1ad --- /dev/null +++ b/chapter7/stack2.h @@ -0,0 +1,78 @@ +// FILE: stack2.h (part of the namespace main_savitch_7B)
+// TEMPLATE CLASS PROVIDED: stack<Item> (a stack of items)
+// The template parameter, Item, is the data type of the items in the stack,
+// also defined as stack<Item>::value_type.
+// It may be any of the C++ built-in types (int, char, etc.), or a class
+// with a default constructor, a copy constructor, and an assignment
+// operator. The definition stack<Item>::size_type is the data type of
+// any variable that keeps track of how many items are in a stack.
+//
+// CONSTRUCTOR for the stack<Item> template class:
+// stack( )
+// Postcondition: The stack has been initialized as an empty stack.
+//
+// MODIFICATION MEMBER FUNCTIONS for the stack<Item> class:
+// void push(const Item& entry)
+// Precondition: size( ) < CAPACITY.
+// Postcondition: A new copy of entry has been pushed onto the stack.
+//
+// Item pop( )
+// Precondition: size( ) > 0.
+// Postcondition: The top item of the stack has been removed.
+//
+// CONSTANT MEMBER FUNCTIONS for the stack<Item> class:
+// bool empty( ) const
+// Postcondition: Return value is true if the stack is empty.
+//
+// size_type size( ) const
+// Postcondition: Return value is the total number of items in the stack.
+//
+// Item top( )
+// Precondition: size( ) > 0.
+// Postcondition: The return value is the top item of the stack (but the
+// stack is unchanged. This differs slightly from the STL stack (where
+// the top function returns a reference to the item on top of the stack).
+//
+// VALUE SEMANTICS for the stack<Item> class:
+// Assignments and the copy constructor may be used with stack<Item>
+// objects.
+//
+// DYNAMIC MEMORY USAGE by the stack<Item> template class:
+// If there is insufficient dynamic memory, then the following functions
+// throw bad_alloc:
+// the copy constructor, push, and the assignment operator.
+
+#ifndef MAIN_SAVITCH_STACK2_H
+#define MAIN_SAVITCH_STACK2_H
+#include <cstdlib> // Provides NULL and size_t
+#include "node2.h" // Node template class from Figure 6.5 on page 308
+
+namespace main_savitch_7B
+{
+ template <class Item>
+ class stack
+ {
+ public:
+ // TYPEDEFS
+ typedef std::size_t size_type;
+ typedef Item value_type;
+ // CONSTRUCTORS and DESTRUCTOR
+ stack( ) { top_ptr = NULL; }
+ stack(const stack& source);
+ ~stack( ) { list_clear(top_ptr); }
+ // MODIFICATION MEMBER FUNCTIONS
+ void push(const Item& entry);
+ void pop( );
+ void operator =(const stack& source);
+ // CONSTANT MEMBER FUNCTIONS
+ size_type size( ) const
+ { return main_savitch_6B::list_length(top_ptr); }
+ bool empty( ) const { return (top_ptr == NULL); }
+ Item top( ) const;
+ private:
+ main_savitch_6B::node<Item> *top_ptr; // Points to top of stack
+ };
+}
+
+#include "stack2.template" // Include the implementation
+#endif
diff --git a/chapter7/stack2.template b/chapter7/stack2.template new file mode 100644 index 0000000..e02d827 --- /dev/null +++ b/chapter7/stack2.template @@ -0,0 +1,59 @@ +// FILE: stack2.template
+// TEMPLATE CLASS IMPLEMENTED: stack<Item> (see stack2.h for documentation)
+// This file is included in the header file, and not compiled separately.
+// INVARIANT for the stack class:
+// 1. The items in the stack are stored in a linked list, with the top of the
+// stack stored at the head node, down to the bottom of the stack at the
+// final node.
+// 2. The member variable top_ptr is the head pointer of the linked list.
+
+#include <cassert> // Provides assert
+#include "node2.h" // Node template class
+
+namespace main_savitch_7B
+{
+ template <class Item>
+ stack<Item>::stack(const stack<Item>& source)
+ // Library facilities used: node2.h
+ {
+ main_savitch_6B::node<Item> *tail_ptr; // Needed for argument of list_copy
+
+ list_copy(source.top_ptr, top_ptr, tail_ptr);
+ }
+
+ template <class Item>
+ void stack<Item>::push(const Item& entry)
+ // Library facilities used: node2.h
+ {
+ list_head_insert(top_ptr, entry);
+ }
+
+ template <class Item>
+ void stack<Item>::pop( )
+ // Library facilities used: cassert, node2.h
+ {
+ assert(!empty( ));
+ list_head_remove(top_ptr);
+ }
+
+ template <class Item>
+ void stack<Item>::operator =(const stack<Item>& source)
+ // Library facilities used: node2.h
+ {
+ main_savitch_6B::node<Item> *tail_ptr; // Needed for argument of list_copy
+
+ if (this == &source) // Handle self-assignment
+ return;
+
+ list_clear(top_ptr);
+ list_copy(source.top_ptr, top_ptr, tail_ptr);
+ }
+
+ template <class Item>
+ Item stack<Item>::top( ) const
+ // Library facilities used: cassert
+ {
+ assert(!empty( ));
+ return top_ptr->data( );
+ }
+}
|