Префиксная и постфиксная польская (бесскобочная) форма записи.

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

Префиксная польская запись (ПрПЗ) определяется следующим образом.

Если инфиксное выражение Е представляет собой один операнд а, то ПрПЗ выражения Е – это просто а.

Если инфиксное выражение Е ₁* Е ₂, где * – знак операции, а Е ₁ и Е ₂ – инфиксные выражения для операндов, то ПрПЗ этого выражения – это * Е ₁' E ₂',где E ₁', E ₂' – ПрПЗ выражений Е ₁ и Е ₂.

Если (Е) есть инфиксное выражение, то ПрПЗ этого выражения есть ПрПЗ Е.

Перечисленные правила определяют порядок построения ПрПЗ заданного инфиксного выражения. Например, для выражений (a + b) * (c - d) построение ПрПЗ можно выполнить так. Обозначим операнды первой выполняемой операции:

E ₁ = (a + b) и E ₂ = (c - d).

Согласно определению префиксная запись выражения Е ₁* Е ₂ – это * E ₁' E ₂', где Е ₁', Е ₂' – префиксные записи выражений Е ₁и Е ₂. Выполняя построение постфиксных записей для этих выражений,

E ₁' = + ab, E ₂' = - cd,

окончательно получаем результат в виде:

*+ ab - cd

Постфиксная запись отличается тем, что знак операции ставится непосредственно за операндами. Так, например, инфиксной записи (A+B) соответствует постфиксная форма AB+.

Постфиксная польская запись (ПоПЗ) определяется следующим образом.

Если инфиксное выражение Е представляет собой один операнд а, то ПоПЗ выражения Е – это а.

Если инфиксное выражение Е ₁* Е ₂, где * – знак операции, E ₁, E ₂ – инфиксные выражения для операндов, то ПоПЗ этого выражения это – Е ₁' E ₂'*, где Е₁', E₂ ' – постфиксные выражения Е ₁, Е ₂.

Если (Е) есть инфиксное выражение, то постфиксная запись этого выражения есть постфиксная запись Е.

Аналогично предыдущему примеру построим ПоПЗ выражения

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

Обозначая операнды внешней операции

E ₁ = (a + b) и E ₂ = (c - d)

найдем постфиксные записи операндов, которые имеют вид:

E ₁' = ab + и E ₂' = cd -

Подставляя полученные постфиксные записи в выражение

E ₁' E ₂'*

окончательно получаем:

ab + cd -*

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

Для записи любого выражения не нужны скобки. Так как оператор непосредственно следует за операндами, участвующими в операции, неопределенность в указании операндов отсутствует. Например, выражение (A + B)+ C имеет постфиксную форму AB + C +, а выражение A +(B + C) представляется в форме ABC ++.

К моменту считывания очередного оператора соответствующие операнды уже были прочитаны. Поэтому оператор может быть выполнен без считывания каких-либо дополнительных данных.

Сказанное выше относится к бинарным операциям, однако это нетрудно распространить на унарные операции. Так, унарный оператор отрицания (эту операцию будем обозначать знаком ~) просто ставят непосредственно за аргументом. Например, инфиксная запись ~ A представляется в форме A ~, а выражение ~(A + B) преобразуется в AB +~. (Заметим, что знак "-" может стоять в инфиксной записи, указывая как бинарную, так и унарную операцию, и его правильный смысл становится очевидным из контекста. В постфиксной записи это сделать труднее.

Благодаря описанным выше свойствам выражение в постфиксной форме может быть вычислено с помощью простого алгоритма:

while(lex!= NULL) // пока в выражении еще есть лексемы

{

lex = getNextLex(); // считать следующую лексему

if(isOperand(lex)) // лексема есть операнд

push(lex); // записать лексему в стек

if(isOperator(lex)) // лексема есть оператор

push(performOperation(lex, pop(), pop()));

/* выполнить указанную лексемой операцию над последними элементами, записанными в стек, и заменить эти элементы результатом операции;

*/

}

В результате вычислений значение выражения оказывается единственным элементом стека.

Такой алгоритм, выполняющий операции над стеком, лежит практически в основе любого компилятора. Обычно блок синтаксического анализа преобразует программу в постфиксную форму, после чего генератор кода строит объектную программу, просматривая выражения вышеописанным методом.

Очевидно, что вычисление постфиксной записи выражения не представляет трудности, преобразование же инфиксной записи в постфиксную заметно сложнее. Предположим, что продукция языка имеет вид

A ® B и C

где A, B и C являются нетерминалами, а "и" – терминал. Будем считать, что знаки операций являются терминалами. Тогда эта продукция означает, что нетерминал A является инфиксной записью, в которой участвуют операнды B и C вместе с оператором "и". Следовательно, постфиксная форма выражения образуется из операндов B, C, за которыми следует оператор "и". Таким образом, для данной продукции постфиксная запись имеет вид

Постфиксная запись для B

Постфиксная запись для C

и

Если терминальные символы выводятся в выходной файл в таком порядке, то все фразы языка будут представлены в постфиксной форме.

Преобразование выражения из инфиксной записи в постфиксную.

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

Рассмотрим два выражения в инфиксной форме: А + В * С и (А + В)* С и соответствующие им постфиксные формы АВС *+ и АВ + С *. В каждом случае порядок следования операндов в этих формах совпадает с порядком следования операндов в исходных выражениях. При просмотре первого выражения (А + В * С) первый операнд А может быть сразу же помещен в постфиксное выражение. Очевидно, что символ "+" не может быть помещен в это выражение до тех пор, пока туда не будет помещен второй, еще не просмотренный операнд. Следовательно, он (т.е. символ "+") должен быть сохранен, а впоследствии извлечен и помещен в соответствующую позицию. После просмотра операнда В этот символ записывается вслед за операндом А. К этому моменту просмотренными уже оказываются два операнда. Однако извлекать и помещать символ "+" в постфиксную запись еще рано, т.к. за ним следует символ "*", имеющий более высокий приоритет. Во втором выражении наличие скобок обуславливает выполнение операции "+" в первую очередь.

Так как при преобразовании инфиксной формы в постфиксную правила приоритета играют существенную роль, для их учета введем функцию precedence(oper1, oper2), где oper1 и oper2 – символы, обозначающие операции. Эта функция возвращает значение TRUE, если oper1 имеет более высокий приоритет, чем oper2, или они имеют равный приоритет, но oper1 располагается слева от oper2 в бесскобочном выражении, представленном в инфиксной форме. В противном случае функция precedence(oper1, oper2) возвращает значение FALSE.Например, значения функций precedence("*","+") и precedence("+" "+") – "истина", аprecedence ("+","*") – "ложь". Фрагмент текста в этом абзаце подчеркнут, так как неправильное формирование постфиксной записи (как вручную, так разработанными студентами программными генераторами) для операций с равным приоритетом является одной из типичных ошибок.

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

1. (Установить в постфиксную строку " ");

2. (Очистить стек с именем opstk);

3. while (на входе еще имеются символы) {

4. read(symb);

5. if(isOperand(symb) == TRUE) {//символ есть операнд

6. (добавить символ к постфиксной строке);

7. } else { //символ есть операция

8. while(empty(stack) == FALSE) &&

(precedence(stacktop(opstk), symb) == TRUE)) {

9. smbtp = pop(opstk);

/* smbtp имеет приоритет больший, чем symb, поэтому она может быть добавлена к постфиксной строке. */

10. (добавить smbtp к постфиксной строке);

11. } // end while

/* в этой точке либо opstk пуст, либо symb имеет приоритет над stacktop(opstk). Мы не можем поместить symb в постфиксную строку до тех пор, пока не считаем следующую операцию, которая может иметь более высокий приоритет. Следовательно, мы должны сохранить symb. */

12. push(opstk, symb);

13. } // end if

14. } // end while

