CS 2620 Assignment #6 Summer 2004

How to handin.
Points : 30
Weight : 3%
Due : Monday Jun 7, 2004 @11:00 pm
Note : Late assignments will be accepted only with the instructor's pre-approval.

1. [15] Linked Lists
   The single linked list implemented in lecture has an inefficiency when removing an item from the back of the list or removing or inserting an item using the iterator, in that it must always start at the head of the list and move forward until the item previous to the current one is found, before the operation can be done. One common method of eliminating this inefficiency is to implement the list as a double linked list. In this implementation, the node class has a prevPtr (in addition to the nextPtr) which points to the node which precedes it. Rewrite the linked list class so that it is doubly linked. The implementation for the single-linked circular list with a dummy head may be found in $L/lect/jun01/slist.

   NOTE: the interface will not change, only the implementation and private members.

2. Stacks
   
   1. [5] In class we developed a queue class by using restrictive inheritance from the list class. Develop a stack class using restrictive inheritance from the list class. Use the single linked circlular list found in $L/lect/jun01/slist.

      The stack needs the following methods:

      1. isEmpty(): Return true if stack is empty, return false otherwise
      2. top() : Return top element of stack
      3. push(item): Insert item on to the stack
      4. pop() : Delete top element from stack

   2. [10] Balancing Symbols: One of the frequent sources of syntax errors is the presence of unbalanced symbols in our source code. Unbalanced symbols typically causes a compiler to spill out many lines of diagnostics without identifying the real error. A useful tool in this situation is a program that checks whether everything (e.g. braces, comment starters etc.) is balanced. For simplicity, we will just check for balancing of parentheses ((,)), brackets ([, ]), and braces ({, }). We can use a stack to check (C++ source) a data file for unbalanced symbols as outlined below:

      Make an empty stack. For each character read from the data file if the character is an opening symbol, push it onto stack If it is a closing symbol, then if stack is empty report an error. Otherwise, pop the stack. If the symbol popped is not the corresponding opening symbol, then report an error. At the end of the data file, if the stack is not empty report an error.

      Write a program that checks a user-supplied C++ source file for unbalanced symbols using the algorithm above and your stack class. Test your program thoroughly.

University of Lethbridge Home Page