CSCI 161 Makeup Quiz: Spring 2013
Sample Solutions

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:


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; }