Drzewa wyrażeń


Tematy pokrewne
Drzewa
Podstawowe pojęcia dotyczące drzew
Przechodzenie drzew binarnych – DFS: pre-order, in-order, post-order
Przechodzenie drzew binarnych – BFS
Badanie drzewa binarnego
Prezentacja drzew binarnych
Kopiec
Drzewa wyrażeń
Drzewa poszukiwań binarnych – BST
Tworzenie drzewa BST
Równoważenie drzewa BST – algorytm DSW
Proste zastosowania drzew BST
Drzewa AVL
Drzewa Splay
Drzewa Czerwono-Czarne
Kompresja Huffmana
Zbiory rozłączne – implementacja za pomocą drzew
Podstawowe pojęcia dotyczące stosów
Odwrotna Notacja Polska

Problem

Przedstawić symboliczne wyrażenie arytmetyczne jako drzewo wyrażeń.



Drzewo wyrażeń (ang. expression tree) jest drzewem binarnym (ang. binary tree), które przedstawia sobą wyrażenie arytmetyczne. Liście drzewa reprezentują argumenty, a wewnętrzne węzły operacje arytmetyczne. Dla uproszczenia umówmy się, że argumenty będą symbolami jednoliterowymi: a, b, c. Operacje ograniczymy do: +, -, *, / oraz ^ (potęgowanie). W wyrażeniu będą mogły pojawiać się nawiasy ().

Poniżej podajemy przykłady kilku drzew wyrażeń arytmetycznych:

 

a + b     
(a + b) * (c - d)  
a ^ (b + c * d)  

 

Tworzenie drzewa wyrażeń wymaga przekształcenia wyrażenia na postać ONP, a następnie wykorzystania stosu oraz drzew binarnych. Zasada jest następująca:

 

Mamy dane symboliczne wyrażenie arytmetyczne:

 

(a * b / c) ^ (d - e)

 

Wyrażenie przekształcamy na postać ONP:

 

a b * c / d e - ^ =

 

Przygotowujemy pusty stos, na którym będziemy umieszczać wskazania węzłów drzewa. Wyrażenie ONP przeglądamy kolejno po jednym elemencie od strony lewej do prawej. Jeśli napotkamy argument, to tworzymy węzeł drzewa z tym argumentem i umieszczamy jego adres na stosie. Jeśli trafimy na operator, to tworzymy węzeł z tym operatorem, następnie ze stosu zdejmujemy dwa węzły i dołączamy je jako synów do węzła z operatorem, po czym adres tego węzła wędruje na stos. Gdy przeglądniemy całe wyrażenie ONP, na stosie będziemy mieli adres korzenia drzewa wyrażeń. Prześledźmy te działania na naszym przykładzie:

 

Wyrażenie ONP Opis Stos
 a b * c / d e - ^ 
Elementem jest argument a. Tworzymy węzeł z tym argumentem i umieszczamy go stosie (uwaga: przez umieszczenie węzła na stosie rozumiemy umieszczenie na stosie jego wskazania).
 a b * c / d e - ^ 
Kolejny element wyrażenia jest również argumentem. Tworzymy dla niego węzeł umieszczamy go na stosie.
 a b * c / d e - ^ 
Teraz napotykamy na operator *. Tworzymy nowy węzeł dla operatora. Ze stosu pobieramy dwa węzły (tzn. adresy tych węzłów) i tworzymy z nich lewego i prawego syna węzła z operatorem, po czym węzeł ten umieszczamy na stosie.
 a b * c / d e - ^ 
Argument c. Tworzymy dla niego węzeł i umieszczamy na stosie.
 a b * c / d e - ^ 
Operator /. Tworzymy węzeł operatora. Ze stosu pobieramy dwa węzły (* i c) i dołączamy je do węzła operatora / jako lewy i prawy syn. Następnie węzeł operatora / umieszczamy na stosie.
 a b * c / d e - ^ 
Argument d. Tworzymy dla niego węzeł i umieszczamy na stosie.
 a b * c / d e - ^ 
Argument e. Tworzymy dla niego węzeł i umieszczamy na stosie.
 a b * c / d e - 
Operator -. Tworzymy węzeł dla operatora -. Ze stosu pobieramy węzły d i e i dołączamy je do węzła operatora jako lewy i prawy syn. Węzeł operatora umieszczamy na stosie.
 a b * c / d e -
Operator ^. Tworzymy węzeł operatora, pobieramy ze stosu dwa węzły i dołączamy je jako lewy i prawy syn. Węzeł umieszczamy na stosie.
 a b * c / d e - ^ 
