Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Из несинтаксических методов рассмотрим распространенный метод получения обратной польской записи.
Способы записи выражений - прямая и обратная польские записи названы так в честь польского математика Яна Лукашевича.
Рассмотрим сущность обратной польской записи на примере:
Выражение a + b * c – d / (a + b) можно графически представить в виде дерева операций:
Здесь узлы – операции, а ветви – операнды. Левая ветвь – левый операнд, а правая – правый. В каждой ветви операциям, которые выполняются раньше, соответствуют нижележащие узлы. Корневая операция выполняется последней.
Если, начав с нижнего листа самой левой ветви, обойти все листья и узлы так, чтобы ветви рассматривались слева направо, а узел рассматривался только после обхода всех исходящих из него ветвей, как показано стрелками на рисунке, то получится обратная польская запись (ОПЗ): a b c * + d a b + / - .
Если используются только бинарные операции, то такой обход дает следующая рекурсивная процедура:
procedure tree(v);
begin
if v.term then print(v.value)
else begin
tree(v.left)
tree(v.right)
print(v.value)
end;
end;
ОПЗ называют также постфиксной записью. Операнды в ОПЗ располагаются в том же порядке, что и в исходном выражении, а знаки операций при просмотре записи слева направо встречаются в том порядке, в котором нужно выполнять соответствующие действия. В ОПЗ отсутствуют скобки.
Таким образом, выражение можно вычислить в процессе однократного просмотра слева направо.
Если элемент – операнд, то переходим на следующий элемент. Если элемент – знак операции, то она выполняется над операндами, записанными слева от знака операции. Результат записывается вместо операндов и операции, которые вычеркиваются. Просмотр продолжается. В результате останется один элемент – значение выражения.
Аналогично можно записывать и вычислять булевские выражения.
Выражение a + b > - 5 and z - d = 1 + q ^ 2 представляется деревом:
Обход дерева дает ОПЗ a b + 5 из z d – 1 q 2 + = and .
Иногда применяют прямую польскую запись (ППЗ) – префиксную запись.
Узлы обходятся так, чтобы верхний узел рассматривался раньше нижнего, и сразу после рассмотрения очередного узла просматривались слева направо исходящие из него ветви.
Получается + a * b c / d + a b .
В рекурсивной процедуре обхода дерева операций будет сначала выведен знак операции, а потом рассматриваются ветви-операнды.
print(v.value)
tree(v.left)
tree(v.right)
Выражения, записанные в ППЗ, вычисляются справа налево.
Метод, который мы с вами рассмотрим, был предложен в 1960 году голландским ученым, которого зовут Эдсгер Вибе Дейкстра (Edsger Wybe Dijkstra).
Он основан на использовании стека с приоритетами, позволяющего изменить порядок следования знаков операций в выражении так, что получается обратная польская запись.
Каждому ограничителю, входящему в выражение, присваивается приоритет.
|
Приоритеты |
Ограничители |
|
0 1 2 3 4 5 6 7 8 9 10 |
{ ( [ begin if for Ф } ) ] end then else to do , ; := goto OR AND NOT > ≥ = ≠ < ≤ + - * / mod div ИЗ ^ exit, halt |
Операция ИЗ – изменение знака, а Ф – вызов функции .
Арифметическое выражение просматривается слева направо.
Операнды переписываются в выходную строку, а знаки операций помещаются в стек операций.
Выходная строка Операнды Входная стока
Если приоритет входного знака равен 0 или больше приоритета знака находящегося в вершине стека или стек пустой, то новый знак добавляется к вершине стека. В противном случае из стека выталкивается и переписывается в выходную строку знак, находящийся в вершине, а также следующие за ним знаки с приоритетами, большими или равными приоритету входного знака. После того входной знак добавляется к вершине стека.
Особенности имеет лишь обработка скобок. Открывающая круглая скобка просто записывается в стек и не выталкивает ни одного знака. В то же время ее не может вытолкнуть ни один знак, кроме закрывающей скобки. Закрывающая скобка имеет приоритет 1, не превосходящий приоритет любой операции. Поэтому закрывающая скобка вызывает выталкивание всех знаков до ближайшей открывающей скобки включительно. В стек закрывающая скобка не записывается. Открывающая и закрывающая скобки как бы взаимно уничтожаются и в выходную строку не переносятся.
После окончания входной строки происходит выталкивание всех оставшихся в стеке символов и дописывание их к выходной строке.
Пример 1. Привести в обратную польскую запись арифметическое выражение:
a + b * c – d / (a + b)
a b c * + d a b + / -
Пример 2. Перевести логическое выражение
a + b > -5 and z – d = 1 + q ^ 2
a b + 5 ИЗ > z d – 1 q 2 ^ + = and
Пусть требуется вычислить выражение (b + a[i+1, j] * c + d ).
Адрес переменной с индексами дает функция упорядочения.
Пусть массив А: array [i1..k1, …, in..kn] хранится в виде вектора, определяемого описанием B: array [1..N] , где
n
N = ∏ (km - im + 1).
m=1
Функция упорядочения позволяет по индексам элемента исходного массива A[j1,…, jn] вычислить соответствующий индекс элемента l массива В.
n
l = 1 + ∑(jm - im ) Dm , где при отображении массива А в массив В «строками» (т.е. быс-
m=1
трее меняется последней индекс) - Dn = 1 и Dm = ( km+1 – im+1 + 1 ) Dm+1, m = n-1, …, 1 ,
а при отображении «столбцами» - D1 = 1 и Dm = ( km-1 – im-1 + 1 ) Dm-1, m = 2, …, n .
Для определения адреса хранения a элемента A[j1,…, jn] в случае, когда вектор B имеет базу b, формулу функции упорядочения целесообразно преобразовать к виду
n
a = b + c +( ∑ jmDm) t ,
m=1
n
где c = ( ∑ imDm ) t, а t – размер элемента массива в байтах.
m=1
Постоянная величина c, как и коэффициенты Dm зависит только от значений граничных пар в описании массива А.
Для вычисления адреса элемента массива нужно знать базу отображающего вектора b, размерность массива n и n целых чисел. При отображении «строками» это коэффициенты:
c, D1 , …, Dn-1 ,
коэффициент Dn здесь всегда равен 1.
Если надо осуществлять контроль за правильностью обращений к элементам массивов при выполнении программы, то для каждого массива нужно хранить нижнюю и верхнюю границы каждого индекса.
Для распределения памяти необходимо знать число элементов в каждом массиве N. При отображении массива «строками» N = D0 = (k1 – i1 + 1) D1 .
Все перечисленные величины хранятся в виде так называемого «определяющего вектора» массива. Для массивов с одинаковыми описаниями – определяющий тоже вектор один.
Введем операцию АДРЕС ЭЛЕМЕНТА МАССИВА (АЭМ), результат выполнения которой – адрес элемента массива, а операнды – идентификатор массива и значения индексных выражений.
Будем обозначать операцию АЭМ символами k], где k – количество операндов, а ] – знак операции.
Если n – число индексов, то k = n + 1.
Тогда ОПЗ выражения (b + a[i+1, j]) * c + d будет выглядеть следующим образом:
b a i 1 j + 3 ] + c * d + .
Действие квадратных скобок похоже на действие круглых. Открывающая индексная скобка всегда записывается в вершину стека, но вместе с ней в вершину стека записывается и начальное (минимальное) значение счетчиков операндов операции АЭМ, равное 2.
Запятая, разделяющая индексные выражения, выталкивает из стека все знаки операций до ближайшей открывающей индексной скобки исключительно. Каждая запятая добавляет в счетчик операндов операции АЭМ единицу.
Пусть имеется выражение y – f (x, y+1, z).
Введем операцию ФУНКЦИЯ, операнды которой – идентификатор функции и значения (или идентификаторы) ее аргументов, а результат – значение функции (точнее, адрес значения функции).
Будем обозначать операцию ФУНКЦИЯ парой символов kΦ, где k – количество операндов.
Тогда ОПЗ выражения примет вид: y f x y 1 + z 4 Φ - .
Алгоритм перевода в обратную польскую запись функции, имеющей не менее одного параметра, тот же, что для переменной с индексами.
Чтобы отличить открывающую круглую скобку в начале списка фактических параметров от круглой скобки в выражении, можно использовать специальную переменную состояния F (признак функции). Эта переменная обычно имеет значение 0. В момент появления идентификатора функции она принимает значение 1, а после занесения в стек круглой скобки и начального значения счетчика операндов, равного 2, вновь принимает значение 0.
Закрывающая скобка, встретив в стеке открывающую круглую скобку, записанную вместе со значением счетчика операндов, занесет это значение в выходную строку, запишет туда знак Φ и уничтожит в стеке круглую скобку и значения счетчика операндов.
Если функция употребляется без параметров, то указатель функции, как и все идентификаторы, будет перенесен непосредственно в выходную строку.
Одновременно переменная состояния F примет значение 1. Если следующий символ не круглая скобка, то признаку F присваивается значение 0, а в выходную строку заносится запись 1Φ в знак того, что операция ФУНКЦИЯ имеет всего один операнд – идентификатор функции.
Дерево оператора присваивания a := b + c
Его ОПЗ имеет вид: a b c + :=
Приоритет знака присваивания должен быть меньше приоритета знака любой арифметической и логической операции, поскольку операция присваивания выполняется после вычисления выражения.
С другой стороны приоритет знака присваивания должен быть больше приоритетов знаков конца оператора (точка с запятой, end и else), чтобы знак конца оператора очищал стек.
До сих пор мы рассматривали конструкции, в которых порядок действий определяется только старшинством операций и скобками, и в ходе исполнения программы не изменяется.
Такие конструкции изображаются статическим деревом.
Для изображения дерева условного оператора понадобятся динамические деревья.
Для этого введем метки, которыми могут помечаться листья и некоторые узлы динамических деревьев. Введем две операции:
- условный переход по значению «ложь» (УПЛ);
- безусловный переход (БП).
Операция УПЛ имеет два операнда: первый – логическое выражение, а второй – метка.
Если логическое выражение истинно, то операция УПЛ пропускается, а если ложно, то происходит переход на метку.
У операции БП имеется лишь один операнд – метка. Результат перехода БП – переход на метку.
Условный оператор вида: if A then B else C;
где А – логическое выражение;
В и С – операторы, можно представить в виде динамического дерева:
Знак «;» не является знаком операции.
Отвечающий ему узел играет роль пустого узла и служит для объединения нескольких последовательно выполняемых действий.
В ОПЗ знак «;» можно не переносить. Обход дерева дает ОПЗ:
A m1 УПЛ В m2 БП m1: С m2:
Частным случаем условного оператора является оператор: if A then B ;
Его дерево:
Его ОПЗ: A m1 УПЛ В m1:
Ограничители if, then и else играют роль скобок: символ if эквивалентен открывающей скобки, а символы then и else, подобно запятым в списках индексов и фактических параметров, являются закрывающими скобками для предшествующего оператора или выражения и открывающими для последующего.
Закрывающей скобкой для оператора, следующего за else, служит точка с запятой или end.
По этим причинам символу if припишем приоритет 0, а символам then и else – 1.
Рассмотрим особенности обработки:
1. Символ if записывается в стек и используется в качестве «хранителя» рабочих меток операций УПЛ и БП. При появлении символа then запись if превращается в if mi, а появление символа else превращает последнюю в if mi mi+1.
Здесь i – номер очередной рабочей метки.
2. Символ then с приоритетом 1 выталкивает из стека все знаки до первого if исключительно. При этом в выходную строку заносится запись mi УПЛ ,
где i – номер очередной нечетной рабочей метки.
Затем метка mi заносится в таблицу меток; к символу if в вершине стека дописывается mi (получается запись if mi).
3. Символ else с приоритетом 1 выталкивает из стека все знаки до первого if исключительно.
В выходную строку добавляется запись mi+1 БП mi : ,
затем метка mi+1 заносится в таблицу меток, а в вершину стека к записи if mi дописывается метка mi+1 (получается запись if mi mi+1).
4. Конец оператора ( ; или end ) выталкивает из стека его содержимое до записи вида if mi или if mi mi+1 ; такая запись удаляется из стека, а в выходную строку в первом случае записывается mi, а во втором – mi+1: .
Пример: Перевести в ОПЗ оператор if a=b then begin a: =0; goto M end else a: =1 ;
получается
a b = m1 УПЛ a 0 := М БП m2 БП m1: a 1 := m2: .
То же самое получается обходом дерева:
Оператор цикла: for <пц> := <нз> to <кз> do <тц>; можно представить в виде дерева:
Особенности обработки:
1. Символ for играет роль открывающей скобки и имеет приоритет 0. В вершину стека записывается FOR <пц>.
2. Символ to является закрывающей скобкой для предшествующего выражения, поэтому имеет приоритет 1 и выталкивает из стека все знаки до записи FOR. Новая метка mi добавляется в таблицу меток и к записи FOR – получается FOR <пц> mi. В выходную строку записывается mi: <пц>.
3. Символ do является закрывающей скобкой для предшествующего выражения , поэтому имеет приоритет 1 и выталкивает из стека все знаки до записи FOR. Новая метка mi+1 добавляется в таблицу меток и к записи FOR – получается FOR <пц> mi mi+1. В выходную строку записывается <= mi+1 УПЛ.
4. Конец оператора цикла (символы «;» и end). При их появлении стек очищается. Если при этом встретится запись FOR <пц> mi mi+1, то это означает окончание оператора цикла. В выходную строку добавляется запись <пц> <пц> 1 + := mi БП mi+1: После этого запись FOR из стека удаляется.
b
a
d
c
b
a
*
+
/
-
+
2
d
1
5a
q
z
ba
a
+
-
>
=
-
+
>
b
and
a
d
c
b
a
*
+
/
-
+
Стек операций
Знак операции
c
логическое выражение
b
:=
метка
a
метка
УПЛ
+
БП
B
УПЛ
m1:
m1
M
A
0
а
b
;
2:
m2
БП
;
m1:C
УПЛ
m1
B
A
а
m1
1
m2
m2:
m1: а
БП
:=
БП
=
:=
УПЛ
;
;
:=
;
<кз>
УПЛ
:=
+
<пц>
БП
<тц>
<нз>
<пц>
m2
1
m1
m2:
<пц>
<пц>
≤