 |
Алгоритм Дейкстры формирования ПолИЗа
|
|
|
|
ПРИОРИТЕТ ОПЕРАЦИИ – это целое число, означающее старшинство операции по отношению к другим операциям. Приоритет операций изменяется с использованием скобок ( и ).
Исходная последовательность просматривается слева на право, как входная последовательность элементов.
АЛГОРИТМ:
1. Если элемент операнд, то он заносится в ПолИЗ.
2. Если элемент операция, то она заносится в ПолИЗ через СТЕК по правилу.
2.1. Если СТЕК пуст, то знак операции заносится в СТЕК,
2.2. Иначе: если приоритет входного знака равен 0, то он заносится в СТЕК, иначе сравниваются приоритеты входного знака и знака в вершине СТЕКа.
2.3. Если приоритет входного знака больше приоритета знака в вершине СТЕКа, то он заносится в СТЕК.
2.4. Иначе из СТЕКа выталкиваются все знаки с приоритетом больше или равным приоритету входного знака в вершине СТЕКа и приписываются к ПолИЗу, затем входной знак заносится в СТЕК.
3. Особо обрабатываются ( и ).
( - имея приоритет 0 сразу же заносится в СТЕК по 2.2.
) – имея приоритет равный 1 выталкивает из СТЕКа все знаки до ближайшей открывающей скобки (, затем они взаимно уничтожаются.
4. При появлении признака конца выражения (в нашем случае;) СТЕК очищается: все оставшиеся знаки выталкиваются и приписываются к ПолИЗу.
Так же ПолИЗу соответствует так называемое дерево ПолИЗа.
Пример: (x+a)*(x-b)+3;
Дерево:
 | |||||||||||||||||||
 |  | ||||||||||||||||||
 |  | ||||||||||||||||||
 |  | ||||||||||||||||||
 |  | ||||||||||||||||||
 |  |  | | ||||||||||||||||
x a x b
ПолИЗ: x a + x b - * 3 +.
Построение ПолИЗа по дереву осуществляется обходом дерева по правилу левое поддерево, правое поддерево, корень.
|
|
|
ПолИЗ выражений, содержащих переменные синтаксиса
Кроме операций сложения и умножения любая программа содержит операции вычисляющие адреса элементов массива в зависимости от индексных выражений. Например:
a[i+1]-b[i,j-1]*a[2*i+1]
 |  | ||||
 | |||||
Индексные выражения.
Выведем формулы вычисления адресов элементов массива.
Для одномерного массива а, описание которого на Паскале и Си имеет вид:
a: array [1..n] of integer; // Pascal
int a[n]; // C/C++
и каждый элемент имеет массива занимает k-байт.
Адрес первого элемента равен A. Выясним чему будут равны адреса других элементов. Для этого рассмотрим расположение элементов массива в физической памяти ЭВМ.
A +k +2k +3k A+k*(i-1)…
k байт
тогда a[i] А+k*(i-1) для языка программирования Паскаль, а для языка программирования C/C++ a[i] A+k*i. Тогда если элемент занимает k – байт, то
a[i] -----> A+k*(i-1) (1)
a[i] -----> A+k*i (1’)
Для двумерного массива:
b: array [1..m,1..n] of integer;// Pascal
int b[m][n];//Си
Адрес элемента с индексами i,j вычисляется по правилу:
b[i,j] -----> B+k*((i-1)*n+(j-1)) (2)
b[i,j] -----> B+k*(i*n+j) (2’)
Для формирования ПолИЗа введем операцию АЭМ (адрес элемента массива) с операндами:
1. Идентификатор массива, ему после распределения памяти транслятором будет соответствовать адрес первого элемента массива.
2. Индексное выражение.
Результат: адрес элемента массива вычисленный по формулам (1)-(2’).
ПолИЗ: a i 1 + А.Э.М. b i j 1 – А.Э.М. a 2 i * 1 + А.Э.М. * -
Анализ ПолИЗа говорит о том, что у операции АЭМ переменное число операндов и их количество надо задавать явно. Сделаем следующую замену: АЭМ – k], где k - количество операндов.
Тогда ПолИЗ: a i j + 2] b i j 1 – 3] a 2 i * 1 + 2] * -.
Изобразим дерево выражения: (смотри рисунок)
-
 |  |
А.Э.М. *
 |  |  |  |
|
|
|
а + А.Э.М. А.Э.М.
 |  |  |  |  |
i 1 b i – a +
 |  | |  |
i j * 1
 | |
2 i
Следовательно, алгоритм Дейкстры дополнится следующими правилами:
ПРАВИЛА:
1. [, имея приоритет 0 заносится в СТЕК [k, где k – минимальное число операндов операции А.Э.М.
2.,, имея приоритет 1 выталкивает из СТЕКа все ближайшие знаки до ближайшей [k и увеличивает k на 1: k=k+1;, никуда не заносится.
3. ], имея приоритет 1 выталкивает из СТЕКа все знаки до ближайшей [k, которая удаляется из СТЕКа, а в ПолИЗ заносится k].
|
|
|
