Обратная польская нотация ( RPN ), также известная как обратная нотация Лукасевича , польская постфиксная нотация или просто постфиксная нотация , представляет собой математическую нотацию, в которой операторы следуют за своими операндами , в отличие от польской нотации (PN), в которой операторы предшествуют своим операндам. Он не нуждается в круглых скобках, если каждый оператор имеет фиксированное количество операндов . Описание «поляк» относится к национальности логика Яна Лукасевича [1] , который изобрел польскую нотацию в 1924 году.[2] [3]
Обратная польская схема была предложена в 1954 году Артуром Бёрксом , Доном Уорреном и Джесси Райтом [4] и независимо заново изобретена Фридрихом Л. Бауэром и Эдсгером В. Дейкстрой в начале 1960-х годов для уменьшения доступа к памяти компьютера и использования стека для оценки выражения . Алгоритмы и обозначения для этой схемы были расширены австралийским философом и ученым-компьютерщиком Чарльзом Л. Хамблином в середине 1950-х годов. [5] [6] [7] [8] [9] [10]
В 1970-х и 1980-х годах Hewlett-Packard использовала RPN во всех своих настольных и портативных калькуляторах и продолжала использовать его в некоторых моделях до 2020-х годов. [11] [12] В информатике обратная польская нотация используется в ориентированных на стек языках программирования, таких как Forth , STOIC , PostScript , RPL и Joy .
В обратной польской нотации операторы следуют за своими операндами ; например, чтобы сложить 3 и 4 вместе, можно было бы написать 3 4 + , а не 3 + 4 . Если имеется несколько операций, операторы даются сразу после их конечных операндов (часто оператор принимает два операнда, и в этом случае оператор записывается после второго операнда); поэтому выражение, записанное 3 − 4 + 5 в обычной записи, будет записано как 3 4 − 5 + в обратной польской записи: сначала из 3 вычитается 4, затем к нему прибавляется 5. Преимущество обратной польской нотации состоит в том, что она устраняет необходимость в круглых скобках, которые необходимы для инфиксной нотации . В то время как 3 − 4 × 5также можно записать 3 − (4 × 5) , что означает нечто совершенно отличное от (3 − 4) × 5 . В обратной польской записи первое можно записать как 3 4 5 × - , что однозначно означает 3 (4 5 ×) - , что сокращается до 3 20 - (которое далее может быть уменьшено до -17); последнее можно записать как 3 4 − 5 × (или 5 3 4 − × , если сохранить аналогичное форматирование), что однозначно означает (3 4 −) 5 × .
Для сравнения, тестирование обратной польской записи с алгебраической записью показало, что обратная польская запись приводит к более быстрым вычислениям по двум причинам. Первая причина заключается в том, что обратному польскому калькулятору не нужно заключать выражения в скобки, поэтому для выполнения типичных вычислений требуется ввести меньше операций. Кроме того, пользователи обратных польских калькуляторов допустили меньше ошибок, чем другие типы калькуляторов. [13] [14] Более поздние исследования показали, что увеличение скорости обратной польской записи может быть связано с меньшим количеством нажатий клавиш, необходимых для ввода этой записи, а не с меньшей когнитивной нагрузкой на ее пользователей. [15]Однако неофициальные данные свидетельствуют о том, что пользователям сложнее выучить обратную польскую нотацию, чем алгебраическую. [14]
Эдсгер В. Дейкстра изобрел алгоритм маневровой станции для преобразования инфиксных выражений в постфиксные выражения (обратная польская нотация), названный так потому, что его работа напоминает работу маневровой станции на железной дороге .