Введем понятие различных форм записи выражений. А+В – инфиксная: знак операции находится между операндами; +АВ – префиксная (польская): знак операции расположен перед операндами; АВ+ – постфиксная (обратная польская): знак операция находится после операндов.

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

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

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

Примеры различных форм записи выражений.

Инфиксное представление Постфиксное представление

А+В-С АВ+С-

(А+В)*(С- D ) AB + CD -*

A^B*C-D+E/F/(G+H) AB^C*D-EF/GH+/+

A-B/(C*D^E) ABCDE^*/-

Инфиксное представление Префиксное представление

А+В-С - +АВС

(А+В)*(С- D ) *+ AB - CD

(( A + B )* C -( D - E )^( F + G ) ^ -*+ ABC - DE + FG

A - B /( C * D ^ E ) - A / B * C ^ DE

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

Правило вычисления выражения в обратной польской записи.

Построение выражений в обратной польской записи

Основное преимущество обратной польской записи перед обычной записью выражений со скобками: выражение можно вычислить в процессе однократного просмотра слева направо

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

 Если очередной элемент – операнд, то рассматривается следующий элемент.

Если текущий элемент – знак операции, то выполняется эта операция над операндами, записанными левее знака операции. Результат операции записывается вместо первого (самого левого) операнда, участвовавшего в операции. Остальные элементы (операнды и знак операции), участвовавшие в операции, вычеркиваются из записи. Просмотр продолжается. В результате последовательного выполнения этого правила будут выполнены все операции в выражении, и запись сократится до одного элемента – результата вычисления выражения.

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