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:
getShape
method (why?);
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.0Help
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