Стеки. Области применения стека

Июль 23, 2022

Главная
Информатика
Стеки. Области применения стека

Содержание

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. Скачать презентацию

Слайд 2

АТД «Стек»
Решение задачи проверки правильности расстановки скобок
Решение задачи вычисления арифметических выражений
Содержание

Слайд 3

1. АТД «Стек»

Слайд 4

Стек – это линейная структура данных, в которой добавление и удаление

элементов возможно только с одного конца (вершины стека).
Stack (Stapel) = кипа, куча, стопка (англ.)
Т.о., стек – это специальный тип списка, в котором все вставки (push) и удаления (pop) выполняются только на одном конце, называемом вершиной (top).
Стеки также иногда называют "магазинами", а в англоязычной литературе для обозначения стеков еще используется аббревиатура LIFO (last-in-first-out - последний вошел – первый вышел).

Определение

Слайд 5

Интуитивными моделями стека могут служить
колода карт на столе при игре

в покер,
книги, сложенные в стопку,
или стопка тарелок на полке буфета.
Во всех этих моделях взять можно только верхний предмет, а добавить новый объект можно, только положив его на верхний.

Определение

Слайд 6

Области применения стека:
передача параметров в функции;
трансляция (синтаксический и семантический анализы,

генерация кодов и т.д.);
реализация рекурсии в программировании;
реализация управления динамической памятью и т.п.

Определение

Слайд 7

Логическая структура стека представлена на рисунке.
Определение
Элементы стека могут иметь как

одинаковые, так и различные размеры.
Последний добавленный в стек элемент еn, называется вершиной стека (top of stack).
Важной составляющей структуры стека является указатель, направленный к вершине, − этот указатель называется указателем стека (stack pointer).
Элемент, непосредственно примыкающий к нижней границе, называется дном стека (bottom of stack).

Слайд 8

1. MAKENULL(S).
Делает стек S пустым.
2. TOP(S).
Возвращает элемент из

вершины стека S.
Обычно вершина стека идентифицируется позицией 1, тогда TOP(S) можно записать в терминах общих операторов списка как
RETRIEVE(FIRST(S), S).
3. POP(S).
Удаляет элемент из вершины стека (выталкивает из стека).
В терминах операторов списка этот оператор можно записать как
DELETE(FIRST(S), S).

Операторы, выполняемые над стеком

Слайд 9

4. PUSH(x, S).
Вставляет элемент х в вершину стека S (заталкивает

элемент в стек).
Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной, и т.д.
В терминах общих операторов списка данный оператор можно записать как
INSERT(x, FIRST(S), S).
5. EMPTY(S).
Эта функция возвращает значение
true (истина), если стек S пустой,
и значение false (ложь) в противном случае.

Операторы, выполняемые над стеком

Слайд 10

Все текстовые редакторы имеют определенные символы, которые служат в качестве стирающих

символов,
т.е. таких, которые удаляют (стирают) символы, стоящие перед ними;
эти символы "работают" как клавиша на клавиатуре компьютера.
Например, если символ # определен стирающим символом,
то строка abc#d##e в действительности является строкой ае.
Текстовые редакторы имеют также символ-убийцу, который удаляет все символы текущей строки, находящиеся перед ним.
В этом примере в качестве символа-убийцы определим символ @.

Пример

Слайд 11

Операции над текстовыми строками часто выполняются с использованием стеков.
Текстовый редактор

поочередно считывает символы.
Если считанный символ не является ни символом-убийцей, ни стирающим символом, то он помещается в стек.
Если вновь считанный символ – стирающий символ, то удаляется символ в вершине стека.
В случае, когда считанный символ является символом-убийцей, редактор очищает весь стек.
В листинге на след. слайде представлена программа, реализующая действия стирающего символа и символа-убийцы.

Пример

Слайд 12

Пример
procedure EDIT;
var s: STACK; с: char;
begin
MAKENULL(S);
while not

eoln do begin
read(c);
if с = '#' then POP(S)
else if с = '@‘ then MAKENULL(S)
else { с — обычный символ }
PUSH(c, S)
end;
печать содержимого стека S в обратном порядке
end; { EDIT }

В этом листинге используется стандартная функция языка Pascal eoln, возвращающая значение true, если текущий символ – символ конца строки.

Слайд 13

В этой программе тип STACK можно объявить как список символов.
Процесс

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

Пример

Слайд 14

Стеки могут представляться в памяти
либо в виде вектора (массива) –

статическая реализация,
либо в виде связного списка – динамическая реализация.

Реализация стеков

Слайд 15

При векторном представлении под стек отводится сплошная область памяти, достаточно большая,

чтобы в ней можно было поместить некоторое максимальное число элементов, которое определяется решаемой задачей.
Граничные адреса этой области являются параметрами физической структуры стека – вектора.
В процессе заполнения стека место последнего элемента (его адрес) помешается в указатель вершины стека.

