- •4. Динамические структуры
- •4.1. Данные динамической структуры
- •4.2. Линейные связанные структуры данных
- •5.3.1. Создание лс.
- •5.3.2. Вывод списка
- •5.3.2. Удаление элемента из списка.
- •5.3.2. Вставка в отсортированный список.
- •5.3.3. Слияние двух отсортированных списков в третий отсортированный список.
- •5.4. Линейный двусвязный список.
- •5.4.1. Создание 2-связного списка.
- •5.4.2. Удаление в 2-связном списке.
- •5.4.2. Вставка заданного элемента в отсортированный 2-связный список.
- •5.5. Стек.
- •5.6. Пример вычисления арифметического выражения с помощью стеков.
5.5. Стек.
Стек — частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной стека (рис. 5.2). Такой принцип доступа к данным называется LIFO (Last In First Out – «последним пришел – первым вышел»). Голову списка в данном случае называют еще указателем стека (stack pointer –sp, однако в целях общности будем как и прежде придерживаться обозначения h).
Стек имеет важное значение для организации межмодульного взаимодействия, организации прерываний, рекурсивных вычислений и еще много других полезных применений, с которыми мы познакомимся в ходе изучения различных алгоритмов.
Удобно все операции со стеком оформить в виде процедур и функций и поместить в отдельный модуль. Ниже приводится пример такого модуля, в котором информационное поле элемента стека относится к символьному типу. Если нужен стек с другим типом элементов, то в этот модуль необходимо внести соответствующие изменения.
UNIT Stack;
INTERFACE
Type u = ^Uzl;
Uzl = Record
i :Char; {информационное поле символьного типа }
L :u;
End;
{ далее h – формальный параметр ! }
Procedure Push ( Var h :u; a :Char ); { включение в стек нового элемента.}
Function Pop ( Var h :u ) :Char; {исключение элемента из стека }
Function Empty ( h :u ) :Boolean; {функция «пустой» стек}
Function Top ( h :u ) :Char; {функция возвращает копию вершины}
IMPLEMENTATION
Procedure Push;
Var t :u;
Begin New(t); t^.i := a; t^.L := h; h := t; End;
Function Pop;
Var t :u;
Begin Pop := h^.i; t := h; h := h^.L; Dispose ( t ); End;
Function Empty; Begin Empty := h = Nil; End;
Function Top; Begin Top := h^.i; End;
End.
5.6. Пример вычисления арифметического выражения с помощью стеков.
Одно из интереснейших применений стека - синтаксический разбор и вычисление выражения, например, арифметического. Пусть дана строка, являющаяся записью арифметического выражения. Возможно наличие бинарных операций '+', '-', '*', '/', левой и правой круглых скобок, в качестве операндов для простоты будем использовать цифры от 0 до 9. Выражение заканчивается знаком '='. Например, допустимым будет выражение 4-2/6*(2+3*6)=. Необходимо написать программу, вычисляющую значение этого выражения или выдающую сообщение об ошибке в нем.
Попробуем сформулировать основные положения, которые нам понадобятся для вычисления выражения.
Операции выражения в скобках выполняются первыми, т.е. имеют наивысший приоритет. Для выражения, находящегося в скобках, правила вычисления выражения те же, что и для обычного выражения.
Наивысший приоритет из четырех возможных арифметических операций имеют операции умножения и деления. При отсутствии скобок эти операции выполняются раньше, чем сложение и вычитание.
Операции с равными приоритетами выполняются в порядке их появления в выражении.
Рассмотрим для начала выражение без скобок, например 8/2+3*4=. Сначала надо выполнить деление, далее - умножение, а затем - сложение. Причем складывать надо результаты первой и второй операций. Будем разбирать выражение по символу. Первый символ 8 - операнд, он нам понадобится позже, поэтому временно поместим его в стек операндов. Следующий символ - знак деления. Мы не знаем, что нам встретится позднее, возможно скобка, поэтому надо ли выполнять деление прямо сейчас, мы сказать не можем. Следовательно, поместим на время этот символ в стек операций. Следующий символ - тоже операнд, и мы поместим его в стек операндов. Далее идет знак сложения. Посмотрим, какие операции встречались до сложения, не надо ли их выполнить раньше. На вершине стека операций находится символ операции деления. Операция деления имеет больший приоритет, чем операция сложения, поэтому выполним теперь деление. Для этого вынем знак операции деления из стека операций, а также возьмем из стека операндов два верхних операнда: сначала - правый (2), затем -левый (8). Поделим левый операнд на правый. Получим значение 4. Оно понадобится нам и позже, поэтому временно положим его в стек операндов. Теперь текущим рассматриваемым символом является знак сложения. Если в стеке операций есть еще элементы, которые надо выполнить до сложения, то выполним их. Но у нас стек пуст. Какие операции встретятся дальше, мы не знаем, поэтому поместим пока знак сложения в стек операций и перейдем к следующему символу. Это операнд 3, поместим его в стек операндов. Перечислим снизу вверх элементы стека операндов: (4, 3). Далее следует знак умножения. Проверим, не было ли у нас операций, которые должны были быть до него выполнены (например, другое умножение). Верхним элементом в стеке операций у нас является знак сложения, так как умножение должно выполняться раньше, поместим его в стек над сложением. Таким образом, стек операций выглядит в следующим виде: ('+','*'). Следующий символ - операнд 4. Поместим его в стек операндов, в котором теперь будут храниться уже три элемента: (4, 3, 4). Следующий символ - знак равенства, означающий конец выражения. На вершине стека операций у нас знак умножения. Выполним эту операцию, вынув ее из стека и взяв два верхних операнда из стека операндов. Левый операнд у нас 3, а правый - 4. Результатом умножения будет 12. Поместим этот результат в стек операндов, теперь там два элемента: (4, 12). На вершине стека операций находится знак сложения. Выполним эту операцию. Левым операндом будет 4, правым - 12. Результатом будет 16, поместим 16 в стек операндов. Стек операций пуст, значит, в стеке операндов у нас находится результат. Удалим его из стека и выведем на экран. У нас получился верный результат вычисления выражения 8/2+3*4.
Заметим, что для элементов стека операндов неудобно использовать тип Char, как для элементов стека операций. Целесообразно элементы стека операндов объявить как вещественные числа.
Схема алгоритма:
1
8
/
2
+
3
*
4
=
2. / So; ( So – стек операций)
3. 2 Sd;
4. + ; смотрим Sо , там /, p( / ) > p( + ), поэтому выполним операцию / ;
8 : 2 = 4 Sd .
5. Смотрим So. Если So ≠Ǿ и p(операции) > p( + ), то эти операции
должны быть выполнены. Но у нас So= Ǿ, поэтому
+ So.
6. 3 Sd;
7. * : смотрим So → там + ; так как p ( + ) < p( * ), поэтому
* So;
8. 4 Sd;
9. = конец выражения.
4 * 3 = 12 Sd;
4 +12 = 16 Sd;
Sd Ответ =16
Теперь посмотрим, какие необходимо выполнить действия, если в выражении есть скобки. В качестве примера разберем выражение 4*(2+3)=. Первый символ - операнд. Поместим его в стек операндов. Следующий символ - знак умножения. Операций, которые надо было выполнить до него, у нас нет, поэтому поместим этот символ в стек операций. Далее следует левая скобка. Это означает, что то, что будет записано далее, должно вычисляться раньше, чем то, что мы рассматривали до сих пор. Поместим левую скобку в стек операций, состояние стека: ( '*','(' ). Далее у нас следует операнд. Поместим его в стек операндов, состояние стека операндов: (4, 2). Следующий символ - знак сложения. На вершине стека находится скобка, таким образом, у нас нет ничего, что надо было выполнить до сложения. Поместим сложение в стек операций, который теперь содержит три элемента: ( '*','(','+' ). Следующий символ - операнд. Поместим его в стек операндов, который теперь имеет следующее содержимое: (4, 2, 3). Далее у нас идет правая скобка, следовательно, выражение в скобках на этом заканчивается, надо его вычислить. Верхней операцией у нас является сложение, выполним его. В стеке операций у нас теперь два элемента: ('*', '(' ), в стеке операндов – тоже два: (4, 5). Выполним все операции, которые содержались в скобках, удалим из стека операций левую скобку (если ее в стеке нет, значит, в выражении была допущена ошибка). Перейдем теперь к следующему символу. Это знак '=', означающий конец выражения. Выполним верхнюю операцию в стеке – умножение. Теперь стек операций у нас пуст, а в стеке операндов хранится число 20. Это и есть результат вычисления нашего выражения.
Итак, для каждого символа в выражении предусмотрены различные действия, причем действия с операциями зависят не только от самой операции, но и от того, что находится на вершине стека операций. Рассмотрим возможные варианты.
Для символов '+' и '-' правила одинаковы:
1. Если стек пуст или верхний элемент - левая скобка, поместим операцию в стек и перейдем к следующему символу.
2. Если на вершине стека операция с равным приоритетом, выполнить ее, поместить рассматриваемую в данный момент операцию в стек и перейти к следующему символу.
3. Если на вершине стека операция с высшим приоритетом, выполнить эту операцию. Так как возможно, что до сложения или вычитания встретилась не одна операция, которая должна быть выполнена раньше рассматриваемой в данный момент, то к следующему символу пока не переходим.
Правила для операций умножения и деления (для символов '*' и '/').
1. Если стек пуст или на вершине находится левая скобка или операция с меньшим приоритетом, операция помещается в стек, и переходят к следующему символу.
2. Если на вершине стека находится операция с равным приоритетом, необходимо выполнить ее и поместить рассматриваемую в данный момент операцию в стек и перейти к следующему символу.
В случае левой скобки необходимо добавить символ в стек операций и перейти к следующему символу.
В случае правой скобки возможны следующие варианты:
1. Стек пуст. Следовательно, не хватает левой скобки, т.е. выражение ошибочно.
2. На вершине - левая скобка. Следовательно, выражение в скобках кончилось, удаляем левую скобку из стека и переходим к следующему символу.
3. На вершине стека - арифметическая операция. Вынимаем операцию из стека и выполняем ее.
И наконец, рассмотрим действия, необходимые для обработки символа конца выражения.
1.Если стек пуст, то выражение вычислено. Следовательно, нужно удалить из стека операндов результат и вывести его.
2. На вершине - левая скобка. Следовательно, левых скобок в выражении было больше, чем правых, т.е. выражение ошибочно.
3. На вершине стека - арифметическая операция. Необходимо удалить ее из стека и выполнить.
Итак, у нас шесть возможных вариантов действий. Для выбора того или иного действия необходимо проверить сочетание состояния вершины стека операций и рассматриваемый символ. Чтобы ускорить выбор нужной операции, составим матрицу, элементы которой будут соответствовать номеру действия, необхо
|
текущая операция из входной строки | |||||||
= |
( |
+ |
- |
* |
/ |
) | ||
вершина стека операций |
пусто |
5 |
1 |
1 |
1 |
1 |
1 |
0 |
( |
0 |
1 |
1 |
1 |
1 |
1 |
3 | |
+ |
4 |
1 |
2 |
2 |
1 |
1 |
4 | |
- |
4 |
1 |
4 |
4 |
2 |
2 |
4 | |
* |
4 |
1 |
4 |
4 |
2 |
2 |
4 | |
/ |
4 |
1 |
2 |
2 |
1 |
1 |
4 | |
Табл. 5.2. Таблица решений для выбора действия. |
0 – ошибка;
1 – положить операцию в стек и перейти к следующему символу выражения;
2 – выполнить верхнюю операцию, положить рассматриваемую операцию в стек и перейти к следующему символу выражения;
3 – извлечь из стека операций верхний элемент и перейти к следующему символу выражения;
4 – выполнить верхнюю операцию;
5 – состояние конца выражения.
Воспользуемся процедурами, описанными в модуле Stack для работы со стеком операций и напишем аналогичный модуль для работы со стеком данных. Далее составим программу вычисления арифметического выражения.
Program Compute;
Uses CRT, So, Sd; { So –стек для знаков операций;
Sd – стек для данных. }
Const tab:Array[0..5,0..6] Of Byte =( ( 5, 1, 1, 1, 1, 1, 0 ),
( 0, 1, 1, 1, 1, 1, 3 ),
( 4, 1, 2, 2, 1, 1, 4 ),
( 4, 1, 2, 2, 1, 1, 4 ),
( 4, 1, 4, 4, 2, 2, 4 ),
( 4, 1, 4, 4, 2, 2, 4 ) );
Var ho :w; h :u; {указатели для стеков операций и данных}
v :String; {в v исходное арифметическое выражение }
Ok, f :Boolean; {флаги корректности и завершения}
j, k :Integer; c :Char; res, x :Real; {рабочие переменные}
.......................................................................................................................................
Function NumAct ( sp :w; op :Char ) :Byte;
{ возвращает номер действия из таблицы tab; op – операция из вх. строки v }
Var i :Byte;
Begin
If EmptyO(sp) Then i := 0 Else i := Pos ( TopO(sp), '( + - * / ) ' );
NumAct := tab [ i, Pos( op, ' = ( + - * / ) ' ) – 1 ];
End;
Function Calc ( op :Char; Var sp: u ) :Boolean;
{вычисляет операцию ор, результат помещает в стек данных;
если успешно, то возвращает True.}
Var x, y :Real;
Begin
Calc := True;
If Empty( sp ) Then Begin Calc := False; Exit; End;
y := Pop ( sp );
If Empty( sp ) Then Begin Calc := False; Exit; End;
x := Pop ( sp );
Case op Of
'+': x := x + y;
'-': x := x - y;
'*': x := x * y;
'/': If y=0 Then Calc := False Else x := x / y;
End;
Push ( sp, x );
End;
.......................................................................................................................................
Begin { головная программа}
ClrScr;
v := ' 4 * ( 2 + 3 ) / 9 = ' ;
ho := Nil; h := Nil;
j := 1; Ok := True; f := False;
While Not f Do
If v[j] In ['0'..'9']
{если v[j] операнд, то положить его в стек, иначе вып-ть действие из tab}
Then Begin Val ( v[j], x, k ); Push ( h, x ); Inc( j ); End
Else If v[ j ] In [ '(', '+', '-', '*', '/' , ')', '=' ]
Then { если v [ j ] есть операция}
Case NumAct( ho, v[j] ) Of
{ошибка в выражении} 0: Begin Ok := False;
f := True;
End;
{операцию в стек} 1: Begin PushO ( ho, v[j] ); Inc( j ); End;
{выч-ть верх операцию} 2: Begin Ok := Calc ( PopO (ho), h );
f := Not Ok;
{а текущю оп-цию в стек} PushO ( ho, v[j] );
Inc( j );
End;
{ ' ( ' из стека } 3: Begin c := PopO ( ho );
Inc( j ) ;
End;
{ выч-ть верх. оп-цию} 4: Begin Ok := Calc ( PopO(ho), h );
f := Not Ok;
End;
{конец выражения} 5: Begin res := Pop ( h );
Ok := Empty ( h ) And ( j >= Length( v ) );
f := True;
End;
End; {Case}
If Ok Then Writeln ( v, res :10 :6 )
Else Write ( 'ошибка в выражении или деление на 0 ' );
Readkey;
Еnd.