admin / 20.07.2018

Постфиксная запись – префиксная форма

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

Постфиксная запись представляет собой такую запись арифметического выражения, в которой сначала записываются операнды, а затем – знак операции. Например, для выражения a + b * c постфиксная запись будет a b c * +. Здесь операндами операции * будут b и c (два ближайших операнда), а операндами операции + будут а и составной операнд b c *. Эта запись удобна тем, что она не требует скобок. Например, для выражения (a + b) * c постфиксная запись будет a b + c *. В этой записи не требуется ставить скобки для того, чтобы изменить порядок вычисления, зависящий от приоритета операций, как в исходном выражении.

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

Алгоритм перевода выражения в постфиксную запись следующий.

  1. Константы и переменные кладутся в формируемую запись в порядке их появления в исходном массиве.
  2. При появлении операции в исходном массиве:
    1. если в стеке нет операций или верхним элементом стека является открывающая скобка, операции кладётся в стек;
    2. если новая операции имеет больший* приоритет, чем верхняя операции в стеке, то новая операции кладётся в стек;
    3. если новая операция имеет меньший или равный приоритет, чем верхняя операции в стеке, то операции, находящиеся в стеке, до ближайшей открывающей скобки или до операции с приоритетом меньшим, чем у новой операции, перекладываются в формируемую запись, а новая операции кладётся в стек.
  3. Открывающая скобка кладётся в стек.
  4. Закрывающая скобка выталкивает из стека в формируемую запись все операции до ближайшей открывающей скобки, открывающая скобка удаляется из стека.
  5. После того, как мы добрались до конца исходного выражения, операции, оставшиеся в стеке, перекладываются в формируемое выражение.

Примеры

  1. a + b * c
Обрабатываемая лексема Результат Стек Пункт алгоритма
a a   1
+ a + 2a
b a b + 1
* a b + * 2b
c a b c + * 1
  a b c * +   5

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

  1. a + b — c * d
Обрабатываемая лексема Результат Стек Пункт алгоритма
a a   1
+ a + 2a
b a b + 1
a b + — 2b
c a b c + — 1
* a b c + — * 2b
d a b c d + — * 1
  a b c d * — +   5
  1. a + b * c — d
Обрабатываемая лексема Результат Стек Пункт алгоритма
a a   1
+ a + 2a
b a b + 1
* a b + * 2b
c a b c + * 1
a b c * + 2c
d a b c * + d 1
  a b c * + d —   5
  1. (a + b) * c
