1.2. Использование стека
При разработке алгоритмов трансляции арифметических выражений широко используются наборы данных со стековой организацией. Стек - это упорядоченный набор элементов, в котором внесение новых элементов и выборка имеющихся осуществляются в соответствии с дисциплиной LIFO (Last In - First Out), когда последний внесенный элемент удаляется первым. Графически стек можно представить в виде бесконечной в одну сторону последовательности слов памяти, причем запись и чтение данных возможны только c одного конца, называемого вершиной стека, что показано на рис. 3.
В простейшем случае при работе со стеком определены две операции:
1) занесение элемента в стек;
2) выборка (извлечение) элемента из стека.
При занесении в стек новый элемент размешается следующим за вершиной и сам становится вершиной cтека. При выборке элемента из стека удаляется только один верхний элемент, т.е. вершина. Иногда разрешается считывать элементы, находящиеся ниже вершины, но не допускается изменять их значения или добавлять новые элементы ниже вершины. Пример работы со стеком приведен на рис. 4.
|
Рис. 3. Стек |
Рис. 4. Пример работы со стеком |
При реализации стека для хранения вещественных чисел с использованием массива, например на языке Паскаль, соответствующий тип данных можно определить следующим образом.
type Stack = record
top: integer; {вершина стека}
element: array [1..Max] of real {элементы стека}
end;
Операция записи элемента x в стек S выполняется процедурой Push.
procedure Push(x: real; var S: Stack);
begin
if S.top < Max then
begin
S.top := S.top + 1;
S.element := x;
end
else Error(“Стек заполнен”);
end;
Операция выборки элемента из стека S производится функцией POP.
function Pop(var S: Stack): real;
begin
if S.top > 0 then
begin
Pop := S.element[S.top];
S.top := S.top - 1;
end
else Error(“Стек пустой”);
end;
1.3. Вычисление выражений в польской записи
Выражение, представленное в польской записи, можно вычислить за один просмотр слева направо. При этом для записи операндов и промежуточных результатов используется отек.
Алгоритм вычисления выражений в польской записи можно представить в виде следующей последовательности шагов.
1. Если текущий символ строки польской записи является операндом, то его значение помещается в стек.
2. Если текущий символ является бинарным оператором, то он выполняется над двумя верхними элементами, выбранными из стека. Результат операции записывается в стек.
3. Если текущий символ входной строки - унарный оператор, то он применяется к верхнему элементу стека. Результат помещается в стек.
Шаги 1-3 повторяются до тех пор, пока не будут просмотрены все символы входной строки, представляющей собой польскую запись арифметического выражения. Результат вычисления выражения остается в стеке.
Необходимо еще раз отметить, что стек используется для хранения операндов. Каждый операнд записывается в стек по мере появления. Следовательно, максимальный размер стека ограничен числом операндов, имеющихся в исходном выражении. Однако при работе с большинством постфиксных выражений фактический размер стека оказывается меньшим, чем максимальный, поскольку при выполнении каждой операции удаляются операнды из стека. При этом запись каждого промежуточного результата в стек делает его доступным в виде операнда для следующей операции.
В качестве примера рассмотрим вычисление выражения (2). Предположим, что операнды имеют следующие значения: a = 4, b = 1, c = 5, d = 64, e = 2, f = 5. Процесс вычислений по шагам приведен в следующей таблице.
-
Входной
символ
Первый
операнд
Второй
операнд
Результат
операции
Состояние стека
1
2
3
4
...
a
b
-
c
d
e
f
^
/
+
a = 4
3
e = 2
d = 64
15
b = 1
c = 5
f = 5
32
2
3
15
32
2
17
a
a
3
3
15
15
15
15
15
15
17
b
c
d
d
d
d
2
e
e
32
f