Algorytmy i Struktury Danych - Drzewa 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ń

Zmienne 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:	( v→data ) ← el	w węźle umieszczamy odczytany element wyrażenia
K06:	Jeśli el nie jest argumentem, to idź do kroku K10
K07:	( v→left ) ← nil	dla argumentów zerujemy synów
K08:	( v→right ) ← nil
K09:	Idź do kroku K14
K10:	( v→right ) ← S.top( )	dla operatorów pobieramy ze stosu dwa węzły
K11:	S.pop( )
K12:	( v→left ) ← S.top( )
K13:	S.pop( )
K14:	S.push ( v )	węzeł umieszczamy na stosie
K15:	Idź do kroku K01	wracamy na początek pętli

Przykładowe programy

Uwaga:

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ć:

pojedyncze litery (małe lub duże) jako symbole argumentów,
znaki operacji arytmetycznych +, -, *, / oraz ^ dla potęgowania,
znaki nawiasów ( i ).

Przykładowe wyrażenie:

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

Pascal

// 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.

C++

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

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

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

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

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Drzewa wyrażeń