Информационные технологии

Меню

Реклама

Обратная польская запись. Но алгоритм его построения

1. Обратная польская запись.

Привычной формой выражений является Инфиксная, когда знак бинарной операции записывается Между обозначениями операндов Этой операции, например, A+B. Рассмотрим запись знаков операций После обозначений операндов, то есть Постфиксная запись, например, Ab+. Такая запись имеет также назову Обратного польского, поскольку его предложил польский логик Ян Лукасевич. Дальше словосочетание обратную польскую запись будем помечать ЗПЗ.

Опишем соответствие между привычными инфиксными выражениями и их ЗПЗ. Пусть E, E1, E2 помечают выражения в инфиксной форме, op1, op2 - знаки унарной и бинарной операций, opf - имя функции. Выражению E в зависимости от его вида отвечает ЗПЗ LE согласно правилам:

E

LE

Стала или имя переменной

E

'' E1 ''

LE1

op1E1

LE1 op1

E1op2E2

LE1 LE2 op2

opf''E1''

LE1 opf

Как видим, эти правила рекурсивные, и ЗПЗ более сложных выражений описываются с помощью ЗПЗ их более простых подвыражений.

В следующих примерах покажем применение приведенных правил с учетом старшинства и свойства левостороннего связывания операций :

L B C = B C;

L --A = L -A - = A--;

L A + B C = LA LBC + = A B C +;

L A + B - C = L A + B L C - = A B + C -;

L 1 - sin A+B = L1 L sin A+B - = 1 L A+B sin - =1 A B + sin -.

Выражения со знаками унарных операций дальше не рассматриваются.

2. Алгоритм построения ЗПЗ.

Выражение является последовательностью символов - цифр, букв и других знаков. Но они образуют лексические единицы, или лексемы, четырех разновидностей: стали, имена обозначения функций, знаки операций и скобки. Будем смотреть на выражение именно как на последовательность лексем, какие мы получаем последовательным чтением выражения слева направо.

Рассмотрим подробнее построение исходной последовательности лексем LE за лексемами выражения E.

Из правил построения LE выплывает, что порядок элементарных обозначений операндов постоянных или имен переменных в выражениях E и LE одинаковый, потому стали и имена переменных можно сразу записывать в исходную последовательность.

Порядок знаков операций изменяется: во входном выражении вида E1 op2 E2 знак op2 предшествует знакам операций выражения E2, а в исходном выражении LE1 LE2 op2 - наоборот. Поэтому знак op2 надо запомнить, выдать LE2, а после него - op2. Знаки операций в выражениях E1 и E2 нужно так же хранить и выдавать после ЗПЗ выражений, которые помечают операнды этих операций. Такая измена порядка знаков достигается за использование Магазина, или Стека; знаки операций поступают у него и изымаются в исходное выражение по принципу Последним вошел - первым вышел LAst IN - FIrst OUt, или LIFO.

На порядок знаков в исходном выражении влияет их старшинство, или приоритет :

L A + B C = A B C +; L A + B - C = A B + C -.

Операция '' старшая за '+', потому в первом выражении операция '+' применяется к значениям A но BC. Во втором выражении старшинство '+' и '-' одинаковое, операции имеют свойство левостороннего связывания, потому '+' применяется к A и B, а '-' - к A+B и C.

Следовательно, когда во входной последовательности читается знак операции op2, из верхушки магазина надо выдать в исходное выражение все знаки, приоритеты которых не ниже от приоритета op2 все они являются знаками из выражения E1, и только после этого запомнить op2 в магазине. Если приоритет знака из верхушки магазина ниже, чем в op2, то op2 записывается в магазин, поскольку должен появиться в исходном выражении раньше.

Процесс построения ЗПЗ выражения можно подать последовательностью троек вида

Исходная последовательность лексем;

Магазин;

Непрочитанная часть выражения.

Верхушку магазина будем указывать справа.

Пример 1. Начало превращения выражения A+BC изображается последовательностью троек

;; A + B C - Начальное состояние: исходная последовательность и магазин пусты;

A;; + B C - Имя перенесено в исходную последовательность;

A; +; B C - Знак перенесен в магазин;

A B; +; C - Имя перенесено в исходную последовательность.

После этого знак '' вмещается в магазин над знаком '+':

A B; +; C.

Приоритет операции '' более высок от '+', потому B является операндом '', а не '+'.

При превращении выражения A+B-C результатом чтения его начала A+B будет

A B; +; - C,

После чего знак '-' вытолкнет из магазина '+', то есть следующей будет тройка

A B +; -; C.

Приоритеты '+' и '-' уровни, потому B связывается с операцией '+' слева.

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

Имя функции записывается в магазин и выдается непосредственно за ЗПЗ выражения ее аргумента. Имя функции выталкивается из верхушки с появлением во входном выражении знака операции или закрывающей скобки.

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

Следовательно, вся описанная обработка лексем подается таким алгоритмом:

While На входе есть лексема C Do

Case C Of

Стала или имя переменной: скопировать ее в исходную последовательность;

Знак операции: к появлению на верхушке магазина открывающей скобки вытолкнуть оттуда и скопировать в исходную последовательность все знаки, чей приоритет не низший от приоритета С; втолкнуть С в магазин;

Открывающая скобка: Втолкнуть С в магазин;

Закрывающая скобка: к появлению на верхушке магазина открывающей скобки вытолкнуть оттуда и скопировать в исходную последовательность все знаки операций; вытолкнуть открывающую скобку;

End;