Префиксная и постфиксная формы записи выражений

Структура, в которой одни элементы, «подчиняются» другим, называется иерархией.
В информатике иерархическую структуру называют деревом.

Дерево состоит из узлов и связей между ними
(они называются дугами)
дуга
корень
листья
промежуточные
узлы

«Сыновья» А: B, C.
«Родитель» B: A.
«Потомки» А: B, C, D, E, F, G.
«Предки» F: A, C.
Корень – узел, не имеющий предков (A).
Лист – узел, не имеющий потомков (D, E, F, G).
Высота – наибольшее расстояние от корня до листа.

Деревья – классификации
Глава 1. Псообразные
1.1. Псовые
1.2. Енотовые
1.3. Медвежьи
…
Глава 2. Кошкоообразные
2.1. Кошачьи
2.2. Гиеновые
2.3. Мангустовые
…
многоуровневый список

Иерархия – файловая система

Деревья и арифметические выражения
(a+3)*5-2*b
(-(*(+(a,3),5),*(2,b)))
(корень(левое,правое))
- * + a 3 5 * 2 b
Префиксная форма – операция перед данными.
левый сын
правый сын

Префиксная форма – вычисление с конца
- * + a 3 5 * 2 b
- * + a 3 5 (2*b)
- * (a+3) 5 (2*b)
- (a+3)*5 (2*b)
(a+3)*5 – (2*b)
Идём с конца, встретили знак операции – выполнили её.

Префиксная форма – вычисление с конца
(идём с конца, встретили знак операции – выполнили её).
Операция записывается перед данными!
Пример:
(a+3)*5–(2*b)
-*+a35*2b
1) - * + a 3 5 (2*b)
2) - * (a+3) 5 (2*b)
3) - (a+3)*5 (2*b)
(корень (левое, правое))

Постфиксная форма (левое-правое-корень)
(a+3)*5-2*b
a 3 + 5 * 2 b * -
(a+3) 5 * 2 b * -
(a+3)*5 2 b * -
(a+3)*5 (2*b) -
(a+3)*5 - (2*b)

Постфиксная форма. Вычисляется с начала!
(a+3)*5-2*b
Пример:
a3+5*2b*-
1)(a+3) 5 * 2 b * -
2)(a+3)*5 2 b * -
3)(a+3)*5 (2*b) -
левое, правое, корень
Операция записывается после данных!

Постфиксная форма для компьютера предпочтительней
Когда программа на языке программирования высокого уровня переводится в машинные коды, математические выражения записываются в бесскобочной постфиксной форме, так и вычисляются.
Когда программа доходит до знака операции, все данные для этой операции уже готовы.
a 3 + 5 * 2 b * -

Определите выражение, соответствующее данному дереву, в «нормальном» виде со скобками (эту форму называют инфиксной – операция записывается между данными). Постройте постфиксную форму.
Решение:
a-(b+c)*d
Постфиксная форма:
abc+d*-

Записать выражение в префиксной форме:
(2*a-3*d)*c+2*b
+ * - * 2 a * 3 d c * 2 b
префиксная форма
Идём с конца, встретили знак операции – выполнили её.

Записать выражение в постфиксной форме:
(2*a-3*d)*c+2*b
2 a * 3 d * - c * 2 b * +
постфиксная форма
Вычисляется с начала!

(2*a-3*d)*c+2*b
2
*
3
d
-
c
а
*
b
+
*
2
*

Выполнить самостоятельно в тетради:
задания 1б, 2а, 3а
(учебник, стр. 49-50)
Ответы:
1б - a-(b-(c-d)) a b c d - - -
2a * + a b + c * 2 d a b + c 2 d * + *
3a 66 (12+6)*(7-3-1)+12
+ * + 12 6 - - 7 3 1 12