Courses/CS 2124/Lab Manual/The Stack and the Class Template

From A-State Computer Science Wiki
Jump to: navigation, search

Introduction

In this exercise a stack data structure is developed from the linked list data structure of a previous laboratory.

The Integer Node Class

Consider the following class definition for an integer node object for use as an element of a list or a stack.

class IntNode {
public:
    IntNode( int new_value );
    int      get_data( ) const;
    void     set_next( IntNode* new_next );
    IntNode* get_next( ) const;
    void     debug_write( ostream& outfile ) const;

private:
    int      payload;
    IntNode* next = nullptr;
};

ostream& operator<<( ostream& outfile, const IntNode& node );

Note that there is nothing in this definition which mentions a list or a stack; this node could be part of either or even some other data structure. Like the list class item constructor last week, the constructor for the integer node class should copy the formal parameter into the private data field and initialize the next pointer to nullptr, the null pointer in C++; write this constructor now. Also as before, methods get_data(), set_next() and get_next() are access functions for the private data defined in the class; write these methods now.

A simple write method would display only the data in the node itself. Method debug_write() is so named as it will also display the data in the node indicated by pointer next. For example, if the node containing 203 is followed by the node containing 407, the method should generate 203(->407) as output. Use the string " / " to indicate a nullptr. Create debug_write() and corresponding overloaded operator << now.

Begin function main() with the following lines; execute the program to see that the node methods and overloaded operator are working properly.

cout << "The Stack & the Class Template (in-lab portion)\n";
IntNode int_item_1( 101 );
IntNode int_item_2( 212 );
cout << "test nodes: " << int_item_1 << ' ' << int_item_2 << "\n";
int_item_1.set_next( &int_item_2 );
cout << "test next:  " << int_item_1 << ' ' << int_item_2 << "\n\n";

The following output should result from the execution of the above fragment.

The Stack & the Class Template (in-lab portion)
test nodes: 101(-> / ) 212(-> / )
test next:  101(->212) 212(-> / )

The List Class

The class definition for a list of integers presented here is similar to what you have done for previous assignments.

class IntList {
public:
    IntList( ) = default;
    ~IntList( );
    bool is_empty( ) const;
    void add_front( int newData );
    int  remove_front( );
    void write( ostream& outfile ) const;

    // disallow copies by marking the following as "delete":
    IntList( const IntList& ) = delete;
    IntList& operator=( const IntList& ) = delete;

private:
    IntNode* head = nullptr;
};
ostream& operator<<( ostream& outfile, const IntList& list );

C++11 attribute initialization, is used to be certain that the head pointer is always initialized to nullptr when the list is created; thus, there is no need to define any constructor. The pointer to the list’s tail node is omitted here for simplification, as there will be no need for it when the list is used in a stack. Copy construction and assignment are disallowed by placing those prototypes in the private access section (and not implementing them). The destructor for the class should deallocate all nodes currently contained in the list. Write the destructor now.


Labcheckpoint.png FOR IN-LAB CREDIT: Explain to the lab instructor why a tail pointer would be needed were the list to be used to implement a queue.


Method is_empty() acts to test the value in the private data’s head pointer for equality with nullptr; write this method now.

Method add_front() should allocate storage for a new IntNode, passing its argument to the IntNode constructor. Write this method now.

Method write should simply iterate through the list, invoking the << operator for each node in turn. This method can begin by setting a pointer current to the head of the list. The body of a loop can print the current integer node’s data, then update the current pointer to the current’s next pointer; while the current pointer is not nullptr, the end of the list has not been reached. Write this method now and overload the << operator to invoke it.

Add the following lines to function main(); execute the program to see that the list methods and functions are working properly.

IntList list1;
list1.add_front( 101 );
list1.add_front( 212 );
list1.add_front( 323 );
list1.add_front( 434 );
cout << "test list 101/212/323/434:\n" << list1 << "\n\n";

The preceding program segment should generate the following output.

test list 101/212/323/434:
434(->323)
323(->212)
212(->101)
101(-> / )

Method remove_front() should reverse the steps of add_front(). When the list is empty, there is nothing to remove. When this circumstance occurs, the remove method should throw an instance of std::length_error with the message string “Empty list.” otherwise, copy the data of the list’s head item into the method’s reference parameter, remove the head item from the list (making its successor the new head), free up the memory of the removed head, and return the value that was in the node being removed. Note that a memory leak is said to occur if the memory is not freed. Write method remove_front() now.

Add the following lines to function main().

int list_data_1;
try {
   list_data_1 = list1.remove_front( );
   cout << "test list remove #1: " << list_data_1 << endl;
} 
catch ( const std::length_error& ) { 
   cout << "test list remove #1 failed\n"; 
}

cout << "list is now:\n" << list1 << "\n";
int list_data_2;
try {
   list_data_2 = list1.remove_front( );
   cout << "test list remove #2: " << list_data_2 << endl;
} 
catch ( const std::length_error& ) { 
   cout << "test list remove #2 failed\n"; 
}
cout << "list is now:\n" << list1 << "\n\n";

Execute the program to verify that method remove_front() is working properly; the following output should be displayed.

test list remove #1: 434
list is now:
323(->212)
212(->101)
101(-> / )

test list remove #2: 323
list is now:
212(->101)
101(-> / )

The Stack Class

In this section a stack data structure is constructed to manipulate data in a last-in first-out (LIFO) fashion, as with a stack of trays in a cafeteria. Consider the following class definition for a stack object.

