Подготовка школьников к олимпиаде по информатике. Задача 6 (8 баллов). Дана префиксная запись арифметического выражения + a * b + c * d + e * f + g * h i. Найти инфиксную запись этого выражения, не содержащую лишних круглых скобок.

Подготовка школьников к олимпиаде по информатике

Задача 6 (8 баллов). Дана префиксная запись арифметического выражения + a * b + c * d + e * f + g * h i. Найти инфиксную запись этого выражения, не содержащую лишних круглых скобок.

Решение задачи 6.
Сначала надо построить бинарное дерево, изображающее арифметическое выражение. Корень дерева и все внутренние
вершины дерева являются бинарными операторами, а листья дерева – операндами. При построении дерева префиксная
запись выражения читается слева направо один раз, а дерево строится сверху вниз (от корня листьям). Затем надо обойти
дерево в центрированном порядке (in-ordered): левое поддерево – вершина – правое поддерево.
Ответ: a + b * (c + d * (e + f * (g + h * i))).