Koniec wyrażenia. Na szczycie stosu mamy adres korzenia drzewa wyrażeń.  

 

Algorytm tworzenia drzewa wyrażeń z wyrażenia ONP

Wejście
Wyrażenie ONP
Wyjście:
Na szczycie stosu adres korzenia drzewa wyrażeń
Elementy pomocnicze:
S  –  stos przechowujący adresy węzłów
el  –  element wyrażenia, znak
v  –  przechowuje adres węzła
Lista kroków:
K01: Jeśli koniec wyrażenia, to zakończ ; sprawdzamy koniec wyrażenia
K02: Czytaj el ; czytamy element wyrażenia
K03: Utwórz nowy węzeł  
K04 v ← adres nowego węzła  
K05: (vdata) ← el ; w węźle umieszczamy odczytany element wyrażenia
K06: Jeśli el nie jest argumentem, to idź do K10  
K07: (vleft) ← nil ; dla argumentów zerujemy synów
K08: (vright) ← nil  
K09: Idź do K14  
K10: (vright) ← S.top() ; dla operatorów pobieramy ze stosu dwa węzły
K11: S.pop()  
K12: (vleft) ← S.top()  
K13: S.pop()  
K14: S.push(v) ; węzeł umieszczamy na stosie
K15: Idź do K01 ; wracamy na początek pętli

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Do programu wprowadzamy symboliczne wyrażenie arytmetyczne. W wyrażeniu można stosować:

Przykładowe wyrażenie:

 

(a + b ^ (c - d)) / e * f ^ g

 

Lazarus
// Tworzenie drzewa wyrażeń
// Data: 11.05.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program e_tree;

// Typ węzłów drzewa
//------------------
type
  PBTNode = ^BTNode;
  BTNode  = record
    left,right : PBTNode;
    data   : char;
  end;

const S_MAX = 100; // rozmiar dla stosów

// Zmienne globalne
//-----------------
var
  cr,cl,cp : string; // łańcuchy do znaków ramek

// Zwraca priorytet operatora dla ONP
//-----------------------------------
function p(c : char) : integer;
begin
  case c of
   '('     : p := 0;
   '+','-' : p := 1;
   '*','/' : p := 2;
   '^'     : p := 3;
   end;
end;

// Funkcja przekształca wyrażenie arytmetyczne e na ONP
//-----------------------------------------------------
function ONP(e : string) : string;
var
  S  : array[0..S_MAX-1] of char;    // Stos operatorów
  sp : integer;                      // Wskaźnik stosu
  t  : string;                       // Wynik
  i  : integer;

begin
  sp := 0;                            // Inicjujemy stos
  t  := '';                           // Zerujemy wynik

  for i := 1 to length(e) do
    case e[i] of                     // Analizujemy znak
    ' ' : ;                          // Spację ignorujemy
    '(' : begin                      // Nawias otwierający zawsze na stos
            S[sp] := '(';
            inc(sp);
          end;
    ')' : begin                      // Nawias zamykający
            while S[sp-1] <> '(' do
            begin
              dec(sp);               // Ze stosu przesyłamy na wyjście
              t := t + S[sp];        // wszystkie operatory aż do nawiasu otw.
              write(S[sp],' ');      // Echo na ekran
            end;
            dec(sp);                 // Usuwamy ze stosu nawias otwierający
          end;
    '+','-','*','/','^' :            // Operator
          begin
            while sp > 0 do
            begin
              if (p(e[i]) = 3) or (p(e[i]) > p(S[sp - 1])) then break;
              dec(sp);               // Na wyjście przesyłamy ze stosu wszystkie
              t := t + S[sp];        // operatory o wyższych priorytetach
              write(S[sp],' ');      // Echo na ekran
            end;
            S[sp] := e[i];           // Operator umieszczamy na stosie
            inc(sp);
          end;
    else
      begin
        t := t + e[i];               // Inaczej znak przesyłamy na wyjście
        write(e[i],' ');             // Echo na ekran
      end;
    end;

  while sp > 0 do                    // Jeśli stos coś zawiera,
  begin
    dec(sp);                         // to na wyjście przesyłamy
    t := t + S[sp];                  // całą zawartość stosu
    write(S[sp],' ');                // Echo na ekran
  end;

  writeln; writeln;

  ONP := t;
end;