Обрабатываемая лексема Результат Стек Пункт алгоритма
(   ( 3
a a ( 1
+ a ( + 2a
b a b ( + 1
) a b +   4
* a b + * 2a
c a b + c * 1
  a b + c *   5
  1. (a + b * c) / 2
Обрабатываемая лексема Результат Стек Пункт алгоритма
(   ( 3
a a ( 1
+ a ( + 2a
b a b ( + 1
* a b ( + * 2b
c a b c ( + * 1
) a b c * +   4
/ a b c * + / 2a
2 a b c * + 2 / 1
  a b c * + 2 /   5
  1. (a * (b + c) + d) / 2
Обрабатываемая лексема Результат Стек Пункт алгоритма
(   ( 3
a a ( 1
* a ( * 2a
( a ( * ( 3
b a b ( * ( 1
+ a b ( * ( + 2a
c a b c ( * ( + 1
) a b c + ( * 4
+ a b c + * ( + 2c
d a b c + * d ( + 1
) a b c + * d +   4
/ a b c + * d + / 2a
2 a b c + * d + 2 / 1
  a b c + * d + 2 /   5
  1. a && b == c
Обрабатываемая лексема Результат Стек Пункт алгоритма
a a   1
&& a && 2a
b a b && 1
== a b && == 2b
c a b c && == 1
  a b c == &&   5
  1. a == b && c || a != d
Обрабатываемая лексема Результат Стек Пункт алгоритма
a a   1
== a == 2a
b a b == 1
&& a b == && 2c
c a b == c && 1
|| a b == c && || 2c
a a b == c && a || 1
!= a b == c && a || != 2b
d a b == c && a d || != 1
  a b == c && a d != ||   5
  1. (a || b) && !c
Обрабатываемая лексема Результат Стек Пункт алгоритма
(   ( 3
a a ( 1
|| a ( || 2a
b a b ( || 1
) a b ||   4
&& a b || && 2a
! a b || && ! 2b
c a b || c && ! 1
  a b || c !

&&

  5

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

  1. Имя функции кладётся в стек и выталкивается оттуда только закрывающей скобкой.

  1. x + (sin x) * 2
Обрабатываемая лексема Результат Стек Пункт алгоритма
x x   1
+ x + 2a
( x + ( 3
sin x + ( sin 6
x x x + ( sin 1
) x x sin + 4
* x x sin + * 2b
2 x x sin 2 + * 1
  x x sin 2 * +   5
  1. a + (sin (b + c))
Обрабатываемая лексема Результат Стек Пункт алгоритма
a a   1
+ a + 2a
( a + ( 3
sin a + ( sin 6
( a + ( sin ( 3
b a b + ( sin ( 1
+ a b + ( sin ( + 2a
c a b c + ( sin ( + 1
) a b c + + ( sin 4
) a b c + sin + 4
  a b c + sin +   5

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

Вычислим значение выражения a b c + * d + 2 / при а = 1, b = 2, c = 3, d = 4

Обрабатываемая лексема Стек
a 1
b 1 2
c 1 2 3
+ 1 5
* 5
d 5 4
+ 9
2 9 2
/ 4.5

Вычислим значение выражения x x sin 2 * + при x = 3.14

Обрабатываемая лексема Стек
x 3.14
x 3.14 3.14
sin 3.14 0
2 3.14 0 2
* 3.14 0
+ 3.14

Вычислим значение выражения a b || c ! && при a = 0, b = 2, c = 0

Обрабатываемая лексема Стек
a 0
b 0 2
|| 1
c 1 0
! 1 1
&& 1

Файл в формате Word

Содержание


* Операции * и / имеют равный приоритет, который больше приоритета операций + и -. Операции + и — также имеют равный приоритет. Операции сравнения имеют больший приоритет, чем логические операции. Операция «НЕ» имеет больший приоритет, чем операция «И» , а «И» имеет больший приоритет, чем операция «ИЛИ».

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

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

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

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

Если инфиксное выражение Е1*Е2, где * – знак операции, а Е1 и Е2 – инфиксные выражения для операндов, то ПрПЗ этого выражения – это *Е1E2‘,где E1‘, E2‘ – ПрПЗ выражений Е1 и Е2.

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

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

E1 = (a + b) и E2 = (cd).

Согласно определению префиксная запись выражения Е1*Е2 – это *E1E2‘, где Е1‘,Е2‘ – префиксные записи выражений Е1и Е2. Выполняя построение постфиксных записей для этих выражений,

E1‘ = +ab, E2‘ = —cd,

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

*+abcd

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

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

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

Если инфиксное выражение Е1*Е2 , где * – знак операции, E1, E2 – инфиксные выражения для операндов, то ПоПЗ этого выражения это – Е1E2‘*, где Е1‘, E2 ‘ – постфиксные выражения Е1 ,Е2 .

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

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

(a + b) * (cd).

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

E1 = (a + b) и E2 = (cd)

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

E1‘ = ab+ и E2‘ = cd

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

E1E2‘*

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

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.

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

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

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



Инфиксная нотация — это форма записи математических и логических формул, в которой операторы записаны в инфиксном стиле между операндами на которые они воздействуют (например 2 + 2). Задача разбора выражений записанных в такой форме для компьютера сложнее по сравнению с префиксной (то есть + 2 2) или постфиксной (2 2 +). Однако эта запись используется в большинстве языков программирования как более естественная для человека.

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

«Antananarivo» — перевод на русский

Инфиксная запись может отличаться от функциональной, где имя функции описывает какую-то операцию, а её аргументы являются операндами. Примером функциональной записи может быть S(1,3) в которой функция S означает операцию сложения: S(1,3) = 1+3 = 4.

См. также

Ссылки

FILED UNDER : IT

Submit a Comment

Must be required * marked fields.

:*
:*