Войти
 |
| Постфиксная нотация («обратная польская») Обозначение префикса («польский») |
|
Обратная польская нотация ( RPN), также известная как польская постфиксная нотация или просто постфиксная нотация, представляет собой математическую нотацию, в которой операторы следуют за своими операндами, в отличие от польской записи (PN), в которой операторы предшествуют своим операндам. Скобки не нужны, если каждый оператор имеет фиксированное количество операндов. Описание «Польский» относится к национальности из логик Ян Лукасевичем, который изобрел польскую нотацию в 1924 году.
Обратная польская схема была предложена в 1954 году Артуром Берксом, Доном Уорреном и Джесси Райтом и независимо заново изобретена Фридрихом Л. Бауэром и Эдсгером В. Дейкстра в начале 1960-х годов, чтобы уменьшить доступ к памяти компьютера и использовать стек для оценки выражений. В алгоритмы и обозначения для этой схемы были расширены австралийским философом и компьютерной ученый Чарльз Л. Хамблин в середине 1950-х годов.
В течение 1970-х и 1980-х годов Hewlett-Packard использовала RPN во всех своих настольных и портативных калькуляторах и продолжала использовать его в некоторых моделях до 2020-х годов. В информатике обратная польская запись используется в стек-ориентированных языках программирования, таких как 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 ×.
Для сравнения, проверка обратной польской записи с алгебраической записью, обратная польская запись, как было обнаружено, приводит к более быстрым вычислениям по двум причинам. Первая причина заключается в том, что калькуляторы с обратным польским языком не нуждаются в выражениях в скобках, поэтому для выполнения типичных вычислений требуется вводить меньше операций. Кроме того, пользователи обратных польских калькуляторов сделали меньше ошибок, чем у других типов калькуляторов. Более поздние исследования показали, что повышенная скорость обратной польской нотации может быть связана с меньшим количеством нажатий клавиш, необходимых для ввода этой нотации, а не с меньшей когнитивной нагрузкой на пользователей. Однако неофициальные данные свидетельствуют о том, что пользователям изучать обратную польскую нотацию труднее, чем алгебраическую нотацию.
Эдсгер В. Дейкстра изобрел алгоритм маневровой станции для преобразования инфиксных выражений в постфиксные выражения (обратная польская нотация), названный так потому, что его работа похожа на работу маневровой станции.
Есть и другие способы создания постфиксных выражений из инфиксных выражений. Большинство синтаксических анализаторов приоритета операторов можно модифицировать для создания постфиксных выражений; в частности, как только абстрактное синтаксическое дерево построено, соответствующее постфиксное выражение задается простым обходом этого дерева после упорядочения.
Первые компьютеры для реализации архитектуры, позволяющие обратной польской нотации были English Electric Company «S KDF9 машина, которая была объявлена в 1960 году и в продаже в 1963 году, и Burroughs B5000, объявленный в 1961 году, а также выступил в 1963 году:
Предположительно, дизайнеры KDF9 позаимствовали идеи из GEORGE (General Order Generator) Хамблина, системы программирования автокода, написанной для компьютера DEUCE, установленного в Сиднейском университете, Австралия, в 1957 году.
Один из разработчиков B5000, Роберт С. Бартон, позже писал, что он разработал обратную польскую нотацию независимо от Хамблина где-то в 1958 году после прочтения учебника 1954 года по символической логике Ирвинга Копи, где он обнаружил ссылку на польскую нотацию, в которой он также читал произведения Яна Лукасевича, еще до того, как узнал о творчестве Хамблина.
Компания Friden представила обратную польскую нотацию на рынке настольных калькуляторов с EC-130, разработанным Робертом «Бобом» Эпплби Рейгеном, поддерживающим четырехуровневый стек в июне 1963 года. Преемник EC-132 добавил функцию квадратного корня в апреле 1965 года. В 1966 году калькулятор Monroe Epic поддерживал безымянную схему ввода, похожую на RPN.
Промо-кепка Hewlett-Packard "No Equals" 1980-х годов - и хвастовство, и отсылка к RPN. Инженеры Hewlett-Packard разработали настольный калькулятор 9100A в 1968 году с обратной польской нотацией только с тремя уровнями стека, вариант с обратной польской нотацией, позже названный трехуровневым RPN. Этот калькулятор популяризировал обратную польскую нотацию в научном и инженерном сообществе. HP-35, первый в мире карманный научный калькулятор, представил классическую четыре уровня RPN в 1972. HP используется обратная польская запись на каждом портативном калькуляторе было продано, будь то научные, финансовые, или программируемый, пока он не представил HP-10, добавив машинный калькулятор в 1977 году. К этому времени HP была ведущим производителем калькуляторов для профессионалов, включая инженеров и бухгалтеров.
Более поздние калькуляторы с ЖК-дисплеями в начале 1980-х, такие как HP-10C, HP-11C, HP-15C, HP-16C и финансовый калькулятор HP-12C, также использовали обратную польскую нотацию. В 1988 году Hewlett-Packard представила бизнес-калькулятор HP-19B без обратной польской нотации, но его преемник 1990 года, HP-19BII, дал пользователям возможность использовать алгебраическую или обратную польскую нотацию.
Примерно в 1987 году HP представила RPL, объектно-ориентированный преемник обратной польской нотации. Он отличается от классической обратной польской нотации за счет использования стека, ограниченного только объемом доступной памяти (вместо трех или четырех фиксированных уровней), и который может содержать все виды объектов данных (включая символы, строки, списки, матрицы, графику, программы). и т. д.) вместо чисел. Он также изменил поведение стека, чтобы больше не дублировать верхний регистр при отбрасывании (поскольку в неограниченном стеке больше нет верхнего регистра) и поведение ↵ Enterключа, так что он больше не дублирует значения в Y при определенных условиях, обе части конкретного набора правил так называемого автоматического стека памяти или операционного стека (памяти) в классической обратной польской нотации для упрощения некоторых вычислений и экономии нажатий клавиш, но которые также иногда вызывают путаницу среди пользователей, не знакомых с эти свойства. С 1990 по 2003 год HP производила серию графических калькуляторов RPL HP-48, а в 2006 году представила HP 50g.
С 2011 года Hewlett-Packard предлагала модели калькуляторов 12C, 12C Platinum, 17bII +, 20b, 30b, 33s, 35s, 48gII (RPL) и 50g (RPL), которые поддерживают обратную польскую нотацию. В то время как калькуляторы, эмулирующие классические модели, продолжают поддерживать классическую обратную польскую запись, новые модели обратной польской записи имеют вариант обратной польской записи, в которой ↵ Enterключ ведет себя как в RPL. Этот последний вариант иногда называют входным RPN. В 2013 году HP Prime представила 128-уровневую форму входного RPN, называемую расширенным RPN. К концу 2017 года только 12C, 12C Platinum, 17bii +, 35s и Prime останутся активными моделями HP, поддерживающими обратную польскую нотацию.
Разработанные сообществом калькуляторы WP 31S и WP 34S, основанные на аппаратной платформе HP 20b / HP 30b, поддерживают классическую обратную польскую нотацию в стиле Hewlett-Packard с четырех- или восьмиуровневым стеком. Семиуровневый стек был реализован в настольном научном калькуляторе MITS 7400C в 1972 году, а восьмиуровневый стек уже был предложен Джоном А. Боллом в 1978 году.
В Великобритании Клайв Синклер «s Sinclair Научные и научно - Programmable модели, используемые в обратной польской нотации.
В 1974 году Commodore выпустила Minuteman * 6 (MM6) без ↵ Enterключа и Minuteman * 6X (MM6X) с ↵ Enterключом, оба реализовали форму двухуровневого RPN. SR4921 RPN пришел с вариантом четыре уровня RPN с уровнями стека имени X, Y, Z, W и (а не Т). В отличие от реализации обратной польской нотации Hewlett-Packard, W заполняется 0 вместо того, чтобы его содержимое дублировалось при отбрасывании стека.
Prinz и Prinztronic были торговыми марками под собственным брендом британской сети магазинов фото- и электронных товаров Dixons, позже переименованной в магазины Currys Digital и ставшей частью DSG International. В 1970-х годах под брендом Prinztronic продавалось множество моделей калькуляторов, и все они были произведены для них другими компаниями.
Среди них был Программируемый научный калькулятор PROGRAM с обратной польской нотацией.
В 1978 году в бортовом навигационном компьютере Heathkit OC-1401 / OCW-1401 использовались пятиуровневые РПН.
Советские программируемые калькуляторы ( МК-52, МК-61, Б3-34 и более ранние модели Б3-21 ) использовали обратную польскую нотацию как для автоматического режима, так и для программирования. Современные российские калькуляторы МК-161 и МК-152, разработанные и производимые в Новосибирске с 2007 года и предлагаемые компанией Semico, обратно совместимы с ними. Их расширенная архитектура также основана на обратной польской нотации.
Существующие реализации, использующие обратную польскую нотацию, включают:
