Содержание
- 2. АТД «Стек» Решение задачи проверки правильности расстановки скобок Решение задачи вычисления арифметических выражений Содержание
- 3. 1. АТД «Стек»
- 4. Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного
- 5. Интуитивными моделями стека могут служить колода карт на столе при игре в покер, книги, сложенные в
- 6. Области применения стека: передача параметров в функции; трансляция (синтаксический и семантический анализы, генерация кодов и т.д.);
- 7. Логическая структура стека представлена на рисунке. Определение Элементы стека могут иметь как одинаковые, так и различные
- 8. 1. MAKENULL(S). Делает стек S пустым. 2. TOP(S). Возвращает элемент из вершины стека S. Обычно вершина
- 9. 4. PUSH(x, S). Вставляет элемент х в вершину стека S (заталкивает элемент в стек). Элемент, ранее
- 10. Все текстовые редакторы имеют определенные символы, которые служат в качестве стирающих символов, т.е. таких, которые удаляют
- 11. Операции над текстовыми строками часто выполняются с использованием стеков. Текстовый редактор поочередно считывает символы. Если считанный
- 12. Пример procedure EDIT; var s: STACK; с: char; begin MAKENULL(S); while not eoln do begin read(c);
- 13. В этой программе тип STACK можно объявить как список символов. Процесс вывода содержимого стека в обратном
- 14. Стеки могут представляться в памяти либо в виде вектора (массива) – статическая реализация, либо в виде
- 15. При векторном представлении под стек отводится сплошная область памяти, достаточно большая, чтобы в ней можно было
- 16. Если указатель выйдет за верхнюю границу стека, то стек считается переполненным и включение нового элемента становится
- 17. При списковом представлении стека память под под каждый элемент стека получают динамически. Включение и выборка элемента
- 18. Каждую реализацию списков можно рассматривать как реализацию стеков, т.к. стеки с их операторами являются частными случаями
- 19. Однако реализация списков на основе массивов не очень подходит для представления стеков, так как каждое выполнение
- 20. Можно более рационально приспособить массивы для реализации стеков, если принять во внимание тот факт, что вставка
- 21. Для такой реализации стеков можно определить абстрактный тип STACK следующим образом: Реализация стеков массивами type STACK
- 22. Реализация стеков массивами: операторы procedure MAKENULL ( var S: STACK ); begin S.top:= maxlength + 1
- 23. Реализация стеков массивами: операторы function TOP ( var S: STACK ): elementtype; { Возвращает элемент из
- 24. Реализация стеков массивами: операторы procedure PUSH ( x: elementtype; var S: STACK ); { Вставляет элемент
- 25. Стек как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа всегда идет с
- 26. Логическая схема стека на основе линейного списка: Реализация стеков списком type celltype = record element: elementtype;
- 27. Реализация стеков списком Реализация основных операций со стеком приведена в виде соответствующих процедур. Приведены их два
- 28. Реализация стека на базе линейного однонаправленного списка: Реализация стеков списком procedure Push(x: elementtype; var top: STACK);
- 29. Реализация стеков списком procedure MAKENULL(var top: STACK); {Очистка стека} begin while top nil do Del_SingleList(top, top);
- 30. Реализация стека отдельными процедурами: Реализация стеков списком function Empty( top: STACK) :boolean; begin Empty:= Top=nil; end;
- 31. Реализация стеков списком procedure Pop(var top: STACK; var x: elementtype); {Возвращает число из вершины стека и
- 32. 2. Решение задачи проверки правильности расстановки скобок
- 33. Задача Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и
- 34. Решение задачи со скобками Алгоритм: в начале стек пуст; в цикле просматриваем все символы строки по
- 35. © С.В.Кухта, 2010 Реализация стека (массив) Структура-стек: const MAXSIZE = 100; type Stack = record {
- 36. Реализация стека (массив) function Pop ( var S:Stack ): char; begin if S.size = 0 then
- 37. © С.В.Кухта, 2010 Программа var br1, br2, expr: string; i, k: integer; upper: char; { то,
- 38. Обработка строки (основной цикл) for i:=1 to length(expr) do begin for k:=1 to 3 do begin
- 39. Реализация стека (список) Добавление элемента: Структура узла: type PNode = ^Node; { указатель на узел }
- 40. Реализация стека (список) Снятие элемента с вершины: function Pop ( var top: PNode ): char; var
- 41. Реализация стека (список) Изменения в основной программе: var S: Stack; ... S.size := 0; var S:
- 42. 3. Решение задачи вычисления арифметических выражений
- 43. Одно из применений стеков можно продемонстрировать на примере вычисления значения арифметического выражения в калькуляторах. Пусть арифметическое
- 44. a b + c d + 1 - / Как вычислять автоматически? Инфиксная запись (знак операции
- 45. В калькуляторах чаще всего применяется представление выражения в инфиксной форме – для записи исходного выражения; и
- 46. В инфиксной форме записи каждый бинарный оператор помещается между двумя своими операндами. Для уточнения порядка вычислений
- 47. В постфиксной форме записи (обратной польской записи ОПЗ, или Reverse Polish Notation RPN) операнды предшествуют своему
- 48. Наиболее простым является алгоритм вычисления постфиксного выражения. Исходная строка содержит элементы только двух видов: числа и
- 49. Алгоритм вычисления постфиксного калькулятора. Из исходной строки выделяется очередной элемент. Если элемент – число, то оно
- 50. Рассмотрим порядок вычисления выражения 3 7.5 * 6е2 5 / + = Шаг 1. Из строки
- 51. Постфиксная форма: a b + c d + 1 - / X = Постфиксный калькулятор
- 52. Алгоритм преобразования выражения из инфиксной формы в постфиксную основан на методе стека с приоритетами. В нем
- 53. Элемент стека состоит из двух полей: оператор или скобка – символьный тип; приоритет – целочисленный тип.
- 54. Алгоритм метода. Из исходной строки выделяется очередной элемент Si. Если Si – операнд, то записать его
- 55. Если теперь элемент в вершине стека имеет приоритет, равный 1 (т.е. добавленный элемент Si является закрывающей
- 56. Рассмотрим порядок преобразования выражения 15 * 4 + (25 / 2 - 3) ^ 2 =
- 57. 15 * 4 + (25 / 2 - 3) ^ 2 = . Шаг 7. Выделен
- 58. 15 * 4 + (25 / 2 - 3) ^ 2 = . Шаг 13. Выделен
- 59. Очевидно, что, используя рассмотренные выше алгоритмы преобразования инфиксного выражения в постфиксное и вычисления постфиксного выражения, легко
- 61. Скачать презентацию