Алгоритмы и структуры данных на С++. Аксёнова Е.А - 55 стр.

4.4.   Другие представления деревьев                                     55


                         Левая скобочная запись
   Если корнем дерева T является узел a, с поддеревьями (T1 , T2 , ..., Tn ),
то правая скобочная запись определяется следующим образом:
  1) l(a) = a;
  2) l(T ) = a(l(T1 ), ..., l(Tn )).
   Левая скобочная запись дерева, изображенного на рисунке 4.4,
имеет вид l(T ) = 1(2(3, 4), 5(6(7, 8, 9))).

Представление арифметических выражений в виде деревьев
   Пусть дано арифметическое выражение (a + b) ∗ c. Его представле-
ние в виде дерева изображено на рисунке 4.5. Правая и левая скобоч-
ные записи этого выражения: r(T ) = ((a, b)+, c)∗), l(T ) = (∗(+(a, b), c)).




                                       Рис. 4.5

   Обратная польская запись получается из правой скобочной записи
выбрасыванием всех скобок и запятых ab + c∗.
   Прямая скобочная запись получается из левой скобочной записи
выбрасыванием всех скобок и запятых ∗ + abc.
   Обратная польская запись используется в языке Fort, а прямая
польская запись – в языке Lisp.
   Далее приведен пример реализации простейшего стекового каль-
кулятора, вычисляющего значение выражения в обратной польской
записи. В программе будем использовать параметризованную реали-
зацию стека, приведенную в главе 2.

int main()
 {
    сalculator();
     return 0;
 }