7.2. Метод Дейкстра.

Один из наиболее эффективных методов получения обратной польской записи был предложен в 1960 г. известным голландским ученым профессором Эдсгер Вайб Дейкстра, который основан на исполь­зовании стека с приоритетами, позволяю­щего изменить порядок следования знаков операций в выражении так, что получается обратная польская запись.

Простейший ва­риант этого метода применим только к про­стым арифметическим и логическим выра­жениям, содержащим простые переменные, знаки арифметических и логических опера­ций, знаки операций отношения и круглые скобки.

7.2.1. Приоритеты операций.

Каждому ограничителю, входящему в выражение, присваивает­ся приоритет: для знаков операций приоритеты возра­стают в порядке, обратном стар­шинству операций; скобки имеют низший приоритет.

7.2.2. Использование стека.

Арифметическое или логиче­ское выражение рассматривается как входная строка символов, которая просматривается слева направо; операнды перепи­сываются в выходную строку, а знаки операций помещаются вна­чале в стек операций: если приоритет входного знака равен нулю или больше приори­тета знака, находящегося в вер­шине стека, то новый знак добав­ляется к вершине стека; в противном случае из стека выталки­вается и переписывается в выходную строку знак, находящийся в вершине, а также следующие за ним знаки с приоритетами, большими или равными приоритету входного знака; затем входной знак добавляется к вершине стека.

II. Контрольные вопросы

1. Что называется модулем? Когда используется модуль?

2. В файлах с какими расширениями находятся текст модуля и оттранслиро­ванный код модуля? На каком этапе модуль подключается к программе?

3. Назвать составные части модуля. Какое назначение имеет каждая из частей модуля?

4. Когда выполняется и в каких случаях используется секция инициализа­ции?

5. Чем отличается статическая переменная от динамической?

6. Чем отличается статическая структура от динамической?

7. Что такое «динамическая память»?

8. Какие существуют предопределенные переменные для отслеживания со­стояния кучи?

9. Что такое «указатель»? Назвать виды указателей.

10. Как описать типизированный и нетипизированный указатели?

11. Какие процедуры существуют для выделения динамической памяти?

12. Как задать значение указателю?

13. Что такое «операция разыменования»?

14. Какие процедуры существуют для освобождения динамической памяти?

15. Для чего используется процедура Mark?

16. Можно ли использовать одновременно механизм освобождения памяти с помощью процедур FreeMem, Dispose и Release?

17. Что такое «линейный список»? Какие существуют линейные списки?

18. Чем отличается линейный двусвязный список от линейного односвязного?

19. Чем отличаются линейные списки от циклических?

20. Какие бывают циклические списки?

21. Какая организация данных называется стеком?

22. Какие операции возможны над стеком?

23. Какая организация данных называется простой очередью?

24. Что представляет собой организация данных «дек»?

25. Что такое «обратная польская запись»?

26. В чем заключается метод Дейкстра?