3. Вычислите выражения, записанные в постфиксной форме: а) 12 6 + 7 3 − 1 − * 12 +; б) 12 10 − 5 7 + * 7 − 2 *; в) 5 6 7 8 9 + − + −; г) 5 4 3 2 1 − − − −. Запишите каждое из них в инфиксной и в префиксной формах, и постройте соответствующее дерево. Единственное ли такое дерево? В этом дереве назовите корень, листья и промежуточные вершины.

Правило: в постфиксной записи оператор применяют к двум последним операндам или результатам, находящимся в стеке.

1. а)

   Постфиксная форма: 12 6 + 7 3 − 1 − * 12 +

   Вычисление: (12 + 6) · ((7 − 3) − 1) + 12 = 18 · 3 + 12 = 66.

   Инфиксная форма: \(((12+6)\cdot((7-3)-1))+12\)

   Префиксная форма: + * + 12 6 − − 7 3 1 12

                    +
                 /     \
                *       12
              /   \
             +     −
           /  \   / \
          12  6  −   1
                / \
               7   3

2. б)

   Постфиксная форма: 12 10 − 5 7 + * 7 − 2 *

   Вычисление: ((12 − 10) · (5 + 7) − 7) · 2 = (2 · 12 − 7) · 2 = 34.

   Инфиксная форма: \((((12-10)\cdot(5+7))-7)\cdot2\)

   Префиксная форма: * − * − 12 10 + 5 7 7 2

                       *
                     /   \
                    −     2
                  /   \
                 *     7
               /   \
              −     +
            /  \   / \
           12  10 5   7

3. в)

   Постфиксная форма: 5 6 7 8 9 + − + −

   Вычисление: 5 − (6 + (7 − (8 + 9))) = 9.

   Инфиксная форма: \(5-(6+(7-(8+9)))\)

   Префиксная форма: − 5 + 6 − 7 + 8 9

                    −
                  /   \
                 5     +
                      / \
                     6   −
                        / \
                       7   +
                          / \
                         8   9

4. г)

   Постфиксная форма: 5 4 3 2 1 − − − −

   Вычисление: 5 − (4 − (3 − (2 − 1))) = 3.

   Инфиксная форма: \(5-(4-(3-(2-1)))\)

   Префиксная форма: − 5 − 4 − 3 − 2 1

                    −
                  /   \
                 5     −
                      / \
                     4   −
                        / \
                       3   −
                          / \
                         2   1

Для каждой корректной постфиксной записи с бинарными операторами дерево разбора единственно: оператор однозначно соединяет два последних доступных поддерева.

В каждом дереве корень — верхняя вершина, соответствующая последнему оператору. Листья — числовые вершины: исходные операнды. Промежуточные вершины — вершины, обозначенные операциями.

Ответ: а) 66; б) 34; в) 9; г) 3.