Arithmetische Ausdrücke

Betrachte

1 + (2 * 3)

Was kommt hier raus? 7!

Ziel: Mechanisches (“automatich”) Verfahren zur Berechnung arithmetischer Ausdrücke.

Alternative Darstellung von “1 + (2 * 3)” als Baum.

      Plus
     /    \
    1     Mult
         /    \
        2      3

Auswertung von “1 + (2 * 3)” mit Hilfe der Baumdarstellung.

Algorithmus:

• Besuche Blätter

• Werte Zwischenknoten aus

• Ersetze Zwischenknoten durch das Ergebnis

Angewandt auf unser Beispiel

      Plus
     /    \
    1     Mult
         /    \
        2      3

=eval=>

      Plus
     /    \
    1      6

=eval=>

      7

Aufgaben

• Wie können wir das ganze in C++ darstellen?

• Wie können wir das ganze in C++ auswerten (“eval”)?

Darstellung in C++

Wir verwenden folgende Klassenhierarchie.

class Exp {};

class Num : public Exp {
    int i;
  public:
     Num(int x) { i = x; }
};

class Plus : public Exp {
  Exp l, r;
  public:
   Plus(Exp x, Exp y) { l = x; r = y; }
};

class Mult : public Exp {
  Exp l, r;
  public:
   Mult(Exp x, Exp y) { l = x; r = y; }
};

Vergleiche String Darstellung

1 + (2 * 3)

mit C++ Darstellung

Plus(Num(1),Mult(Num(2),Num(3))

Klammern sind nicht mehr notwendig!

Kompletter Programcode

Was ist mit der Auswertung?

Idee: Implementiere “eval” als virtuelle Methode.

Auswertung in C++

Wir implementieren “eval” als virtuelle Methode.

Virtuelle Methodenauswahl Bedarf des dynamischen Typs. D.h. eine Referenz auf Exp (“pointer”).

Um Speicherfehler zu vermeiden verwenden wir “smart pointers”.

Anpassung von “Exp” ist wie folgt.

Beachte. Anstatt Num, Plus, Mult finden wir jetzt IntExp, PlusExp und MultExp.

class Exp {
public:
  virtual int eval() = 0;
};
class IntExp : public Exp {
public:
  int x;
  IntExp(int x) {
    if(x == 1 || x == 2) {
      this->x = x;
    }
    else {
      this->x = 1;
      cout << "\nmust be 1 or 2";
    }
  }
  int eval() { return this->x; }

};
class PlusExp : public Exp {
public:
  std::shared_ptr<Exp> left, right;
  PlusExp(std::shared_ptr<Exp> left, std::shared_ptr<Exp> right) {
    this->left = left; this->right = right;
  }
  int eval() { return left->eval() + right->eval(); }

};

class MultExp : public Exp {
public:
  std::shared_ptr<Exp> left, right;
  MultExp(std::shared_ptr<Exp> left, std::shared_ptr<Exp>right) {
    this->left = left; this->right = right;
  }
  int eval() { return left->eval() * right->eval(); }

};

Beachte.

• new kann nur auf native “pointer” angewandt werden

• Ein “smart pointer” Objekt muss via `make_shared’ angelegt werden

Wir “verstecken” `make_shared’ in folgenden Hilfsfunktionen zum anlegen von dynamischen Exp Objekten.

std::shared_ptr<Exp> newInt(int i) {
  return std::make_shared<IntExp>(i);
}

std::shared_ptr<Exp> newPlus(std::shared_ptr<Exp> left, std::shared_ptr<Exp> right) {
  return std::make_shared<PlusExp>(PlusExp(left,right));
}

std::shared_ptr<Exp> newMult(std::shared_ptr<Exp> left, std::shared_ptr<Exp> right) {
  return std::make_shared<MultExp>(MultExp(left,right));
}

Kompletter Programmcode

Parsing

Ein einfacher Parser findet sich hier

Weitere Details siehe Syntax Analyse