Реализация стеков

Слайд 16

Если указатель выйдет за верхнюю границу стека, то стек считается переполненным

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

Реализация стеков

Слайд 17

При списковом представлении стека память под под каждый элемент стека получают

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

Реализация стеков

Слайд 18

Каждую реализацию списков можно рассматривать как реализацию стеков, т.к. стеки с

их операторами являются частными случаями списков с операторами, выполняемыми над списками.
Надо просто представить стек в виде однонаправленного списка,
так как в этом случае операторы PUSH и POP будут работать только с ячейкой заголовка и первой ячейкой списка.
Фактически заголовок может быть и указателем, а не полноценной ячейкой,
поскольку стеки не используют такого понятия, как "позиция",
и, следовательно, нет необходимости определять позицию 1 таким же образом, как и другие позиции.

Реализация стеков массивами

Слайд 19

Однако реализация списков на основе массивов не очень подходит для представления

стеков,
так как каждое выполнение операторов PUSH и POP в этом случае требует перемещения всех элементов стека
и поэтому время их выполнения пропорционально числу элементов в стеке.

Реализация стеков массивами

Слайд 20

Можно более рационально приспособить массивы для реализации стеков, если принять во

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

Реализация стеков массивами

Слайд 21

Для такой реализации стеков можно определить абстрактный тип STACK следующим образом:
Реализация

стеков массивами

type
STACK = record
top: integer;
element: array[1..maxlength] of elementtype
end;

В этой реализации стек состоит из последовательности элементов
element[top], element[top + 1], ..., element[maxlength].
Если top = maxlength+1, то стек пустой.

Слайд 22

Реализация стеков массивами: операторы
procedure MAKENULL ( var S: STACK );
begin

S.top:= maxlength + 1
end; { MAKENULL }
function EMPTY ( S: STACK ): boolean;
begin
if S. top > maxlength then
EMPTY:=true
else EMPTY:=false
end; { EMPTY }

Слайд 23

Реализация стеков массивами: операторы
function TOP ( var S: STACK ): elementtype;