/* к этому моменту строка оказывается просмотренной целиком. Мы должны поместить оставшиеся в стеке операции в постфиксную строку. */

15. while(empty(opstk) == FALSE) {

16. smbtp=pop(opstk);

17. (добавить smbtp к постфиксной строке);

18. } // end while

Для обеспечения возможности работы со скобками после считывания открывающейся скобки она записывается в стек. Это может быть выполнено путем установки правила precedence(op, "(") == FALSE для любого символа операции, отличного от символа правой (закрывающей) скобки. Также определим precedence("(", op) == FALSE для того, чтобы символ операции, появляющийся после левой скобки, записывался в стек.

После считывания закрывающей скобки все операции вплоть до первой открывающей скобки должны быть прочитаны из стека и помещены в постфиксную строку. Это может быть сделано путем установки precedence(op, ")") == TRUE для всех операций op, отличных от левой скобки. После считывания этих операций из стека и закрытия открывающей скобки необходимо выполнить следующую операцию. Открывающая скобка должна быть удалена из стека и отброшена вместе с закрывающей скобкой. Обе скобки не помещаются затем ни в постфиксную строку, ни в стек. Установим функцию precedence("(", ")") равной FALSE. Это гарантирует нам то, что при достижении открывающей скобки цикл, начинающийся в строке 8, будет пропущен, а открывающая скобка не будет помещена в постфиксную строку.

Выполнение продолжится со строки 12. Однако, поскольку открывающая скобка не должна помещаться в стек, строка 12 заменяется оператором

if((empty(opstk) == TRUE) || (symb <> ")"))

push(opstk, symb);

else smbtp=pop(opstk);

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

precedence("(",op) == FALSE для любой операции op

precedence(op,"(") == FALSE для любой операции op, отличной от ")"

precedence(op,")") == TRUE для любой операции op, отличной от "("

precedence(")",op) = "неопределенно" для любой операции op, (попытка сравнения двух указанных операций означает ошибку)

Проиллюстрируем этот алгоритм несколькими примерами:

Пример1:

А + В * С

Приводится содержимое symb, постфиксной строки и opstk после просмотра каждого символа. Вершина opstk находится справа.

Строка	symb	Постфиксная строка	opstk
	A	A
	+	A	+
	B	AB	+
	*	AB	+*
	C	ABC	+*
		ABC*	+
		ABC*+

Строки 1, 3 и 5 соответствуют просмотру операнда таким образом, что символ (symb) немедленно помещается в постфиксную строку. В строке 2 была обнаружена операция, а стек оказался пустым, поэтому операция помещается в стек. В строке 4 приоритет нового символа (*) больше, чем приоритет символа, расположенного в вершине стека (+), поэтому новый символ помещается в стек. На 6-м и 7-м шагах входная строка пуста, поэтому из стека считываются элементы, которые затем помещаются в постфиксную строку.

Пример2:

(А + В)* С

Строка	symb	Постфиксная строка	Opstk
	(		(
	A	A	(
	+	A	(+
	B	AB	(+
	)	AB+
	*	AB+	*
		AB+C*

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

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