Обратная польская запись – это постфиксная запись операций, которая предусматривает, что знаки операций записываются после операндов. Она была предложена польским математиком Я. Лукашевичем, откуда и происходит ее название.
В этой записи знаки операций записываются непосредственно за операндами. По сравнению с обычной (инфиксной) записью операций в польской записи операнды следуют в том же порядке, а знаки операций – строго в порядке их выполнения. Тот факт, что в этой форме записи все операции выполняются в том порядке, в котором они записаны, делает ее чрезвычайно удобной для вычисления выражений на компьютере. Польская запись не требует учитывать приоритет операций, в ней не употребляются скобки, и в этом ее основное преимущество.
Она чрезвычайно эффективна в тех случаях, когда для вычислений используется стек. Ниже будет рассмотрен алгоритм вычисления выражений в форме обратной польской записи с использованием стека.
Главный недостаток обратной польской записи также проистекает из метода вычисления выражений в ней: поскольку используется стек, то для работы с ним всегда доступна только верхушка стека, а это делает крайне затруднительной оптимизацию выражений в форме обратной польской записи. Практически выражения в форме обратной польской записи почти не поддаются оптимизации.
Но там, где оптимизация вычисления выражений не требуется или не имеет большого значения, обратная польская запись оказывается очень удобным методом внутреннего представления программы.
Обратная польская запись была предложена первоначально для записи арифметических выражений. Однако этим ее применение не ограничивается. В компиляторе можно порождать код в форме обратной польской записи для вычисления практически любых выражений. Для этого достаточно ввести знаки, предусматривающие вычисление соответствующих операций. В том числе, возможно ввести операции условного и безусловного перехода, предполагающие изменение последовательности хода вычислений и перемещение вперед или назад на некоторое количество шагов в зависимости от результата на верхушке стека. Такой подход позволяет очень широко применять форму обратной польской записи.
Преимущества и недостатки обратной польской записи определяют и сферу ее применения. Так, она очень широко используется для вычисления выражений в интерпретаторах и командных процессорах, где оптимизация вычислений либо отсутствует вовсе, либо не имеет существенного значения.
Вычисление выражений с помощью обратной польской записи. Вычисление выражений в обратной польской записи идет элементарно просто с помощью стека. Для этого выражение просматривается в порядке слева направо и встречающиеся в нем элементы обрабатываются по следующим правилам:
1. Если встречается операнд, то он помещается в стек (попадает на верхушку стека).
2. Если встречается знак унарной операции (операции, требующей одного операнда), то операнд выбирается с верхушки стека, операция выполняется и результат помещается в стек (попадает на верхушку стека).
3. Если встречается знак бинарной операции (операции, требующей двух операндов), то два операнда выбираются с верхушки стека, операция выполняется и результат помещается в стек (попадает на верхушку стека).
Вычисление выражения заканчивается, когда достигается конец записи выражения. Результат вычисления при этом всегда находится на верхушке стека.
Очевидно, что данный алгоритм можно легко расширить и для более сложных операций, требующих три и более операндов.
На рис. 13 рассмотрены примеры вычисления выражений в обратной польской записи.
Оптимизация кода
