ПЕРЕВОД В ОБРАТНУЮ ПОЛЬСКУЮ ЗАПИСЬ АРИФМЕТИЧЕСКОГО
ВЫРАЖЕНИЯ
В ы х о д с н т а р я о к а | 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.
+
d
+ c
+
АЭМ
a
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.
-
y
f x z
+
y 1
Рис.7.2. Дерево выражения, содержащего указатель функции
Особый случай, когда указатель функций употребляется без параметров, при переводе в обратную польскую запись можно не выделять, поскольку в этом случае указатель функций, как и все идентификаторы, будет перенесен непосредственно в выходную строку. Одновременно переменная состояния F примет значение 1. Если следующий символ не круглая скобка, то признаку присваивается значение 0, а в выходную строку заносится запись 1Ф в знак того, что операция ФУНКЦИЯ имеет всего один операнд - идентификатор функции
Дата добавления: 2019-02-12; просмотров: 391; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!