1. An expression is syntactically correct if it has the following forms: an expression followed by an optional operator and another expression

   expression = expression [ operator expression ]

   or just a number.

   expression = number

   A number is a digit followed by digits

   number = digit digits

   and a digit and digits are as you'd expect

   digit = 0 | 1 | . . . | 9
   digits = digit digits | nothing

   The operators are

   operator = + | - | * | /

   Write an algorithm that accepts a string containing an expression and determines if the expression is syntactically correct. The algorithm should ignore all white-space characters; all other characters should not be ignored.

   ---

   

   This recognizer assumes spaces in numbers are o.k. (which is a nice feature; it lets you write things like 1 000 000). If spaces in numbers aren't o.k., the recognizer would have another state off the unlabled state with a transition on spaces; the new state would go either to Start or Error (or stay in the same state).

   ---

2. Describe a conservation property and a test for it that is applicable to doubly-linked lists. You do not have to write code; just describe the algorithm.

   ---

   One possibility is the number of links in the list: the number of links pointed to in the forward direction should be equal to the number of links pointed to in the backwards direction. A test for this would make a round trip along the list, first in the forward direction and then in the backward direction, keeping count as it goes. When the code returns to its starting point, the count should be zero (or whatever value it started with).

   This test could fail to find link errors if the errors were symmetric in both directions:

   

   This kind of link error can be caught by another conservation test: the predecessor of a node's successor should be the node itself. The test word traverse the list, in one directly only, checking at each node to see if this == this->next->last. The test applies to of all nodes in a doubly-linked list if the list has both a dummy head and tail; otherwise, the test would have to treat one or both ends of the list as a special case.

   ---

3. Give three boundary conditions relevant to the conservation test you described in the previous question. Explain why boundary conditions are relevant.

   ---

   There are huge number of boundary conditions for doubly-linked list. Using the general rule of thumb "zero, one, many", the empty list, the list containing two elements and the list containing more than four elements would be applicable to the link-counting test. The testing empty list is always relevant, the two-element list is the smallest non-trivial, non-empty list, and a list of more than three elements would make sure link traversal is working well.

   With respect to the predecessor-successor test, the empty list, the list of one element, and the list of two elements are relevant.

   ---

4. Explain how Cargill said to handle the difference in value and behavior between parent and child classes.

   ---

   Differences in value between two (or more) classes should be handled by member variables inherited from the parent class and initialized as desired by each class. Differences in behavior between two classes should be handled by member functions inherited from the parent class and overridden as desired by the child classes.

   ---

This page last modified on 3 April 2001.