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

1.

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

2.

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

3.

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

4.

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

5. Деревья – классификации

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

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

Документы
Тексты
Доходы.doc
Расходы.odt
Отдых.txt
Фотографии
Документы
Текст
ы Доходы.doc
Расходы.odt
Отдых.txt
Фотографии
Папа.jpg
Мама.gif
Папа.jpg
Мама.gif
Документы
Тексты
Доходы.doc
Расходы.odt
Фотографии
Отдых.txt
Папа.jpg
Мама.gif

7. Деревья и арифметические выражения

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

8. Префиксная форма – вычисление с конца

- * + 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)
!
Скобки не нужны, вычисляется
однозначно!

9.

Префиксная форма – вычисление с конца
(идём с конца, встретили знак операции – выполнили её).
Операция записывается перед данными!
Пример:
(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)
(корень (левое, правое))

10. Постфиксная форма (левое-правое-корень)

*
(a+3)*5-2*b
+
a
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)
*
5
2
b
3
!
Вычисляется
с начала!

11.

Постфиксная форма. Вычисляется с начала!
Операция записывается после данных!
Пример:
(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) левое, правое, корень

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

Домашнее задание:
Учебник стр. 38-40 читать
Задания 1в, 2в, 3б,в письменно в тетради