// Funkcja zwraca adres korzenia drzewa wyrażeń,
// które zostaje utworzone na podstawie wyrażenia e
//-------------------------------------------------
function etree(e : string) : PBTNode;
var
  S  : array[0..S_MAX-1] of PBTNode; // Stos
  sp : integer;                      // Wskaźnik stosu
  v  : PBTNode;                      // Adres węzła
  i  : integer;                      // Indeks

begin
  sp := 0;                           // Zerujemy stos

  for i := 1 to length(e) do         // Przetwarzamy wyrażenie ONP
  begin
    new(v);                          // Tworzymy nowy węzeł

    v^.data := e[i];                 // Umieszczamy w nim element wyrażenia

    if e[i] in ['+','-','*','/','^'] then
    begin                            // Operator
      v^.right := S[sp - 1];         // Pobieramy ze stosu węzły i czynimy je
      v^.left  := S[sp - 2];         // synami węzła
      dec(sp,2);
    end
    else
    begin                            // Argument
      v^.left  := nil;               // Liść, nie ma synów
      v^.right := nil;
    end;

    S[sp] := v;                      // Węzeł umieszczamy na stosie
    inc(sp);
  end;

  etree := S[sp - 1];                // Zwracamy adres korzenia
end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease(v : PBTNode);
begin
  if v <> nil then
  begin
    DFSRelease(v^.left);   // usuwamy lewe poddrzewo
    DFSRelease(v^.right);  // usuwamy prawe poddrzewo
    dispose(v);            // usuwamy sam węzeł
  end;
end;

// Procedura wypisuje drzewo
//--------------------------
procedure printBT(sp,sn : string; v : PBTNode);
var
  s : string;
begin
  if v <> nil then
  begin
    s := sp;
    if sn = cr then s[length(s) - 1] := ' ';
    printBT(s+cp,cr,v^.right);

    s := Copy(sp,1,length(sp)-2);
    writeln(s,sn,v^.data);

    s := sp;
    if sn = cl then s[length(s) - 1] := ' ';
    printBT(s+cp,cl,v^.left);
  end;
end;

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

var
  e : string;                        // Wyrażenie
  root : PBTNode;                    // Korzeń drzewa
begin

  // Ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr := #218#196;
  cl := #192#196;
  cp := #179#32;

  readln(e);                         // Czytamy wyrażenie

  writeln;

  root := etree(ONP(e));             // Tworzymy drzewo wyrażeń

  printBT('','',root);               // Wyświetlamy drzewo

  DFSRelease(root);                  // Usuwamy drzewo z pamięci

end.
Code::Blocks
// Tworzenie drzewa wyrażeń
// Data: 11.05.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <string>

using namespace std;

// Typ węzłów drzewa
//------------------
struct BTNode
{
  BTNode * left, * right;
  char data;
};

const int S_MAX = 100; // rozmiar dla stosów

// Zmienne globalne
//-----------------

string cr,cl,cp;      // łańcuchy do znaków ramek

// Zwraca priorytet operatora
//---------------------------
int p(char c)
{
  switch(c)
  {
    case '+'     : ;
    case '-'     : return 1;
    case '*'     : ;
    case '/'     : return 2;
    case '^'     : return 3;
  }
  return 0;
}

// Funkcja przekształca wyrażenie arytmetyczne e na ONP
//-----------------------------------------------------
string ONP(string e)
{
  char S[S_MAX];                     // Stos operatorów
  int sp;                            // Wskaźnik stosu
  string t;                          // Wynik
  unsigned int i;

  sp = 0;                            // Inicjujemy stos
  t  = "";                           // Zerujemy wynik

  for(i = 0; i < e.length(); i++)
    switch(e[i])                     // Analizujemy znak
    {
      case ' ' : break;              // Spację ignorujemy
      case '(' : {                   // Nawias otwierający zawsze na stos
                   S[sp++] = '(';
                   break;
                 }
      case ')' : {                   // Nawias zamykający
                   while(S[sp - 1] != '(')
                   {                 // Ze stosu przesyłamy na wyjście
                     t += S[--sp];   // wszystkie operatory aż do nawiasu otw.
                     cout << S[sp] << " "; // Echo na ekran
                   }
                   sp--;             // Usuwamy ze stosu nawias otwierający
                   break;
                 }
      case '+' : ;                   // Operator
      case '-' : ;
      case '*' : ;
      case '/' : ;
      case '^' : {
                   while(sp)
                   {
                     if((p(e[i]) == 3) || (p(e[i]) > p(S[sp - 1]))) break;
                                    // Na wyjście przesyłamy ze stosu wszystkie
                     t += S[--sp];  // operatory o wyższych priorytetach
                     cout << S[sp] << " "; // Echo na ekran
                   }
                   S[sp++] = e[i];  // Operator umieszczamy na stosie
                   break;
                 }
      default :  {
                   t += e[i];       // Inaczej znak przesyłamy na wyjście
                   cout << e[i] << " "; // Echo na ekran
                   break;
                 }
    }

  while(sp)                         // Jeśli stos coś zawiera,
  {                                 // to na wyjście przesyłamy
    t += S[--sp];                   // całą zawartość stosu
    cout << S[sp] << " ";           // Echo na ekran
  }

  cout << endl << endl;
  return t;
}

