The quiz is closed book, closed notes, no electronic devices permitted.
It consists of a single question worth 10 marks.
You have 50 minutes to complete the question.

Question 1:

[Part a: 3 marks] The definition of the stack class below is incomplete - it shows all the methods, but none of the private struct definitions or data fields. Provide appropriate content for the private section of the class definition, assuming a linked-list style of stack implementation is to be used.

SAMPLE SOLUTION: private: struct Node { char bracket; int lineNum; Node *next; } *top; };

[Part b: 4 marks] Using your answer for part (a) above, implement the constructor, push, and pop methods for the stack.

SAMPLE SOLUTION: Stack::Stack() { top = NULL; } bool Stack::push(char c, int line) { Node *n = new Node; if (n == NULL) return false; n->bracket = c; n->lineNum = line; n->next = top; return true; } bool Stack::pop(char &c, int &line) { if (top == NULL) return false; c = n->bracket; line = n->lineNum; Node *victim = top; top = top->next; delete victim; return true; }

[Part c: 3 marks] Study the bracket-checking function provided below (which assumes the availability of the correctly-implemented stack class), then answer the following two questions:
(i) Why is the second end of file test necessary in the function - the if (!fpin.eof()) that appears inside the body of the while loop?

SAMPLE SOLUTION: The second eof test is necessary because otherwise we might process the last character in the file twice. This would be important iff the last character in the file was a closing bracket, since we would attempt to pop/match with it twice instead of once.


(ii) What would be the impact on the function behaviour if we replaced the statement fpin.get(c); with the statement fpin >> c;?

SAMPLE SOLUTION: If we used fpin >> c; instead of fpin.get(c); it would always skip whitespace, including the newline character. Since we use the newline character to keep track of which line number we are on, the function's error messages would always say all brackets were on line 1.

class Stack {
   // a stack of bracket data: each entry contains the
   //    the bracket type and a line number
   public:
      Stack();         // initializes an empty stack
     ~Stack();         // deallocates the stack
      bool isempty();  // true iff the stack is empty

      // push bracket info onto the top of the stack
      bool push(char c, int line);  

      // pop bracket info off the top of the stack
      bool pop(char &c, int &line);  

   private:
      // ... to be done by you ...
};
// Check the file to ensure that all brackets { } ( )     
//     are properly matched/nested
// Display appropriate error messages if errors are detected,
//     return true if the file is readable and the bracketing
//     is valid, false otherwise
bool checkBrackets(char filename[])
{
   Stack S;      // stack to track open brackets
   char c, c2;   // characters being processed
   int line = 1; // track the current line number
   bool valid = true;  // track if the file still appears to be valid

   // try opening the file
   ifstream fpin;
   fpin.open(filename);
   if (fpin.fail()) return false;

   // process the file one character at a time
   while (valid && !fpin.eof()) {

      // get the next character and check for end of file
      fpin.get(c);
      if (!fpin.eof()) {

         // if it is an opening bracket then push it on the stack
         if ((c == '{') || (c == '(')) {
            if (!S.push(c, line)) valid = false;
         }

         // if it is a closing bracket then pop the top bracket off
         //    the stack if possible (otherwise it is an error) 
         else if ((c == '}') || (c == ')')) {
             if (S.isempty()) {
                cout << "Found a closing " << c << " from line " << line;
                cout << " when no brackets were open\n";
                valid = false;
             } else {
                // lookup the stored bracket and line it was on    
                int line2;
                if (!S.pop(c2, line2)) valid = false;
                else {
                   if ((c == '}') && (c2 != '{')) valid = false;
                   if ((c == ')') && (c2 != '(')) valid = false;
                   if (!valid) {
                      cout << "Bracket mismatch: " << c2 << " from line ";
                      cout << line2 << " and " << c << " " << line << endl;
                   }
                }
             }
         }
         // if it is a new line adjust the line number 
         else if (c == '\n')  line++;
      }
   }

   // once we have read every character in the file,
   // make sure there are no brackets left unclosed
   if (valid && !S.isempty()) {
      cout << "There were unclosed brackets left when the file ended\n";  
      valid = false;
   }

   // close the file and return the final result
   fpin.close();
   return valid;
}