Обратная польская запись (ОПЗ) - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Обратная польская запись (ОПЗ), слайд №1

Обратная польская запись (ОПЗ), слайд №2

Обратная польская запись (ОПЗ), слайд №3

Обратная польская запись (ОПЗ), слайд №4

Обратная польская запись (ОПЗ), слайд №5

Обратная польская запись (ОПЗ), слайд №6

Обратная польская запись (ОПЗ), слайд №7

Обратная польская запись (ОПЗ), слайд №8

Обратная польская запись (ОПЗ), слайд №9

Обратная польская запись (ОПЗ), слайд №10

Обратная польская запись (ОПЗ), слайд №11

Обратная польская запись (ОПЗ), слайд №12

Обратная польская запись (ОПЗ), слайд №13

Обратная польская запись (ОПЗ), слайд №14

Обратная польская запись (ОПЗ), слайд №15

Обратная польская запись (ОПЗ), слайд №16

Обратная польская запись (ОПЗ), слайд №17

Обратная польская запись (ОПЗ), слайд №18

Обратная польская запись (ОПЗ), слайд №19

Обратная польская запись (ОПЗ), слайд №20

Обратная польская запись (ОПЗ), слайд №21

Обратная польская запись (ОПЗ), слайд №22

Обратная польская запись (ОПЗ), слайд №23

Обратная польская запись (ОПЗ), слайд №24

Обратная польская запись (ОПЗ), слайд №25

Обратная польская запись (ОПЗ), слайд №26

Обратная польская запись (ОПЗ), слайд №27

Обратная польская запись (ОПЗ), слайд №28

Обратная польская запись (ОПЗ), слайд №29

Обратная польская запись (ОПЗ), слайд №30

Обратная польская запись (ОПЗ), слайд №31

Обратная польская запись (ОПЗ), слайд №32

Обратная польская запись (ОПЗ), слайд №33

Обратная польская запись (ОПЗ), слайд №34

Обратная польская запись (ОПЗ), слайд №35

Обратная польская запись (ОПЗ), слайд №36

Обратная польская запись (ОПЗ), слайд №37

Обратная польская запись (ОПЗ), слайд №38

Обратная польская запись (ОПЗ), слайд №39

Обратная польская запись (ОПЗ), слайд №40

Обратная польская запись (ОПЗ), слайд №41

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Обратная польская запись (ОПЗ). Доклад-сообщение содержит 41 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Обратная польская запись (ОПЗ) Обратная польская запись (ОПЗ) Сложные вычислительные задачи обычно требу-ют больших объемов вычислений, поэтому к разработчикам языков программирования предъявлялось требование: максимально при-близить форму записи математических выра-жений в коде программы к естественному языку математики. Одну из первых областей системного програм-мирования составили исследования способов трансляции математических выражений.

Слайд 2

Описание слайда:

В результате наибольшее распространение полу-чил метод трансляции с помощью обратной польской записи, которую предложил польский математик Я. Лукашевич. В результате наибольшее распространение полу-чил метод трансляции с помощью обратной польской записи, которую предложил польский математик Я. Лукашевич. ОПЗ представляет собой выражение, записанное в постфиксной форме, без скобок, по специальным правилам.

Слайд 3

Описание слайда:

Пусть для операндов А и В выполняется операция сложения. Пусть для операндов А и В выполняется операция сложения. Привычная форма записи А+В называется инфиксной. Форма записи, в которой знак операции следует перед операндами +АВ, называется префиксной. Если же операция записывается после операндов АВ+, то это постфиксная форма. Получение ОПЗ реализуется с использованием структур в виде стека и дерева.

Слайд 4

Описание слайда:

Алгоритм, использующий стек Алгоритм, использующий стек Получение ОПЗ с использованием стека может осуществляться весьма просто на основе алгоритма, предложенного Дейкстрой, кото-рый ввел понятие стекового приоритета операций, например:

Слайд 5

Описание слайда:

Суть алгоритма в следующем Суть алгоритма в следующем Исходное выражение, записанное в виде строки символов S, просматривается слева направо. Операнды переписываются в выходную строку В, операции обрабатываются с использованием стека, который первоначально пуст, на основе следующих правил. 1. Если в строке S встретился операнд, то его помещаем в строку В. 2. Если в S встретилась открывающая скобка, то ее помещаем в стек.

Слайд 6

Описание слайда:

