тогда 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].

4.3.4.3. Алгоритм перевода ПолИЗа в машинные команды

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

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

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

Рассмотрим пример: a+b*c-d/(a+b)

ПолИЗ: abc*+dab+/-

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