The third lab exercise in Design Patterns

1. We consider a computer program for manipulating vector drawings, such as Inkscape or Visio. Assume that there is a need for encapsulating various shapes and the whole drawing according to the following interfaces: 

class Point{
public:
  double x_;
  double y_;
//...
};

class Shape{
public:
  virtual const std::string& id() const =0;
  virtual void translate(const Point& pt) =0;
  // ...
};

class Drawing{
public:
  virtual void addShape(Shape* pShape)=0;
  virtual void removeShape(const std::string& id)=0;
  virtual Shape& getShape(int i)=0;
  virtual int nShapes()=0;
};

Design and implement the class ShapeLineSegment by deriving from the interface Shape. Design the class DrawingVector as a child of the Drawing interface as an adapter for a linear collection defined in the standard library of the language. Choose the external class as std::vector (C++), list (Python), or ArrayList (Java).

Test the correct functionality of the developed components by a suitable test driver.

2. We continue considering a computer program for manipulating vector drawings. Your task is to enable traversal throughout the elements of the drawing according to the Iterator pattern. In order to do that, you first need to refactor the Drawing class by:

Don't forget to design a suitable iterator class (DrawingIterator).

Now offer an alternative drawing implementation based on a binary tree (DrawingTree) which associates the drawing elements with their ID code (this code is provided by the Shape::id() method). This implementation can be based on std::map (C++), dict (Python) or TreeMap (Java). Show that clients can transparently use both implementations thanks to polymorphic iterators.

Test the correct functionality of your design by a suitable test driver.

3. We develop a program for controlling a vending machine for hot beverages. The first demonstration needs to support at least two different drinks, and so we choose tea and coffee.

It is known that the coffee can be prepared according to the following recipe: 

  - boil water
  - add a spoonful of coffee
  - poor into cup
  - add milk and sugar

The tea is prepared in a similar manner: 

  - boil water
  - insert a tea bag
  - poor into cup
  - add sugar, insert a slice of lemon

Design the solution to the problem according to the Template method pattern by choosing the following participants:

Each called method needs to produce a diagnostic message on standard output, in order to be able to follow the program execution.

4. This task considers the design of smart pointers in C++. We are going to refer to the implementation in the boost library, although in the meantime these concepts have entered the standard library. Study the implementation of the class scoped_ptr in the file boost/smart_ptr/scoped_ptr.hpp. Write short test drivers for scoped_ptr and shared_ptr.

Notice: this task has to be solved in C++. You should understand how these library components work at least at the conceptual level.

5. You need to write a simple component suitable for recursive parsing, displaying and evaluating arithmetic expressions. The component has to support addition, subtraction, mulitplication and division over numerical and symbolic arguments, as well as grouping with round brackets.

The following instructions are suitable for designing a Pythonic solution, feel free to diverge slightly if you prefer to use some other language. The main part of your component should be the function parseExpression which accepts an expression string and generates a Composite which represents the syntax tree of the expression. Composite components need to define a constructor, a method toStr which expresses the contents of the object as a string (in Python, it is sensible to name this method as __str__ or __repr__), as well as the method evaluate which returns the numerical value of the composite. Symbolic data should be evaluated by referencing some global dictionary, e.g. Symbols.

Test the developed components by i) manually setting values for some symbols, ii) parsing an expression containing those symbols, iii) printing the parsed expression, and iv) printing the evaluated numerical value. Recommended test dialogue in the interactive Python shell is shown below. 

>>> tree=parseExpression("6*(x+4)/2-3-x")
>>> tree.toStr()
((((6.0*(x+4.0))/2.0)-3.0)-x)
>>> tree.evaluate() # this does not work, since x is unknown!
...
KeyError: 'x'
>>> Symbols['x']=5
>>> tree.evaluate()
19.0
>>> x=5; 6*(x+4)/2-3-x # test correctness...
19.0
>>> Symbols['x']=4     # try with some other x...
>>> tree.evaluate()
17.0
Help

Writing a parser can be very hard if we approach it without proper planning. Some of the difficulties which need to be considered are listed below:

An elegant solution can be achieved by resolving the operators according to their priority (first + and -, and then * and /). We need to pay attention to postpone the parsing of operators in parentheses. In order to pick the right asociativity, it is beneficial to consider operators from the right towards the left. When all operators are done, we need to deal with the terms which can be a parenthesized subexpression, or an atomic expression (number or a symbol).

We provide a simple recursive function which implements the parsing algorithm sketched above. The function needs to be modified in a way to produce a composite object on output. This composite object needs to include methods for diagnostic printing and evaluating, according to the instructions from the beginning. The required program can be written in 60 lines of Pyhton, including 20 lines of a modified function parse. 

# adapted from  http://news.ycombinator.com/item?id=284842
def parse(strinput):
  for operator in ["+-", "*/"]:
    depth = 0
    for p in range(len(strinput) - 1, -1, -1):
      if strinput[p] == ')': depth += 1
      elif strinput[p] == '(': depth -= 1
      elif depth==0 and strinput[p] in operator:
        # strinput is a compound expression
        return (strinput[p], parse(strinput[:p]), parse(strinput[p+1:]))
  strinput = strinput.strip()
  if strinput[0] == '(':
    # strinput is a parenthesized expression?
    return parse(strinput[1:-1])
  # strinput is an atom!
  return strinput