C++Guns – RoboBlog blogging the bot

Okay ich fasse mal zusammen. Ich sehe 3 Fälle, vom einfachsten zum schwersten.

1) Ganz normal Klassen ableiten.

class Base {
public:
  ~Base() {
    cout << "~TestClass\n";
  }
};

class Derived : public TestClass {
public:
  ~Derived() {
    cout << "~Derived\n";
  }
};

int main() {
  {
  cout << "a\n";
  Derived a;
  }
  cout << "b\n";
  Derived *b = new Derived();
  delete b;
}

Ausgabe:
a                                                                                                                
~Derived                                                                                                         
~Base
b
~Derived
~Base

Der Destructor wird immer aufgerufen.
2) Mit Polymorphie (Pointer ist vom Type Base)

class Base {
public:
  virtual ~Base() {
    cout << "~TestClass\n";
  }
};

class Derived : public TestClass {
public:
  virtual ~Derived() {
    cout << "~Derived\n";
  }
};

int main() {
  {
  cout << "a\n";
  Derived a;
  }
  cout << "b\n";
  Base *b = new Derived();
  delete b;
}

Ausgabe:
a                                                                                                                
~Derived                                                                                                         
~Base
b
~Derived
~Base

Der Destructor wird immer aufgerufen.

3) Mit Polymorphie und class Derived als abstracte Klasse

class Base {
public:
  virtual ~Base() = 0;
};

Base::~Base() {
    cout << "~Base\n";
}

class Derived : public Base {
public:
  virtual ~Derived() {
    cout << "~Derived\n";
  }
};

int main() {
  {
  cout << "a\n";
  Derived a;
  }
  cout << "b\n";
  Base *b = new Derived();
  delete b;
}

Ausgabe:
a                                                                                                                
~Derived                                                                                                         
~Base
b
~Derived
~Base

Der Destructor wird immer aufgerufen.
Der Destructor von Base ist zwar abstract, es gibt aber eine default Implementation, die im Zweifel garnichts macht. Es muss immer eine Implementation der Spezialfunktionen, wie dem Destructor, geben. Wird keine explicit angegeben, erstellt automatisch der Compiler eine. (Ausser man declariert ihn mit "=0" als abstract).

Wozu das ganze? Abstrace Klassen können nicht instanziiert werden, sie dienen wirklich nur als ein abstractes Interface. Sollte man es dennoch versuchen, bekommt man folgende Compilerfehler:

error: cannot declare variable ‘c’ to be of abstract type ‘Base’
 Base c;
 note:   because the following virtual functions are pure within ‘Base’:
 virtual ~Base() = 0;

PS: Wird das virtual keyword mal vergessen, wird der Base Destructor im ungünstigen Fall nicht aufgerufen ;)

Hf

Die Wikipedia Artikel zum Cocke-Younger-Kasami-Algorithmu kann man vergessen. Man kapiert nichts. Hab auf youtube ein 15min Video [1] von Benny Neugebauer dazu gefunden. Wunderbar, alles gleich verstanden :)
Hab ihn mal schnell in C++ implementiert. Hier die Hauptschleife:

    /*
    Für j = 2 ... n
      Für i = 1 ... n - j + 1
        Für k = 1 ... j - 1
          Setze V_{i,j} := V_{i,j} + { l | \exists B,C in N ((l -> BC) in P and B in V_{i,k} and C in V_{i + k, j - k}) \}

    Falls S \in V_{1,n}, stoppe und gib "w wird von G erzeugt" aus
    Stoppe und gib "w wird nicht von G erzeugt" aus
    */
    for(size_t row=1; row < n; row++) {
//        cout << "row " << row << "\n";
        for(size_t col=0; col < n-row; col++) {
//            cout << "col " << col << "\n";
            for(size_t k=0; k < row; k++) {
                const auto &e1 = V.at(k, col);
                const auto &e2 = V.at(row-k-1, col+k+1);

                for(size_t i=0; i < e1.size(); i++) {
                    for(size_t j=0; j < e2.size(); j++) {
//                        cout << "Check " << e1.at(i) << " " << e2.at(j) << "\n";
                        const Production::String toTest({e1.at(i), e2.at(j)});
                        for(const Production& p : P) {
                            if(p.right == toTest) {
                                // uniq append
                                if(contains(V.at(row, col), p.left) == false) {
                                    V.at(row, col).push_back(p.left);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

Für jeden Matrixeintrag in der oberen linken Dreiecksmatrix:
Für jeden Eintrag oberhalt in der Spalte und Diagonal nach oben:
Schaue nach ob die Konkatenation der beiden Einträge in der rechten Seite der Produktionsregeln vorkommen:
Ja) Linke Seite der Produktion in die Matrix eintragen.

Steht am Ende in der letzten Zeile, erste Spalte das Startsymbol, dann kann das Wort erkannt werden.

CYK.zip

[1] https://www.youtube.com/watch?v=JugIgxUyA4Q