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