Własny język programowania

03.02.2010 - Maciej Piróg
TrudnośćTrudność

Reprezentujemy drzewa wyrażeń

Będziemy zajmować się obliczaniem wartości wyrażeń, więc w pamięci lepiej przechowywać wyrażenia w postaci drzew (o tym jak przekształcić wyrażenie w drzewo, czyli o parsowaniu, przeczytać można w 2. części cyklu).

By zaprogramować drzewa wyrażeń w języku C++, wspomożemy się następującą obserwacją: Każde drzewo wyrażeń jest albo liczbą albo powstało z połączenia dwóch wyrażeń przez binarny operator. Użyjemy mechanizmu dziedziczenia, by każdy z tych przypadków był reprezentowany przez oddzielne klasy.

Klasą nadrzędną jest Expression, z której dziedziczyć będą wszystkie inne "rodzaje" wyrażeń:

1
2
3
class Expression
{
};

Jak widać, wyrażenia na razie nie mają żadnej ciekawej funkcjonalności.

Wyrażenia pierwszego "rodzaju" to stałe liczbowe. Reprezentująca je klasa wygląda następująco:

1
2
3
4
5
6
7
class Constant : Expression
{
    int value;
 
  public:
    Constant(int v) : value(v) { }
};
Obiekty tej klasy przechowują w polu value wartość przechowywaną w liściu drzewa wyrażenia. Konstruktor pozwala ustalić tę wartość w momencie tworzenia obiektu.

Wyrażenia drugiego "rodzaju" to węzły drzewa reprezentujące operatory. Muszą przechowywać w sobie nie tylko etykietę operatora, ale także wskaźniki na poddrzewa (reprezentujące podwyrażenia):

1
2
3
4
5
6
7
8
9
class Binary_operator : Expression
{
    char symbol;
    Expression` left, * right;
 
  public:
    Binary_operator(char s, Expression* l, Expression* r)
      : symbol(s), left(l), right(r) { }
};

Dla przykładu skonstruujmy drzewo odpowiadające wyrażeniu 2 + (1 + 7) * (4 * 5) z pierwszego obrazka:

1
2
3
4
5
6
7
8
9
10
11
  Expression* n4 = new Constant(4); // 4
  Expression* n5 = new Constant(5); // 5
  Expression* e1 = new Binary_operator('*', n4, n5); // 4 * 5
  Expression* n1 = new Constant(1); // 1
  Expression* n7 = new Constant(7); // 7
  Expression* e2 = new Binary_operator('+', n1, n7); // 1 + 7
  Expression* e3 = new Binary_operator('*', e2, e1);
                                         // (1 + 7) * (4 * 5)
  Expression* n2 = new Constant(2); // 2
  Expression* e4 = new Binary_operator('+', n2, e3);
                                    // 2 + (1 + 7) * (4 * 5)

Oczywiście nie musimy być aż tak rozwlekli, to samo drzewo można skonstruować jednym wyrażeniem:

1
2
3
4
  Expression* e = new Binary_operator('+', new Constant(2),
    new Binary_operator('*',
      new Binary_operator('+', new Constant(1), new Constant(7)),
      new Binary_operator('*', new Constant(4), new Constant(5))));

Obliczamy wartość wyrażeń

Przypomnijmy, że wskaźnik pewnego typu (np. Expression*) może wskazywać nie tylko na obiekty tego typu, ale także na obiekty dowolnego typu, który z niego dziedziczy (np. Constant). Miało to miejsce w przykładach powyżej. Mechanizm metod wirtualnych pozwala na wywołanie metod właściwych dla klasy obiektu, na który pokazuje wskaźnik, a nie tych, które są właściwe dla klasy samego wskaźnika, na przykład:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class A
{
  public:
    virtual void print() { cout << "A"; }
};
 
class B : public A
{
  public:
    virtual void print() { cout << "B"; }
};
 
int main()
{
  B b;
  A* ptr = &b;
  ptr->print();
  return 0;
}
Powyższy program spowoduje wypisanie na ekran 'B', chociaż typem ptr jest wskaźnik na obiekt klasy A.

Rozbudujemy teraz nasze drzewa o wirtualną metodę obliczania wartości wyrażenia. Musimy ją zadeklarować w klasie Expression:

1
2
3
4
5
class Expression
{
  public:
    virtual string eval() = 0;
};
Niektóre klasy (tak jak Expression w naszym przypadku) służą jedynie do tego, by być nadklasami dla pewnej liczby dziedziczących z nich klas, które implementują te same metody wirtualne (tak jak Constant i Binary_operator). Obiektów takich klas w praktyce nigdy się nie tworzy. Takie klasy nazywamy interfejsami.
Ponieważ sama klasa Expression nie reprezentuje żadnego wyrażenia, obliczanie "wartości" obiektów tej klasy nie miałoby sensu. Dlatego napisaliśmy  = 0;, by poinformować kompilator języka C++, że jest to jedynie deklaracja metody, która będzie zdefiniowana w klasach, które dziedziczą z Expression.

Wartością stałej liczbowej jest oczywiście reprezentowana przez nią liczba:

1
2
3
4
5
6
7
8
9
10
11
12
class Constant : Expression
{
    int value;
 
  public:
    Constant(int v) : value(v) { }
 
    virtual int eval()
    {
      return value;
    }
};

Natomiast by obliczyć wartość wyrażenia będącego operatorem łączącym dwa podwyrażenia, należy obliczyć wartości tych podwyrażeń i zastosować odpowiednie działanie do wyników:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Binary_operator : Expression
{
    char symbol;
    Expression *left, *right;
 
  public:
    Binary_operator(char s, Expression* l, Expression* r)
      : symbol(s), left(l), right(r) { }
 
    virtual int eval()
    {
      switch (symbol)
      {
        case '*': return left->eval() * right->eval();
        case '+': return left->eval() + right->eval();
        case '-': return left->eval() - right->eval();
        // ... inne operatory
      }
    }
};

Sprawdźmy, czy obliczanie wyrażeń zaimplementowane w powyższy sposób działa. Wykonanie poniższego kodu spowoduje obliczenie wyrażenia 2 + (1 + 7) * (4 * 5). Wynik, tak jak oczekiwaliśmy, jest równy 162:

1
2
3
4
5
6
  Expression* f = new Binary_operator('+', new Constant(2),
    new Binary_operator('*',
      new Binary_operator('+', new Constant(1), new Constant(7)),
      new Binary_operator('*', new Constant(4), new Constant(5))));
 
  cout << f->eval();

4.8
Twoja ocena: Brak Ocena: 4.8 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com