Задание №1701/04

По приведённым в таблице данным восстановим дерево разбора арифметического выражения (рисунок 1). Общим родителем вершин с ID 1 и ID 3 является вершина с ID 4, при этом вершина с ID 3 является родителем для вершин с ID 2 и ID 5. Родителем вершины с ID 4 является вершина с ID 0, отсутствующая в таблице, поэтому можно считать вершину с ID 4 корнем дерева.

Вычислим значение арифметического выражения по построенному дереву. Существуют различные способы обхода деревьев, рассмотрим лишь один из них. Так как значение в вершине с ID 4, являющейся корнем, равно *, то значение всего выражения равно произведению значений левого (с корнем, имеющим ID 1) и правого поддерева (с корнем, имеющим ID 3). Отметим, что перестановка поддеревьев местами (левого и правого) на результат не влияет в силу коммутативности операции умножения.

Левое поддерево содержит единственную вершину с ID 1 и числовым значением, равным 8. Рекурсивно применяя рассмотренный выше алгоритм, вычислим значение поддерева, имеющего корень с ID 3, которое равно сумме значений вершин с ID 2 и ID 5, то есть \(5+4=9\).

Таким образом, искомое значение арифметического выражение равно \( 8*(5+4) = 72\).

72