3. Если в S встретилась закрывающая скобка, то извлекаем из стека и записываем в строку В все операции до "(", саму "(" скобку также извлекаем из стека; обе скобки игнорируются. 3. Если в S встретилась закрывающая скобка, то извлекаем из стека и записываем в строку В все операции до "(", саму "(" скобку также извлекаем из стека; обе скобки игнорируются. 4. Если в S встретилась операция Х, то вытал-киваем из стека все операции, приоритет кото-рых не ниже Х, после чего саму операцию Х записываем в стек. 5. При достижении конца строки S, анализируем стек и, если он не пуст, извлекаем и пере-писываем его элементы в выходную строку В.

Слайд 7

Описание слайда:

Пример реализации Пример реализации Исходное выражение задано в виде строки S "a + b*c + ( d*e + f )*g" Запишем это выражение в форме ОПЗ. Ответом будет выражение (без скобок) abc*+de*f+g*+ Результат будем получать в строке В. Начинаем последовательно просматривать сим-волы исходной строки, причем В – пустая строка и стек пуст.

Слайд 8

Описание слайда:

Всего в строке 15 символов (15 п.п.). Всего в строке 15 символов (15 п.п.). 1. Букву «a» помещается в строку В 2. Операцию «+» помещаем в стек. 3. Букву «b» помещаем в строку В. На этот момент стек и строка В выглядят следующим образом:

Слайд 9

Описание слайда:

Слайд 10

Описание слайда:

6. Следующая операция «+»: анализируем стек и видим, что в вершине стека «*» и следующая за ней «+» имеют приоритеты не ниже текущей. Следовательно, обе операции извлекаем из стека и помещаем в строку В, а текущую операцию «+» помещаем в стек. 6. Следующая операция «+»: анализируем стек и видим, что в вершине стека «*» и следующая за ней «+» имеют приоритеты не ниже текущей. Следовательно, обе операции извлекаем из стека и помещаем в строку В, а текущую операцию «+» помещаем в стек. В итоге имеем

Слайд 11

Описание слайда:

7. Далее следует символ «(», его помещаем в стек. 7. Далее следует символ «(», его помещаем в стек. 8. Букву «d» помещаем в строку В. В результате получается

Слайд 12

Описание слайда:

9. Операцию «*» помещаем в стек, т.к. приоритет у скобки самый низкий. 9. Операцию «*» помещаем в стек, т.к. приоритет у скобки самый низкий. 10. Букву «e» помещаем в строку В. Получили

Слайд 13

Описание слайда:

11. Следующая операция «+»: приоритет операции «*» в вершине стека выше, поэтому извлекаем из стека «*» и помещаем в строку В. Текущий символ «+» помещаем в стек. 11. Следующая операция «+»: приоритет операции «*» в вершине стека выше, поэтому извлекаем из стека «*» и помещаем в строку В. Текущий символ «+» помещаем в стек. 12. Букву «f» помещаем в строку В. Получаем

Слайд 14

Описание слайда:

13. Далее идет закрывающая скобка, все элементы до символа «(» извлекаем из стека и помещаем в строку В (это элемент «+»), сам символ «(» тоже извлекаем из стека. 13. Далее идет закрывающая скобка, все элементы до символа «(» извлекаем из стека и помещаем в строку В (это элемент «+»), сам символ «(» тоже извлекаем из стека. Обе скобки игнорируются:

Слайд 15

Описание слайда:

14. Операцию «*» помещаем в стек, т.к. ее приоритет выше операции «+» в вершине стека. 14. Операцию «*» помещаем в стек, т.к. ее приоритет выше операции «+» в вершине стека. 15. Букву «g» записываем в строку В. Получаем

Слайд 16

Описание слайда:

Все символы строки S просмотрены, следова-тельно, анализируем состояние стека, если он не пуст, то переписываем все его элементы в строку В, т.е. операции «+» и «*» последо-вательно извлекаем из стека в строку: Все символы строки S просмотрены, следова-тельно, анализируем состояние стека, если он не пуст, то переписываем все его элементы в строку В, т.е. операции «+» и «*» последо-вательно извлекаем из стека в строку:

Слайд 17

Описание слайда:

Вычисление выражения, записанного в ОПЗ, может проводиться путем однократного просмотра, что является весьма удобным при генерации объектного кода программ. Вычисление выражения, записанного в ОПЗ, может проводиться путем однократного просмотра, что является весьма удобным при генерации объектного кода программ. Рассмотрим простой пример.

Слайд 18

Описание слайда:

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

void main () void main () { Stack *t, *Op = NULL; // Стек операций Op – пуст char a, In [81], Out [81]; // In – входная (S), Out – выходная (B) строки int k = 0, l = 0; // Текущие индексы для строк cout > In;