Обратная польская запись - Reverse Polish notation

Postfix-dia.svg

Обозначение инфиксов

Обратная польская нотация ( 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.

Фирма Хьюлет-Паккард

Основная статья: Калькуляторы HP
Промо-кепка 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

Разработанные сообществом калькуляторы WP 31S и WP 34S , основанные на аппаратной платформе HP 20b / HP 30b, поддерживают классическую обратную польскую нотацию в стиле Hewlett-Packard с четырех- или восьмиуровневым стеком. Семиуровневый стек был реализован в настольном научном калькуляторе MITS 7400C в 1972 году, а восьмиуровневый стек уже был предложен Джоном А. Боллом в 1978 году.

Sinclair Radionics

В Великобритании Клайв Синклер «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 вместо того, чтобы его содержимое дублировалось при отбрасывании стека.

Prinztronic

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, обратно совместимы с ними. Их расширенная архитектура также основана на обратной польской нотации.

Другой

Существующие реализации, использующие обратную польскую нотацию, включают:

  • Языки программирования, ориентированные на стек, такие как:
  • Калькуляторы оборудования:
    • Некоторые калькуляторы Hewlett-Packard для науки / техники и бизнеса / финансов
    • Semico калькуляторов
    • SwissMicros калькуляторов
    • Некоторые калькуляторы APF также могут использовать RPN
  • Программные калькуляторы:
    • Калькулятор Mac OS X
    • Несколько приложений для Apple iPhone, например, «калькулятор обратной полировки».
    • Несколько приложений для Android, например "RealCalc"
    • Несколько приложений для Windows 10 Mobile, например «RPN9»
    • Программа калькулятора системы unix dc
    • Пакет библиотеки Emacs Lisp calc
    • Калькулятор Xorg ( xcalc )
    • grpn научный / инженерный калькулятор с использованием GIMP Toolkit ( GTK + )
    • F-корреляции в элементах словаря MultiValue
    • RRDtool , широко используемое программное обеспечение для составления таблиц и построения графиков.
    • grdmath, программа для алгебраических операций с сетками NetCDF , часть набора Generic Mapping Tools (GMT)
    • galculator, настольный калькулятор GTK
    • Калькулятор стека без мыши, научный / инженерный калькулятор, включая комплексные числа.
    • rpCalc, простой калькулятор обратной полировки, написанный на Python для Linux и MS Windows и опубликованный под лицензией GNU GPLv2 .
    • orpie, калькулятор RPN для терминала для вещественных или комплексных чисел или матриц.

Смотрите также

использованная литература

дальнейшее чтение

внешние ссылки