ПЕРЕВОД В ОБРАТНУЮ ПОЛЬСКУЮ ЗАПИСЬ АРИФМЕТИЧЕСКОГО

ВЫРАЖЕНИЯ

В ы х о д с н т а р я о к а

a a a a a a a a a a a a a a b b b b b b b b b b b b c c c c c c c c c c * * * * * * * * * + + + + + + + + + a d d d d d d d a a a a a b b b + + -

Стек

+ + ( ( ( ( * * / / / / / / + + + + - - - - - - - -

a + b * c - d / ( a + b )

Входная строка

Пример 2. Перевести в обратную польскую запись простое логическое выражение

а + Ь > - 5 ^ z - d = 1 + q ^ 2 (3)

Решение приведено в табл.2.

Переменные с индексами

Пусть требуется вычислить выражение

( а + Ь [ i + 1 , j ] ) * с + d

Для выполнения вычислений на машине необходимо сначала найти рес переменной с индексами. Адрес этой переменной дает функция упорядочения [2]. Коэффициенты функции упорядочения хранятся в группе ячеек памяти, на начало которой указывает адрес, назначенный идентификатору массива в результате обработки описаний и распределения памяти. Аргументами функции упорядочения являются значения индексов (индексных выражений) элемента массива.

Таблица 7.2

ПЕРЕВОД В ОБРАТНУЮ ПОЛЬСКУЮ ЗАПИСЬ ЛОГИЧЕСКОГО

ВЫРАЖЕНИЯ

В ы х о д н а я c т р о к а

a a a a a a a a a a a a a a a a b b b b b b b b b b b b b b + + + + + + + + + + + + + 5 5 5 5 5 5 5 5 5 5 5 из из из из из из из из из из из > > > > > > > > > > > z z z z z z z z z z d d d d d d d d - - - - - - - 1 1 1 1 1 1 q q q q 2 2 + = Ù

С т е к

+ + + + из из - - = = = = = = + + > > > Ù Ù Ù Ù Ù Ù Ù Ù Ù Ù

a + b > - 5 Ù z - d = 1 + q Ù 2

Входная строка

Введем операцию АДРЕС ЭЛЕМЕНТА МАССИВА (АЭМ), результат выполнения которой - адрес элемента массива, а операнды - идентификатор массива (точнее, назначенный ему адрес) и значения индексных выражений. Тогда рассматриваемое выражение [3] можно представить деревом, показанным на рис.7.1.

+ c

АЭМ

b + j

Рисунок7.1 - Дерево выражения, содержащего переменную с индексами

Обратная польская запись, полученная обходом дерева, имеет вид

а Ь i + j А Э М + с * d + (4)

Как обычно, в обратной польской записи левее операции АЭМ расположены операнды. Однако в отличие от логических и арифметических операций количество операндов операции АЭМ переменно. Оно зависит от размерности массива. Это вынуждает вместе со знаком операции АЭМ явным образом задать количество операндов.

Будем обозначать операцию АЗМ парой символов:

К ] ,

где К - целое число, равное количеству операндов, а ] - символ закрывающей индексной скобки, используемый в качестве знака операции АЭМ.

Очевидно, если n - число индексов, то

К = n + 1

Используя новое обозначение операции АЭМ, обратную польскую запись (4) можно переписать в виде

а Ь i 1 + j 3 ] + с * d + (5)

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

Однако в отличие от круглых скобок одновременно с записью в стек открывающей индексной скобки туда записывается также начальное (минимальное) значение счетчика операндов операции АЭМ, равное 2. Кроме того, после выталкивания из стека знаков закрывающей индексной скобкой и переписи их в выходную строку туда же переписывается значение счетчика операндов, а затем и сама закрывающая скобка.

Запятая, разделяющая индексные выражения, играет одновременно роль закрывающей скобки для предыдущего индексного выражения и роль открывающей скобки - для последующего. Поэтому запятой можно назначить приоритет 1 как закрывающей скобке, дополнив алгоритм условием, что запятая выталкивает из стека все знаки операции до ближайшей открывающей индексной скобки исключительно. Сама запятая, как и любая закрывающая скобка, в стек не записывается. Появление запятой равносильно появлению еще одного индекса, поэтому каждая запятая добавляет в счетчик операндов операции АЭМ единицу.

Пример. Перевести в обратную форму польскую инверсную запись выражение (3).

Решение приведено в табл.7.3.

табл.3 знак [сопровождается значением счетчика операндов операции АЭМ. Напомним, что минимальное значение этого счетчика равно 2. Нетрудно видеть, что окончательно выходная строка в табл.7.3 совпадает с записью в (5), полученной обходом дерева на рис.7.1.

Таблица 7.3

Перевод в обратную польскую запись выражения, Содержащего переменную синдексами

В ы х о д н а с я т р о к а	a a a a a a a a a a a a a a b b b b b b b b b b b b i i i i i i i i i i + + + + + + + + + j j j j j j j j 3 3 3 3 3 3 3 ] ] ] ] ] ] ] + + + + + + c c c c * * * d d +
С т е к	+ + [2 [2 [2 [2 [3 [3 + + + + + + + + + ( ( ( ( ( ( ( ( ( ( ( * * +
	( a + b [ i + 1 , j ] ) * c d
	Входная строка

Указатели функций

Помимо простых переменных и переменных с индексами выражение может содержать также указатели функций. Рассмотрим наиболее простой случай, когда параметры функции вызываются по значению. В частности, этот случай имеет место для стандартных функций ПАСКАЛЯ. Выражение на ПАСКАЛЕ:

y – f ( x , y , + 1 , z ) (6)

содержит указатель функции с идентификатором f. Внешне указатель функции отличается от переменной с индексами лишь тем, что после идентификатора функции записана строка, заключенная в круглые скобки, а не в квадратные, как у элемента массива. Поэтому дерево для указателя функции и алгоритмы перевода указателя функции в обратную польскую запись практически те же, что для переменных с индексом.

Введем операцию ФУНКЦИЯ, операнды которой - идентификатор функции и значения (или идентификаторы) ее аргументов, а результат - значение функции (точнее, адрес значения функции). Тогда выражение (6) можно представить в виде дерева, изображенного на рис.2. Обход этого дерева дает обратную польскую запись выражения (6).

Очевидно, как и в случае переменных с индексами, в обратной польской записи целесообразно вместе со знаком операции ФУНКЦИЯ указывать количество операндов. Это облегчает последующую трансляцию указателя функции в машинные команды и позволяет контролировать правильность обращения к функции (соответствие числа фактических и формальных параметров).

Будем обозначать операцию ФУНКЦИЯ парой символов

КФ,

где К - количество операндов, а Ф - знак операции ФУНКЦИЯ. Тогда обратная польская запись выражения (6) примет следующий вид

y f x y 1 + z 4 Ф -.

Алгоритм перевода в обратную польскую запись функции, имеющий не менее одного параметра, тот же, что для переменной с индексом. Различие состоит лишь в том, что в момент прихода закрывающей круглой скобки в выходную строку записывается символ Ф. Чтобы отличить открывающую круглую скобку в начале списка фактических параметров от открывающей круглой скобки в начале выражения, можно использовать переменную состояния F (признак функции). Эта переменная обычно имеет значение ноль. В момент появления идентификатора функции она принимает значение 1, а после занесения в стек круглой скобки и начального значения счетчика операндов, равно 2 (см 1.2), вновь принимает значение 0. Закрывающая скобка, встретив в стеке открывающую круглую, записанную вместе со значением счетчика операндов, занесет это значение в выходную строку, запишет туда знак Ф и уничтожит в стеке круглую скобку и значение счетчика операндов.

Пример. Перевести в обратную польскую запись выражение (6).

Решение приведено в табл.7.4.

Таблица 7.4

Перевод в обратную польскую запись выражения, Содержащего указатель функции

В ы х о д с н т а р я о к а	y y y y y y y y y y y y y f f f f f f f f f f f x x x x x x x x x y y y y y y y 1 1 1 1 1 + + + + z z z 4 4 ф ф -
F	0 0 1 0 0 0 0 0 0 0 0 0 0
Стек	+ + (2 (2 (3 (3 (3 (3 (4 (4 - - - - - - - - - - -
	y - f ( x , y + 1 , z ) -
	Входная строка

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

f x z

y 1

Рис.7.2. Дерево выражения, содержащего указатель функции

Особый случай, когда указатель функций употребляется без параметров, при переводе в обратную польскую запись можно не выделять, поскольку в этом случае указатель функций, как и все идентификаторы, будет перенесен непосредственно в выходную строку. Одновременно переменная состояния F примет значение 1. Если следующий символ не круглая скобка, то признаку присваивается значение 0, а в выходную строку заносится запись 1Ф в знак того, что операция ФУНКЦИЯ имеет всего один операнд - идентификатор функции

Дата добавления: 2019-02-12; просмотров: 391; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 3 4 5 6 7 8 91011 12 Следующая ⇒

Мы поможем в написании ваших работ!