// Funkcja zwraca adres korzenia drzewa wyrażeń,
// które zostaje utworzone na podstawie wyrażenia e
//-------------------------------------------------
BTNode * etree(string e)
{
  BTNode * S[S_MAX];                 // Stos
  int sp;                            // Wskaźnik stosu
  BTNode * v;                        // Adres węzła
  unsigned int i;                    // Indeks

  sp = 0;                            // Zerujemy stos

  for(i = 0; i < e.length(); i++)    // Przetwarzamy wyrażenie ONP
  {
    v = new BTNode;                  // Tworzymy nowy węzeł

    v->data = e[i];                  // Umieszczamy w nim element wyrażenia

    switch(e[i])
    {
      case '+' : ;
      case '-' : ;
      case '*' : ;
      case '/' : ;
      case '^' : {                   // Operator
                   v->right = S[--sp]; // Pobieramy ze stosu węzły i czynimy je
                   v->left  = S[--sp]; // synami węzła
                   break;
                 }
      default  : {                   // Argument
                   v->left = v->right= NULL; // Liść, nie ma synów
                   break;
                 }
    }
    S[sp++] = v;                      // Węzeł umieszczamy na stosie
  }

  return S[sp - 1];                   // Zwracamy adres korzenia
}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease(BTNode * v)
{
  if(v)
  {
    DFSRelease(v->left);   // usuwamy lewe poddrzewo
    DFSRelease(v->right);  // usuwamy prawe poddrzewo
    delete v;              // usuwamy sam węzeł
  }
}

// Procedura wypisuje drzewo
//--------------------------
void printBT(string sp, string sn, BTNode * v)
{
  string s;

  if(v)
  {
    s = sp;
    if(sn == cr) s[s.length() - 2] = ' ';
    printBT(s + cp, cr, v->right);

    s = s.substr(0,sp.length()-2);
    cout << s << sn << v->data << endl;

    s = sp;
    if(sn == cl) s[s.length() - 2] = ' ';
    printBT(s + cp, cl, v->left);
  }
}

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

int main()
{
  string e;                        // Wyrażenie
  BTNode * root;                   // Korzeń drzewa

  // Ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

  getline(cin,e);                    // Czytamy wyrażenie

  cout << endl;

  root = etree(ONP(e));              // Tworzymy drzewo wyrażeń

  printBT("","",root);               // Wyświetlamy drzewo

  DFSRelease(root);                  // Usuwamy drzewo z pamięci

  return 0;
}
Free Basic
' Tworzenie drzewa wyrażeń
' Data: 11.05.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

' Typ węzłów drzewa
'------------------
Type BTNode
  Left As BTNode Ptr
  Right As BTNode Ptr
  Data As String * 1
End Type

Const S_MAX = 100 ' rozmiar dla stosów

' Zmienne globalne
'-----------------

Dim Shared As String * 2 cr,cl,cp ' łańcuchy do ramek

' Zwraca priorytet operatora
'---------------------------
Function p(c As String) As Integer
  Select Case c
         Case "("
           p = 0
         Case "+","-"
           p = 1
         Case "*","/"
           p = 2
         Case "^"
           p = 3
  End Select
End Function