class IntStack {
public:
    bool is_empty( ) const;
    void push( int operand );
    int  pop( );
    void debug_write( ostream& outfile ) const;

private:
    IntList list;
};
ostream& operator<<( ostream& outfile, const IntStack& stack );

Observe that this class lists no constructor prototype. Since the private data for the class consists of an instance of another class (whose constructor will in turn initialize it), there is nothing to be done explicitly in the constructor of a stack.

Methods is_empty(), push(), pop() and debug_write() each invoke the corresponding method of attribute list; write these trivial methods now, overloading operator << to call debug_write(). Since the stack data structure privately contains a list data structure, the user is unaware of any other capabilities of the list. In fact, the user will be unaware (and unaffected) if the list is replaced with some other data structure, such as an array; only the stack method implementations would be changed.

Add the following lines to function main(); execute the program to see that the stack object methods and functions are working properly.

IntStack stack;
stack.push( 101 );
stack.push( 212 );
stack.push( 323 );
stack.push( 434 );
cout << "test stack 101/212/323/434:\n" << stack << endl;

int stack_data_1;
try {
    stack_data_1 = stack.pop( );
    cout << "test stack pop #1: " << stack_data_1 << endl;
}
catch ( const std::length_error& ) {
    cout << "test stack pop #1 failed\n"; 
}

cout << "stack is now:\n" << stack << endl;

int stack_data_2;
try {
    stack_data_2 = stack.pop( );
    cout << "test stack pop #2: " << stack_data_2 << endl;
}
catch ( const std::length_error& ) {
    cout << "test stack pop #2 failed\n"; 
}
cout << "stack is now:\n" << stack << endl;

The following results should be displayed upon executing this program fragment.

test stack 101/212/323/434:
434(->323)
323(->212)
212(->101)
101(-> / )

test stack pop #1: 434
stack is now:
323(->212)
212(->101)
101(-> / )

test stack pop #2: 323
stack is now:
212(->101)
101(-> / )


Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate your stack for the lab instructor.


Stack Example: Postfix Evaluation

The stack is now applied to the solution of a practical problem. A postfix expression is written with the operators following their operands, rather than separating their operands as they do in the more common infix expression. The simple infix expression ’‘2 + 3’’ is written as the postfix expression ’‘2 3 +.’’ The expression ’‘(2 + 3) * 5’’ is written as ’‘2 3 + 5 *.’’ The expression ’‘5 * 2 + 3’’ is written ’‘5 2 * 3 +,’’ while the similar expression ’‘5 * (2 + 3)’’ is written ’‘5 2 3 + *.’’ A postfix operator is applied to the two values immediately to its left. Note that postfix expressions do not require parentheses to denote order of evaluation.

A stack may be used to store the data of a postfix expression until an operator is encountered, at which point the two topmost stack items are removed (popped) from the stack for evaluation; the result is then placed back on the stack. When the end of the expression is reached, the top of the stack represents the value of the expression. If the stack has other than exactly one item remaining at this point, the expression was not well-formed; this is also the case if the stack becomes empty before the expression evaluation is complete.

Create the file ’‘stack_calc.txt’’ and place any one of the postfix examples given above, such as 2 3 + 5 *, in it. Be sure that the cursor will not move past the last character on the line; otherwise, the end of the expression may not be detected correctly.

Add the following code to function main(). Note that the body of the while loop is empty here.

IntStack postfix_stack;
ifstream infile( "stack_calc.txt", std::ios::in );
if ( !infile )
    cout << "error opening data file!\n";
else {
    bool stackError = false;  // true if stack empties too soon or unexpected operator
    while ( infile.good( ) && !stackError ) {
        string token;
        infile >> token;


        // BODY OF LOOP GOES HERE
        

        cout << "stack is now \n" << postfix_stack << "\n\n";
    }  // end of "read file" loop
    if ( stackError )
        cout << "invalid expression!!\n";
    else {
        try {
            int result = postfix_stack.pop( );
            cout << "expression evaluates to " << result << endl;
        } 
        catch ( const std::length_error& ) {
            cout << "final pop of IntStack failed\n";
        }
        if ( postfix_stack.is_empty( ) ){
            cout << "OK: empty stack => well-formed postfix expression!\n";
        }
        else {  // stack is not empty: there were too many numbers in the input!
            cout << "ERROR: non-empty stack => illegal postfix "
                 << "expression!\n";
        }
    }
}

The body of the while loop must process the input string stored in token, a variable name commonly used when parsing input data. This character string will either be a number or an operator; if the first character of token is numeric, the entire string may be assumed to represent a number. The <string> library method std::stoi() converts a std::string into an integer. Begin the body of the loop with an if control structure to check for a numeric token; if this should be the case, push the integer equivalent onto the postfix stack. Write this if control structure now.

If the token string is not a number, it must be an operator; for this example, consider only +, -, * and /. For any operator, two values are popped off of the stack and the operator is applied to them; the result is pushed back onto the stack. An if-else chain (or switch) control structure can be used to perform the correct operation. The algorithm should handle the exception that could be thrown by either pop operation, and the selection control structure should include a default to handle operators other than +, -, * and /. Write this code now as the body of the else corresponding to the if control structure of the preceding paragraph.

Execute the program to be sure that it evaluates legal postfix expressions correctly. Test the code with some moderately complex expressions. Be careful non-commutative operators - and / — for example, the expression “3 2 -” must evaluate to 1, not -1.


Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate the program with one such expression for the lab instructor.


Submit your finished project.