Обратная польская запись операций

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

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

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

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

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

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

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

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

1. Если встречается операнд, то он помещается в стек (попадает на верхушку стека).

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

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

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

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

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

Оптимизация кода