' Funkcja przekształca wyrażenie arytmetyczne e na ONP
'-----------------------------------------------------
Function ONP(e As string) As String
  Dim S(S_MAX) As String * 1        ' Stos operatorów
  Dim sp As Integer                 ' Wskaźnik stosu
  Dim t As String                   ' Wynik
  Dim i As Integer

  sp = 0                            ' Inicjujemy stos
  t  = ""                           ' Zerujemy wynik

  For i = 1 To Len(e)
    Select Case Mid(e,i,1)          ' Analizujemy znak
      case " "                      ' Spację ignorujemy
      case "("
        S(sp) = "("                 ' Nawias otwierający zawsze na stos
        sp += 1
    	case ")"
    	  While S(sp-1) <> "("        ' Nawias zamykający
          sp -= 1                   ' Ze stosu przesyłamy na wyjście
          t += S(sp)                ' wszystkie operatory aż do nawiasu otw.
          Print S(sp);" ";          ' Echo na ekran
    	  Wend
        sp -= 1                     ' Usuwamy ze stosu nawias otwierający
      case "+","-","*","/","^"
        While sp > 0
          If (p(Mid(e,i,1)) = 3) OrElse (p(Mid(e,i,1)) > p(S(sp - 1))) Then Exit While
          sp -= 1                   ' Na wyjście przesyłamy ze stosu wszystkie
          t += S(sp)                ' operatory o wyższych priorytetach
          Print S(sp);" ";          ' Echo na ekran
        Wend
        S(sp) = Mid(e,i,1)          ' Operator umieszczamy na stosie
        sp += 1
      Case Else
        t += Mid(e,i,1)             ' Inaczej znak przesyłamy na wyjście
        Print Mid(e,i,1);" ";       ' Echo na ekran
    End Select
  Next

  While sp > 0                      ' Jeśli stos coś zawiera, 
    sp -= 1                         ' to na wyjście przesyłamy
    t += S(sp)                      ' całą zawartość stosu
    print S(sp);" ";                ' Echo na ekran
  Wend

  Print: Print
  
  ONP = t
End Function

' Funkcja zwraca adres korzenia drzewa wyrażeń,
' które zostaje utworzone na podstawie wyrażenia e
'-------------------------------------------------
Function etree(e As String) As BTNode Ptr
  Dim As BTNode Ptr S(S_MAX)        ' Stos
  Dim As Integer sp                 ' Wskaźnik stosu
  Dim As BTNode Ptr v               ' Adres węzła
  Dim As Integer i                    ' Indeks

  sp = 0                            ' Zerujemy stos

  For i = 1 To Len(e)               ' Przetwarzamy wyrażenie ONP
    v = new BTNode                  ' Tworzymy nowy węzeł
    v->data = Mid(e,i,1)            ' Umieszczamy w nim element wyrażenia

    Select Case Mid(e,i,1)
      case "+","-","*","/","^"      ' Operator
        v->right = S(sp-1)          ' Pobieramy ze stosu węzły i czynimy je
        v->left  = S(sp-2)          ' synami węzła
        sp -= 2
      Case Else                     ' Argument
        v->left  = 0                ' Liść, nie ma synów
        v->Right = 0
    End Select

    S(sp) = v                       ' Węzeł umieszczamy na stosie
    sp += 1
  Next

  etree = S(sp-1)                   ' Zwracamy adres korzenia
End Function

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
Sub DFSRelease(v As BTNode Ptr)
  If v Then
    DFSRelease(v->left)   ' usuwamy lewe poddrzewo
    DFSRelease(v->right)  ' usuwamy prawe poddrzewo
    Delete v              ' usuwamy sam węzeł
  End If
End Sub


' Procedura wypisuje drzewo
'--------------------------
Sub printBT(sp As String, sn As String, v As BTNode Ptr)

  Dim As String s

  If v Then
    s = sp
    If sn = cr Then Mid(s,Len(s) - 1, 1) = " "
    printBT(s + cp, cr, v->right)

    s = Mid(s,1, Len(sp)-2)
    Print Using "&&&";s;sn;v->Data

    s = sp
    If sn = cl Then Mid(s,Len(s) - 1, 1) = " "
    printBT(s + cp, cl, v->Left)
  End If
End Sub

'**********************
'*** PROGRAM GŁÓWNY ***
'**********************

Dim As string e                   ' Wyrażenie
Dim As BTNode Ptr root            ' Korzeń drzewa

' Ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
' wstawiać znaki konsoli do tworzenia ramek.
' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

cr = Chr(218) + Chr(196)
cl = Chr(192) + Chr(196)
cp = Chr(179) + " "

Open Cons For Input As #1

Line Input #1,e                     ' Czytamy wyrażenie

Print

root = etree(ONP(e))                ' Tworzymy drzewo wyrażeń

printBT("","",root)                 ' Wyświetlamy drzewo

DFSRelease(root)                    ' Usuwamy drzewo z pamięci

End
Wynik
(a + b ^ (c - d)) / e * f ^ g

a b c d - ^ + e f g ^ * /

    ┌─g
  ┌─^
  │ └─f
┌─*
│ └─e
/
│     ┌─d
│   ┌─-
│   │ └─c
│ ┌─^
│ │ └─b
└─+
  └─a

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe