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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Обратная польская запись (ОПЗ), слайд №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 встретилась открывающая скобка, то ее помещаем в стек.
Описание слайда:
Суть алгоритма в следующем Суть алгоритма в следующем Исходное выражение, записанное в виде строки символов S, просматривается слева направо. Операнды переписываются в выходную строку В, операции обрабатываются с использованием стека, который первоначально пуст, на основе следующих правил. 1. Если в строке S встретился операнд, то его помещаем в строку В. 2. Если в S встретилась открывающая скобка, то ее помещаем в стек.

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


Обратная польская запись (ОПЗ), слайд №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 << " Input formula : "; cin >> In;
Описание слайда:
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 << " Input formula : "; cin >> In;

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


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

Слайд 25


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

Слайд 26


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

Слайд 27


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

Слайд 28


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

Слайд 29


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

Слайд 30


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

Слайд 31


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

Слайд 32


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

Слайд 33


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

Слайд 34


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

Слайд 35


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

Слайд 36


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

Слайд 37


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

Слайд 38


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

Слайд 39


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

Слайд 40


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

Слайд 41


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию