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

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

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

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

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

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

А+В-С АВ+С-

(А+В)*(С-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

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