Treće laboratorijske vježbe iz OOUP

1. Pretpostavimo da se u programu za vektorsku grafiku javlja potreba za enkapsuliranjem oblika i crteža prema sljedećim sučeljima: 

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

Implementiraj pravocrtni segment (ShapeLineSegment) kao najjednostavniju implementaciju sučelja Shape. Oblikuj implementaciju sučelja crteža (Drawing) kao prilagodnik za linearni spremnik iz standardne biblioteke (DrawingVector). Neka vanjski razred u C++-u bude std::vector, u Pythonu list, a u Javi ArrayList.
Napiši jednostavno ispitno okruženje te ispitaj ispravan rad razvijenih komponenata.

2. I dalje smo kod programa za vektorsku grafiku. Implementiraj prolaz kroz elemente crteža u skladu s oblikovnim obrascem Iterator. Oblikuj iterator kao odgovarajući korisnički razred. Prepravi prilagodnik prema spremniku biblioteke u skladu s novim sučeljem:

Sad ponudi alternativnu implementaciju crteža temeljenu na binarnom stablu (DrawingMap) koje za ključ koristi identifikacijski kod elemenata crteža (njega vraća metoda Shape::id()). Neka vanjski razred u C++-u bude std::map, u Pythonu dict, a u Javi TreeMap. Pokaži da klijenti mogu transparentno koristiti i jednu i drugu implementaciju crteža zahvaljujući polimorfnim iteratorima.

Ispitaj ispravan rad razvijenih komponenata.

3. Razvijamo program za upravljanje strojem za pripremanje toplih napitaka. U prvoj demonstracijskoj verziji potrebno je podržati barem dva različita napitka, te se odlučujemo za čaj i kavu.

Poznato je da se kava radi po sljedećem receptu: 

  - zakuhaj vodu
  - umiješaj kavu
  - izlij u posudu
  - dodaj šećer i mlijeko

Čaj se sprema na sličan način: 

  - zakuhaj vodu
  - umetni vrećicu čaja
  - izlij u posudu
  - dodaj limun

Oblikuj rješenje problema prema obrascu okvirne metode. Neka su elementi obrasca kako slijedi:

Neka svaka pozvana metoda na standardnom izlazu ispiše dijagnostički izlaz kako bi se mogao pratiti tijek izvođenja programa.

4. Proučite način korištenja pametnih pokazivača biblioteke boost. Proučite implementaciju razreda scoped_ptr u datoteci boost/smart_ptr/scoped_ptr.hpp. Napišite kratke ispitne programe za scoped_ptr i shared_ptr.
Napomena: ovaj zadatak mora se riješiti u C++-u. Trebali biste steći razumijevanje kako spomenute komponente rade, barem na konceptualnoj razini.

5. Potrebno je napisati jednostavni rekurzivni program za parsiranje, prikazivanje i evaluiranje aritmetičkih izraza. Program treba podržavati operacije zbrajanja, oduzimanja, množenja i dijeljenja, te grupiranje zagradama nad brojčanim i simboličkim podatcima. Evaluiranje simboličkih podataka implementirajte prozivanjem globalnog rječnika Symbols.

Neka se program temelji na funkciji parseExpression koja treba kreirati kompozit koji predstavlja sintaksno stablo izraza. Sve komponente kompozita trebaju definirati konstruktor, metodu toStr koja sadržaj kompozita izražava znakovnim nizom (u Pythonu ovu metodu ima smisla nazvati __str__ ili __repr__), te metodu evaluate koja evaluira vrijednost kompozita.

Ispitajte razvijeni program na način da ručno postavite vrijednosti simbola, pokrenete parsiranje izraza zadanog znakovim nizom, te zatim ispišete parsirani izraz kao i njegovu numeričku vrijednost. Preporučeni primjer ispitivanja u interaktivnoj ljusci Pythona prikazan je u nastavku. 

>>> tree=parseExpression("6*(x+4)/2-3-x")
>>> tree.toStr()
((((6.0*(x+4.0))/2.0)-3.0)-x)
>>> tree.evaluate() # ovo ne radi jer ne znamo x!
...
KeyError: 'x'
>>> Symbols['x']=5
>>> tree.evaluate()
19.0
>>> x=5; 6*(x+4)/2-3-x # proba
19.0
>>> Symbols['x']=4     # radi i za drugi x
>>> tree.evaluate()
17.0
Pomoć

Parsiranje može biti vrlo težak zadatak ako problemu ne pristupimo na pravi način. Situaciju posebno kompliciraju sljedeći problemi:

Stoga elegantno rješenje možemo postići ako razrješavamo operatore redoslijedom koji odgovara njihovom prioritetu. Pri tome moramo paziti da zanemarimo operatore koji su uokvireni zagradama. Kako bismo pogodili asocijativnost, operatore treba uzimati u obzir s desna na lijevo. Kad obradimo sve operatore, potrebno je provjeriti radi li se o izrazu kojeg grupiraju zagrade. Ako to nije slučaj, vraćamo atomarni izraz koji može biti broj ili simbol.

Kôd koji implementira gore skicirani algoritam parsiranja prikazan je u nastavku. Prikazani kôd treba modificirati na način da na izlazu proizvede kompozit kojeg jednostavno možemo ispisati i evaluirati, u skladu s uputama danim na početku zadatka. Traženi program može se napisati u manje od 60 redaka Pythona, uključujući i 20 redaka modificirane funkcije 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