{ Возвращает элемент из вершины стека S. }
begin
if EMPTY(S) then
error('Стек пустой’)
else TOP:= S.elements[S.top]
end; { TOP }
procedure POP ( var S: STACK );
{ Удаляет элемент из вершины стека (выталкивает из стека). }
begin
if EMPTY(S) then
error('Стек пустой')
else S.top:= S.top + 1
end; { POP }

Слайд 24

Реализация стеков массивами: операторы
procedure PUSH ( x: elementtype; var S: STACK

);
{ Вставляет элемент х в вершину стека S (заталкивает элемент в стек). }
begin
if S.top = 1 then error('Стек полон')
else begin
S.top:= S.top - 1
S.elements[S.top]:= x
end
end; { PUSH }

Слайд 25

Стек как динамическую структуру данных легко организовать на основе линейного списка.

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

Реализация стеков списком

Слайд 26

Логическая схема стека на основе линейного списка:
Реализация стеков списком
type celltype

= record
element: elementtype;
next: ^ celltype
end;
STACK = ^ celltype;
var top: STACK;

Слайд 27

Реализация стеков списком
Реализация основных операций со стеком приведена в виде соответствующих

процедур.
Приведены их два варианта:
с использованием процедур операций с линейным однонаправленным списком;
самостоятельная реализация – без таких процедур.

Слайд 28

Реализация стека на базе линейного однонаправленного списка:
Реализация стеков списком
procedure Push(x:

elementtype;
var top: STACK);
{Запись элемента в стек (положить в стек)}
begin
InsFirst_SingleList(x, top);
end; { PUSH }
procedure Pop(var x: elementtype;
var top: STACK);
{Чтение элемента из стека (снять со стека) с удалением }
begin
if top <> nil then begin
x := top^.element;
Del_SingleList(top, top); {удаляем вершину}
end;
end; { POP }

Слайд 29

Реализация стеков списком
procedure MAKENULL(var top: STACK);
{Очистка стека}
begin
while top <>

nil do
Del_SingleList(top, top); {удаляем вершину}
end; { MAKENULL }
function Empty(top: STACK): boolean;
{Проверка пустоты стека}
begin
if top = nil then Empty := true
else Empty := false;
end; { EMPTY }

Слайд 30

Реализация стека отдельными процедурами:
Реализация стеков списком
function Empty( top: STACK) :boolean;
begin
Empty:=

Top=nil;
end; { EMPTY }
procedure Push(x: elementtype; var top: STACK);
{добавление элемента в стек}
Var p: STACK;
begin
new(p); {создаем новый узел}
p^.next:= top; {он будет находиться перед вершиной}
p^.element:= х;
top:=p; {Делаем p вершиной стека}
end; { PUSH }

Слайд 31

Реализация стеков списком
procedure Pop(var top: STACK; var x: elementtype);
{Возвращает число из

вершины стека и затем уничтожает вершину}
Var p: STACK;
begin
if Empty(top)=False then begin
p:= top^.next; {запоминаем следующий узел}
x:=top^.element; {вытаскиваем инф-цию из вершины}
dispose(top); {уничтожаем вершину}
top:=p; {делаем p вершиной}
end else
error('стек уже пуст‘)
end; { POP }

Слайд 32

2. Решение задачи проверки правильности расстановки скобок

Слайд 33

Задача
Задача: вводится символьная строка, в которой записано выражение со скобками трех

типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры:
[()]{} ][ [({)]}
Упрощенная задача: то же самое, но с одним видом скобок.
Решение: счетчик вложенности скобок. Последовательность правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным.

Слайд 34

Решение задачи со скобками
Алгоритм:
в начале стек пуст;
в цикле просматриваем все символы

строки по порядку;
если очередной символ – открывающая скобка, заносим ее на вершину стека;
если символ – закрывающая скобка, проверяем вершину стека: там должна быть соответствующая открывающая скобка (если это не так, то ошибка);
если в конце стек не пуст, выражение неправильное.

[ ( ( ) ) ] { }

Слайд 35

© С.В.Кухта, 2010
Реализация стека (массив)
Структура-стек:
const MAXSIZE = 100;
type Stack = record

{ стек на 100 символов }
data: array[1..MAXSIZE] of char;
size: integer; { число элементов }
end;

Добавление элемента:

procedure Push( var S: Stack; x: char);
begin
if S.size = MAXSIZE then
writeln(’Стек полон’)
else begin
S.size := S.size + 1;
S.data[S.size] := x;
end;
end;

ошибка: переполнение стека

добавить элемент

Слайд 36

Реализация стека (массив)
function Pop ( var S:Stack ): char;
begin
if S.size

= 0 then begin
Pop := char(255);
end else begin
Pop := S.data[S.size];
S.size := S.size - 1;
end;
end;

Снятие элемента с вершины:

Пустой или нет?

Function Empty ( S: Stack ): Boolean;
begin
Empty := (S.size = 0);
end;

ошибка: стек пуст

Слайд 37

© С.В.Кухта, 2010
Программа
var br1, br2, expr: string;
i, k: integer;
upper:

char; { то, что сняли со стека }
error: Boolean; { признак ошибки }
S: Stack;
begin
br1 := '([{'; br2 := ')]}';
S.size := 0;
error := False;
writeln('Введите выражение со скобками');
readln(expr);
... { здесь будет основной цикл обработки }
if not error and Empty(S) then
writeln('Выражение правильное.')
else writeln('Выражение неправильное.')
end.

открывающие скобки

закрывающие скобки

Слайд 38

Обработка строки (основной цикл)
for i:=1 to length(expr) do begin
for

k:=1 to 3 do begin
if expr[i] = br1[k] then begin { откр. скобка }
Push(S, expr[i]); { втолкнуть в стек}
break;
end;
if expr[i] = br2[k] then begin { закр. скобка }
upper := Pop(S); { снять символ со стека }
error := upper <> br1[k];
break;
end;
end;
if error then break;
end;

цикл по всем символам строки expr

цикл по всем видам скобок

ошибка: стек пуст или не та скобка

была ошибка: дальше нет смысла проверять

Слайд 39

Реализация стека (список)
Добавление элемента:
Структура узла:
type PNode = ^Node; { указатель на

узел }
Node = record
data: char; { данные }
next: PNode; { указатель на след. элемент }
end;

procedure Push( var top: PNode; x: char);
var NewNode: PNode;
begin
New(NewNode); { выделить память }
NewNode^.data := x; { записать символ }
NewNode^.next := top; { сделать первым узлом }
top := NewNode;
end;

Слайд 40

Реализация стека (список)
Снятие элемента с вершины:
function Pop ( var top: PNode

): char;
var q: PNode;
begin
if top = nil then begin { стек пуст }
Pop := char(255); { неиспользуемый символ }
end else begin
Pop := top^.data; { взять верхний символ }
q := top; { запомнить вершину }
top := top^.next; { удалить вершину из стека }
Dispose(q); { удалить из памяти }
end;
end;

Слайд 41

Реализация стека (список)
Изменения в основной программе:
var S: Stack;
...
S.size := 0;
var S:

PNode;

S := nil;

Пустой или нет?

function Empty ( S: Stack ): Boolean;
begin
Empty := (S = nil);
end;

Слайд 42

3. Решение задачи вычисления арифметических выражений

Слайд 43

Одно из применений стеков можно продемонстрировать на примере вычисления значения арифметического

выражения в калькуляторах.
Пусть арифметическое выражение составлено из комбинации
чисел,
знаков бинарных арифметических операций (операторов)
+, -, *, /, ^,
круглых скобок (, )
и пробелов.
Алгоритм вычисления предусматривает представление выражения в определенном формате.

Слайд 44

a b + c d + 1 - /
Как вычислять автоматически?
Инфиксная

запись
(знак операции между операндами)

(a + b) / (c + d – 1)

необходимы скобки!

Постфиксная запись (знак операции после операндов)

польская нотация,
Jan Łukasiewicz (1920)

скобки не нужны, можно однозначно вычислить!

Префиксная запись (знак операции до операндов)

/ + a b - + c d 1

обратная польская нотация,
F. L. BauerF. L. Bauer and E. W. Dijkstra

Формы записи арифметических выражений

Слайд 45

В калькуляторах чаще всего применяется представление выражения в
инфиксной форме –

для записи исходного выражения;
и постфиксной форме – для автоматического вычисления выражения.
В обеих формах выражения представляются в виде символьных строк.

Формы записи арифметических выражений

Слайд 46

В инфиксной форме записи каждый бинарный оператор помещается между двумя своими

операндами.
Для уточнения порядка вычислений могут использоваться круглые скобки.
Инфиксный формат записи используется в большинстве языков программирования и калькуляторах и практически совпадает с естественной формой записи выражения.
Примеры записи выражений:
5.7 + 6.8 =
15 * 4 + (25 / 2 - 3) ^ 2 =
3 * 7.5 + 6е2 / 5.0 =

Формы записи арифметических выражений

Слайд 47

В постфиксной форме записи (обратной польской записи ОПЗ, или Reverse Polish

Notation RPN) операнды предшествуют своему оператору.
Примеры записи выражений:
5.7 6.8 + =
15 4 * 25 2 / 3 - ^ + =
3 7.5 * 6е2 5.0 / + =

Формы записи арифметических выражений

Слайд 48

Наиболее простым является алгоритм вычисления постфиксного выражения.
Исходная строка содержит элементы

только двух видов: числа и операторы.
Пусть выражение заканчивается символом '='.
Алгоритм использует один стек, элементами которого являются числа вещественного типа.

Постфиксный калькулятор

Слайд 49

Алгоритм вычисления постфиксного калькулятора.
Из исходной строки выделяется очередной элемент.
Если элемент

– число, то оно заносится в стек. Переход к п.1.
Если элемент – оператор, то из стека последовательно извлекаются два элемента,
сначала правый операнд,
затем левый операнд
и над ними выполняется операция, определенная оператором.
Результат операции (число) заносится в стек.
Переход к п.1.
Пункты 1 – 3 выполняются до тех пор, пока в исходной строке не встретится признак конца выражения '='.
В этом случае число, находящееся в стеке, является результатом вычисления.

Постфиксный калькулятор

Слайд 50

Рассмотрим порядок вычисления выражения
3 7.5 * 6е2 5 / + =

Шаг 1. Из строки выделяется число 3 и помещается в стек. Стек: 3.
Шаг 2. Из строки выделяется число 7.5 и помещается в стек. Стек: 3 7.5.
Шаг 3. Из строки выделяется оператор '*'. Из стека извлекаются числа 7.5 и 3. Выполняется операция 3*7.5, результат 22.5 помещается в стек. Стек: 22.5.
Шаг 4. Из строки выделяется число 6е2 и помещается в стек. Стек: 22.5 600.
Шаг 5. Из строки выделяется число 5 и помещается в стек. Стек: 22.5 600 5.
Шаг 6. Из строки выделяется оператор '/'. Из стека извлекаются два числа 5 и 600. Выполняется операция 600/5, и результат 120 помещается в стек. Стек: 22.5 120.
Шаг 7. Из строки выделяется оператор '+'. Из стека извлекаются два числа 120 и 22.5. Выполняется операция 22.5+120. Результат 142.5 засылается в стек.
Шаг 8. Из строки выделяется символ '=' - признак конца выражения. Из стека извлекается результат вычисления - число 142.5.

Постфиксный калькулятор

Слайд 51

Постфиксная форма:
a b + c d + 1 - /
X

Постфиксный калькулятор

Слайд 52

Алгоритм преобразования выражения из инфиксной формы в постфиксную основан на методе

стека с приоритетами.
В нем всем операторам и скобкам-разделителям ставятся в соответствие целочисленные приоритеты.
Чем старше операция, тем выше ее приоритет.
Открывающая скобка имеет низший приоритет, равный 0,
закрывающая скобка – равный 1.
В ходе обработки исходной строки
операнды переносятся в выходную строку непосредственно,
а операторы – через стек в соответствии со своими приоритетами.