Обратная польская запись некогда составляла основу мира компьютерного программиста. Сегодня она уже не так хорошо известна. Поэтому шуточная иллюстрация, изображающая «обратную» польскую колбасу за пределами булочки, все еще может оказаться непонятой некоторыми хорошо осведомленными программистами. Не очень хорошо объяснять шутку, но в данном случае это будет в полной мере оправдано.
Инфиксная запись
Все программисты и большинство школьников знакомы с использованием операторов. Например, в выражении х + у для суммирования значений переменных х и у использован знак сложения. Менее известно то, что это заимствованное из математики обозначение, называемое инфиксной нотацией, на самом деле представляет большую проблему для машин. Такой оператор принимает в качестве входных два значения, записанные слева и справа от него. В программировании использовать нотацию со знаками операций необязательно. Например, х + у можно записать в виде функции сложить (х, у), в которую компилятор в конце концов и преобразует инфиксную нотацию. Однако все знают математику слишком хорошо, чтобы не использовать арифметические выражения, которые образуют своего рода внутренний мини-язык почти в каждом языке программирования.
Трансляторы формул
Первый действительно успешный язык программирования Fortran стал таким в основном потому, что арифметические выражения (т. е. формулы) в нем преобразовывались (транслировались) в код, откуда и произошло его название – FORmula TRANslation. До этого их приходилось записывать, например, в виде функций сложить (а, умножить (b, c)). В Коболе проблема реализации автоматического преобразования формул считалась очень трудной, поскольку программистам приходилось писать такие вещи, как Add A To B Mutliply By C.
Что не так с инфиксом?
Проблема заключается в том, что операторы обладают такими свойствами, как приоритет и ассоциативность. Из-за этого определение функции инфикса становится нетривиальной задачей. Например, приоритет умножения выше, чем сложения или вычитания, и это означает, что выражение 2 + 3 * 4 не равно сумме 2 и 3, умноженной на 4, как это бы было при выполнении операторов слева направо. На самом деле следует умножить 3 на 4 и прибавить 2. Этот пример иллюстрирует, что вычисление инфиксного выражения часто требует изменения порядка операторов и их операндов. Кроме того, приходится использовать скобки, чтобы нотация выглядела более ясно. Например, (2 + 3) * (4 + 5) нельзя записать без скобок, потому что 2 + 3 * 4 + 5 означает, что необходимо умножить 3 на 4 и добавить 2 и 5.
Порядок, в котором необходимо вычислять операторы, требует долгого запоминания. Из-за этого школьники, начинающие изучать арифметику, часто получают неправильные результаты, даже если фактически операции выполняются правильно. Необходимо учить порядок действия операторов наизусть. Сперва должны выполняться действия в скобках, затем умножение и деление и, наконец, сложение и вычитание. Но есть и другие способы записи математических выражений, поскольку инфиксная нотация является всего лишь одним из возможных «малых языков», которые можно добавить к большему.
Префиксная и постфиксная нотация
Двумя наиболее известными альтернативными вариантами является запись оператора до или после его операндов. Они известны как префиксная и постфиксная нотации. Логик Ян Лукасевич придумал первую из них в 1920-е годы. Он жил в Польше, поэтому запись называют польской. Постфиксный вариант, соответственно, получил название обратной польской нотации (ОПН). Единственная разница между этими двумя методами состоит в направлении, в котором следует читать запись (слева направо или справа налево), поэтому достаточно подробно рассмотреть только один из них. В ОПН оператор записывается после его операндов. Так, выражение АВ + представляет собой пример обратной польской записи для A + B.
Неограниченное число операндов
Непосредственным преимуществом нотации является то, что она обобщается n-адическим оператором, а инфиксная нотация на самом деле работает только с двумя операндами, т. е. по своей природе подходит только для бинарных операций. Так, например, ABC @ является обратным польским выражением с использованием триадического знака, который находит максимальное значение из A, B и C. В этом случае оператор действует на 3 операнда слева от себя и соответствует вызову функции @ (A, В, С). Если попытаться записать символ @ в качестве инфиксного, например A @ BC или что-то подобное, то становится понятно, что это попросту не работает.
Приоритет задается порядком
Обратная польская запись имеет еще одно преимущество в том, что приоритет операторов может быть представлен порядком их появления. При этом никогда не понадобятся скобки, хотя они могут быть включены в качестве знаков операций, чтобы облегчить конвертацию с инфиксной нотацией. Например, АВ + С * – однозначный эквивалент (А + В) * С, так как умножение не может быть вычислено, пока не будет выполнено сложение, которое дает второй операнд для операции умножения. То есть если вычисляется AB + C * по одному оператору за раз, то получится A B + C * -> (A B +) * C -> (A+B)*C.
Алгоритм вычисления
В ОПН оператор выглядит так же, как функция, которая принимает в качестве аргументов два значения, записанные слева от нее. Кроме того, это естественная нотация для использования в языках программирования, поскольку ход ее вычислений соответствует стековым операциям и необходимость в синтаксическом анализе отпадает. Например, в ОПН выражение 5 + 6 * 7 будет выглядеть как 5, 6, 7 *, +, и оно может быть вычислено просто путем сканирования слева направо и записи значений в стек. Каждый раз, когда встречается знак операции, выбираются 2 верхних элемента из машинной памяти, применяется оператор и результат возвращается в память. При достижении конца выражения результат вычислений окажется в вершине стека.
Например:
- S = () 5, 6, 7, *, + поместить 5 в стек.
- S = (5) 6, 7, *, + поместить 6 в стек.
- S = (5, 6) 7, *, + поместить 7 в стек.
- S = (5, 6, 7) *, + выбрать 2 значения из стека, применить * и поместить результат в стек.
- S = (5, 6 * 7) = (5, 42) + выбрать 2 значения из стека, применить + и поместить результат в стек.
- S = (5 + 42) = (47) вычисление завершено, результат находится в вершине стека.
Этот алгоритм обратной польской записи можно проверять многократно, но каждый раз он будет работать, независимо от того, насколько сложным является арифметическое выражение.
ОПН и стеки тесно связаны между собой. Приведенный пример наглядно демонстрирует, как можно использовать память, чтобы вычислить значение в обратной польской нотации. Менее очевидно, что можно использовать стек, преобразовав стандартные инфиксные выражения в ОПН.
Примеры на языках программирования
На языке Паскаль обратная польская запись реализуется примерно так (приведена часть программы).
Для считывания чисел и операторов в цикле вызывается процедура, которая определяет, является ли токен числом или знаком операции. В первом случае значение записывается в стек, а во втором над двумя верхними числами стека выполняется соответствующие действие и результат сохраняется.
toktype := num;
read(с);
if с in ['+', '-', '*', '/'] then begin
if eoln then cn := ' ' else read(cn);
if cn = ' ' then
case с of
'+': toktype := add; '-': toktype := sub;
'*': toktype := mul; '/': toktype := div
end
else begin
if с = '-' then sgn := -1 else error := с <> '+';
с := cn
end
end;
if (not error) and (toktype = num) then getnumber;
if toktype <> num then begin
у := рор; х := рор;
if not error then
case toktype of
add: z := х+у; sub: z := х-у; mul: z := х*у; div: z := х/у
end
push(z);
C-реализация обратной польской записи (приведен часть программы):
for (s = strtok(s, w); s; s = strtok(0, w)) {
a = strtod(s, &e);
if (e > s) push(a);
#define rpnop(x) printf("%с:", *s), b = pop(), a = pop(), push(x)
else if (*s == '+') rpnop(a + b);
else if (*s == '-') rpnop(a - b);
else if (*s == '*') rpnop(a * b);
else if (*s == '/') rpnop(a / b);
#undef rpnop
}
Аппаратные реализации
В те времена, когда вычислительная техника стоила очень дорого, считалось хорошей идеей заставлять людей пользоваться ОПН. В 1960-х гг., как и сегодня, можно было купить калькуляторы, которые работают в обратной польской записи. Для сложения 2 и 3 в них необходимо ввести 2, затем 3 и нажать кнопку "плюс". На первый взгляд, ввод операндов до оператора казался сложным и трудно запоминающимся, но через некоторое время некоторые пристрастились к такому образу мышления и не могли понять, почему остальные настаивают на глупой инфиксной записи, которая так сложна и так ограничена.
Компания Burroughs даже построила мэйнфрейм, у которого не было никакой другой оперативной памяти, кроме стека. Единственное, что делала машина, – применяла алгоритмы и методы обратной польской записи к центральному стеку. Все ее операции расценивались как операторы ОПН, действие которых распространялось на n верхних значений. Например, команда Return брала адрес из вершины стека и т. д. Архитектура такой машины была простой, но недостаточно быстрой, чтобы конкурировать с более общими архитектурами. Многие, однако, до сих пор сожалеют о том, что такой простой и элегантный подход к вычислениям, где каждая программа была выражением ОПН, не нашел своего продолжения.
Одно время калькуляторы с обратной польской записью пользовались популярностью, и некоторые до сих пор отдают им предпочтение. Кроме того, были разработаны стек-ориентированные языки, такие как Forth. Сегодня он мало используется, но до сих пор вызывает ностальгию со стороны бывших его пользователей.
Так в чем смысл шутки об обратной польской сосиске?
Если считать сосиску оператором, то в инфиксной нотации она должна находиться внутри булки, как в обычном хот-доге. В обратной польской записи она находится правее двух половинок, готовая попасть между ними после вычисления. Теперь начинается самая трудная часть – горчица. Она уже находится на сосиске, т. е. уже вычислена как унарный оператор. Существует мнение, что горчица также должно быть показана как невычисленная и, следовательно, должна быть перемещена вправо от сосиски... Но возможно, для этого потребуется слишком большой стек...
