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

Przykładowe wyrażenie:

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

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

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

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

// 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
  // Stos operatorów
  S  : array [0..S_MAX-1] of char;
  // Wskaźnik stosu
  sp : integer;
  // Wynik pośredni
  t  : string;
  i  : integer;

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

  // Jeśli stos coś zawiera, 
  while sp > 0 do
  begin
    // to na wyjście przesyłamy
    dec(sp);
    // całą zawartość stosu
    t := t+S[sp];
    // Echo na ekran
    write(S[sp], ' ');
  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
  // Stos
  S  : array [0..S_MAX-1] of PBTnode;
  // Wskaźnik stosu
  sp : integer;
  // Adres węzła
  v  : PBTnode;
  // Indeks
  i  : integer;

begin
  // Zerujemy stos
  sp := 0;
  // Przetwarzamy wyrażenie ONP
  for i := 1 to length(e) do
  begin
    // Tworzymy nowy węzeł
    new(v);
    // Umieszczamy w nim
    // element wyrażenia
    v^.Data:= e[i];
    if e[i] in ['+', '-', '*', '/', '^'] then
    // Operator
    begin
      // Pobieramy ze stosu węzły
      // i czynimy je synami węzła
      v^.right := S[sp-1];
      v^.left  := S[sp-2];
      dec(sp, 2);
    end
    else
    // Argument
    begin
      // Liść, nie ma synów
      v^.left  := nil;
      v^.right := nil;
    end;
    // Węzeł umieszczamy na stosie
    S[sp] := v;
    inc(sp);
  end;
  // Zwracamy adres korzenia
  etree := S[sp-1];
end;

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

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

    s := Copy(sp, 1, length(sp)-2);
    for i := 1 to length(s) do
      write(char(ord(s[i])));
    for i := 1 to length(sn) do
      write(char(ord(sn[i])));
    writeln(v^.data);

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

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

var
  // Wyrażenie
  e : string;
  // Korzeń drzewa
  root : PBTnode;
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;

  // Czytamy wyrażenie
  readln(e);
  writeln;
  // Tworzymy drzewo wyrażeń
  root := etree(onp(e));
  // Wyświetlamy drzewo
  print_bt('', '', root);
  // Usuwamy drzewo z pamięci
  dfs_release(root);
end.

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

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

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

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

// 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)
{
  // Stos operatorów
  char S[S_MAX];
  // Wskaźnik stosu
  int sp;
  // Wynik
  string t;
  unsigned int i;

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

  // Jeśli stos coś zawiera, 
  // to na wyjście przesyłamy
  while(sp)
  {
    // całą zawartość stosu
    t += S[--sp];
    // Echo na ekran
    cout << S [sp] << " ";
  }
  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)
{
  // Stos
  BTnode * S[S_MAX];
  // Wskaźnik stosu
  int sp;
  // Adres węzła
  BTnode * v;
  // Indeks
  unsigned int i;

  // Zerujemy stos
  sp = 0;
  // Przetwarzamy wyrażenie ONP
  for(i = 0; i < e.length(); i++)
  {
    // Tworzymy nowy węzeł
    v = new BTnode;
    // Umieszczamy w nim
    // element wyrażenia
    v->data = e[i];
    switch(e [i])
    {
      // Operator
      case '+' :
      case '-' :
      case '*' :
      case '/' :
      case '^' : {
                   // Pobieramy ze stosu węzły
                   // i czynimy je synami
                   // węzła
                   v->right = S[--sp];
                   v->left  = S[--sp];
                   break;
                 }
      // Argument
      default  : {
                   // Liść, nie ma synów
                   v->left = v->right= NULL;
                   break;
                 }
    }
    // Węzeł umieszczamy na stosie
    S[sp++] = v;
  }
  // Zwracamy adres korzenia
  return S[sp-1];
}

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

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

  if(v)
  {
    s = sp;
    if(sn == cr)
      s[s.length()-2] = ' ';
    print_bt(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] = ' ';
    print_bt(s+cp, cl, v->left);
  }
}

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

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

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

  // Czytamy wyrażenie
  getline(cin, e);
  cout << endl;
  // Tworzymy drzewo wyrażeń
  root = etree(onp(e));
  // Wyświetlamy drzewo
  print_bt("", "", root);
  // Usuwamy drzewo z pamięci
  dfs_release(root);
  return 0;
}

' 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

' rozmiar dla stosów
Const S_MAX = 100

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

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

' 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
  ' Stos operatorów
  Dim S(S_MAX) As String * 1
  ' Wskaźnik stosu
  Dim sp As Integer
  ' Wynik
  Dim t As String
  Dim i As Integer

  ' Inicjujemy stos
  sp = 0
  ' Zerujemy wynik
  t  = ""
  For i = 1 To Len(e)
    ' Analizujemy znak
    Select Case Mid(e, i, 1)
      ' Spację ignorujemy
      Case " "
      Case "("
        ' Nawias otwierający
        ' zawsze na stos
        S(sp) = "("
        sp += 1
      Case ")"
    	' Nawias zamykający
        While S(sp-1) <> "("
          ' Ze stosu przesyłamy
          ' na wyjście wszystkie
          ' operatory aż do
          ' nawiasu otwierającego
          sp -= 1
          t += S(sp)
          ' Echo na ekran
          Print S(sp);" ";
        Wend
        ' Usuwamy ze stosu
        ' nawias otwierający
        sp -= 1
      Case "+", "-", "*", "/", "^"
        While sp > 0
          If(p(Mid(e, i, 1)) = 3) OrElse _
            (p(Mid(e, i, 1)) > p(S(sp-1))) _
          Then Exit While
          ' Na wyjście przesyłamy
          ' ze stosu wszystkie
          sp -= 1
          ' operatory o wyższych
          ' priorytetach
          t += S(sp)
          ' Echo na ekran
          Print S(sp);" ";
        Wend
        ' Operator umieszczamy
        ' na stosie
        S(sp) = Mid(e, i, 1)
        sp += 1
      Case Else
        ' Inaczej znak
        ' przesyłamy na wyjście
        t += Mid(e, i, 1)
        ' Echo na ekran
        Print Mid(e, i, 1);" ";
    End Select
  Next
  ' Jeśli stos coś zawiera, 
  While sp > 0
    ' to na wyjście przesyłamy
    sp -= 1
    ' całą zawartość stosu
    t += S(sp)
    ' Echo na ekran
    Print S(sp);" ";
  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
  ' Stos węzłów
  Dim As BTnode Ptr S(S_MAX)
  ' Wskaźnik stosu
  Dim As Integer sp
  ' Adres węzła
  Dim As BTnode Ptr v
  ' Indeks
  Dim As Integer i
  
  ' Zerujemy stos
  sp = 0
  ' Przetwarzamy wyrażenie ONP
  For i = 1 To Len(e)
    ' Tworzymy nowy węzeł
    v = new BTnode
    ' Umieszczamy w nim
    ' element wyrażenia
    v->data = Mid(e, i, 1)

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

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

' Procedura wypisuje drzewo
'--------------------------
Sub print_bt(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) = " "
    print_bt(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) = " "
    print_bt(s+cp, cl, v->Left)
  End If
End Sub

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

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

' 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
' Czytamy wyrażenie
Line Input #1, e
Print
' Tworzymy drzewo wyrażeń
root = etree(onp(e))
' Wyświetlamy drzewo
print_bt("", "", root)
' Usuwamy drzewo z pamięci
dfs_release(root)
End