Обратная польская запись: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
отмена правки 107634996 участника 213.230.73.90 (обс.)
Метка: отмена
оформление
Строка 1: Строка 1:
{{Математические нотации|logo=[[Файл:Postfix-dia.svg|125px]]}}
{{Математические нотации|logo=[[Файл:Postfix-dia.svg|125px]]}}
{{не путать|Польская нотация|(прямой) польской нотацией}}
{{не путать|Польская нотация|(прямой) польской нотацией}}
ом команд, по сравнению с обыет количество действий, которые нужно выполнить для получения результата.
'''Обра́тная по́льская запись ({{lang-en|Reverse Polish notation, RPN}})''' — форма записи [[Математическое выражение|математических]] и [[Логическое выражение|логических]] выражений, в которой [[операнд]]ы расположены перед знаками [[Операция (программирование)|операций]]. Также именуется как ''обратная бесскобочная запись'', ''постфиксная нотация'', ''бесскобочная символика Лукасевича'', ''польская инверсная запись'', ''ПОЛИЗ''.


== Преобразова стека приоритетнее '''''o1''''' ==
'''Стековой машиной''' называется алгоритм, проводящий вычисления по обратной польской записи (см. ниже ''[[#Пример вычисления выражений|пример вычисления выражений]]'').

== История ==
Обратная польская нотация (ОПН) была разработана [[Австралия|австралийским]] [[философия|философом]] и специалистом в области [[теория вычислительных машин|теории вычислительных машин]] [[Хэмблин, Чарльз|Чарльзом Хэмблином]] в середине [[1950-е|1950-х]] на основе [[Польская нотация|польской нотации]], которая была предложена в [[1920 год]]у польским математиком [[Лукасевич, Ян|Яном Лукасевичем]]. Работа Хэмблина была представлена на конференции в июне [[1957]], и издана в 1957 и [[1962]].

Первыми компьютерами, поддерживающими обратную польскую нотацию, были [[KDF9]] от [[English Electric Company]], который был анонсирован в [[1960]] и выпущен (появился в продаже) в [[1963]], и [[США|американский]] [[Burroughs B5000]], анонсирован в [[1961]], выпущен в том же 1963. Один из проектировщиков B5000, {{s|Р. С. Бартон}}, позже написал, что разработал обратную польскую запись независимо от Хэмблина, примерно в 1958, в процессе чтения книги по [[символьная логика|символьной логике]], и до того как познакомился с работой Хэмблина.

Компания [[Friden]] перенесла ОПН в настольные [[калькулятор]]ы, выпустив в июне 1964 модель EC-130. А в 1968 инженеры [[Hewlett-Packard]] разработали настольный калькулятор [[Hewlett-Packard 9100A|9100A]] с поддержкой ОПН. Этот калькулятор сделал обратную польскую нотацию популярной среди учёных и инженеров, даже несмотря на то, что в ранней рекламе 9100A ОПН не упоминалась. В [[1972]] калькулятор [[HP-35]] с поддержкой ОПН стал первым научным карманным калькулятором.

В 1971 году появился оригинальный [[язык программирования]] [[Forth]], языковая машина которого имеет двухстековую структуру и где все вычисления проводятся на [[стек]]е. В этом языке ОПН является естественным способом записи любых операций с данными, хотя возможна, при желании, реализация и обычной ([[Инфиксная нотация|инфиксной]]) записи арифметических операций.

ОПН применялась в советском инженерном калькуляторе Б3-19М (совместная разработка с ГДР), выпущенном в 1976 году. Все выпускаемые в [[СССР]] вплоть до конца 1980-х годов [[калькулятор|программируемые микрокалькуляторы]], за исключением «[[Электроника МК-85]]» и «[[Электроника МК-90]]», использовали ОПН — она проще реализовывалась и позволяла обойтись в программировании вычислений меньшим числом команд, по сравнению с обычной алгебраической нотацией, а количество программной памяти в этих моделях всегда было критическим ресурсом. ОПН используется в современных российских программируемых калькуляторах «[[Электроника МК-152]]» и «[[Электроника МК-161]]», что обеспечивает их совместимость с программами, написанными для советских калькуляторов.

== Определение ==
Чтобы дать индуктивное определение постфиксной нотации<ref>А. В. Ахо, Р. Сети, Д. Д. Ульман. ''Компиляторы: принципы, технологии и инструменты.'' М.: «Вильямс», 2003. С. 51.</ref>, обозначим выражения в инфиксной нотации <math>E</math>, <math>E_1</math>, <math>E_2</math>, эквивалентные им выражения в постфиксной нотации <math>\dot E</math> , <math>\dot E_1</math>, <math>\dot E_2</math> соответственно; <math>o</math> — произвольный бинарный оператор, тогда:

1. Если <math>E</math> — переменная или константа, то <math>\dot E</math> есть <math>E</math>.

2. Если <math>E</math> — выражение вида <math>E_1 o E_2</math>, то <math>\dot E</math> есть <math>\dot E_1 \dot E_2 o</math>.

3. Если <math>E</math> — выражение вида <math>(E_1)</math>, то <math>\dot E</math> есть <math>\dot E_1</math>.

== Описание ==
Отличительной особенностью обратной польской нотации является то, что все аргументы (или [[операнд]]ы) расположены перед знаком операции. В общем виде запись выглядит следующим образом:

* Запись набора операций состоит из последовательности операндов и знаков операций. Операнды в выражении при письменной записи разделяются пробелами.
* Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу.
* Результатом вычисления выражения становится результат последней вычисленной операции.

Например, рассмотрим вычисление выражения <code>{{s|7 2 3 * −}}</code> (эквивалентное выражение в инфиксной нотации: <code>{{s|7 − 2 * 3}}</code>).
# Первый по порядку знак операции — «*», поэтому первой выполняется операция умножения над операндами 2 и 3 (они стоят последними перед знаком). Выражение при этом преобразуется к виду <code>{{s|7 6 −}}</code> (результат умножения — 6, — заменяет тройку «2 3 *»).
# Второй знак операции — «−». Выполняется операция вычитания над операндами 7 и 6.
# Вычисление закончено. Результат последней операции равен 1, это и есть результат вычисления выражения.

Очевидное расширение обратной польской записи на унарные, тернарные и операции с любым другим количеством операндов: при использовании знаков таких операций в вычислении выражения операция применяется к соответствующему числу последних встретившихся операндов.

Особенности обратной польской записи следующие:
* Порядок выполнения операций однозначно задаётся порядком следования знаков операций в выражении, поэтому отпадает необходимость использования скобок и введения приоритетов и ассоциативности операций.
* В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций. Так, в инфиксной записи выражение <code>{{s|5 * (−3 + 8)}}</code> использует знак «минус» как символ унарной операции (изменение знака числа), а выражение <code>{{s|(10 − 15) * 3}}</code> применяет этот же знак для обозначения бинарной операции (вычитание). Конкретная операция определяется тем, в какой позиции находится знак. Обратная польская запись не позволяет этого: запись <code>{{s|5 3 − 8 + *}}</code> (условный аналог первого выражения) будет интерпретирована как ошибочная, поскольку невозможно определить, что «минус» после 5 и 3 обозначает не вычитание; в результате будет сделана попытка вычислить сначала <code>5 − 3</code>, затем <code>2 + 8</code>, после чего выяснится, что для операции умножения не хватает операндов. Чтобы всё же записать это выражение, придётся либо переформулировать его (например, записав вместо выражения <code>{{s|− 3}}</code> выражение <code>{{s|0 − 3}}</code>), либо ввести для операции изменения знака отдельное обозначение, например, «±»: <code>{{s|5 3 ± 8 + *}}</code>.
* Так же, как и в инфиксной нотации, в ОПН одно и то же вычисление может быть записано в нескольких разных вариантах. Например, выражение <code>{{s|(10 − 15) * 3}}</code> в ОПН можно записать как <code>{{s|10 15 − 3 *}}</code>, а можно — как <code>{{s|3 10 15 − *}}</code>
* Из-за отсутствия скобок обратная польская запись короче инфиксной. За этот счёт при вычислениях на калькуляторах повышается скорость работы оператора (уменьшается количество нажимаемых клавиш), а в программируемых устройствах сокращается объём тех частей программы, которые описывают вычисления. Последнее может быть немаловажно для портативных и встроенных вычислительных устройств, имеющих жёсткие ограничения на объём памяти.

== Вычисления на стеке ==

=== Общий порядок ===
Автоматизация вычисления выражений в обратной польской нотации основана на использовании [[стек]]а. Алгоритм вычисления для стековой машины элементарен:

# Обработка входного символа
#* Если на вход подан операнд, он помещается на вершину стека.
#* Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлечённых из стека, взятых в порядке добавления. Результат выполненной операции кладётся на вершину стека.
# Если входной набор символов обработан не полностью, перейти к шагу 1.
# После полной обработки входного набора символов результат вычисления выражения лежит на вершине стека.

Реализация стековой машины, как программная, так и аппаратная, чрезвычайно проста и может быть очень эффективной. Обратная польская запись совершенно унифицирована — она принципиально одинаково записывает унарные, бинарные, тернарные и любые другие операции, а также обращения к функциям, что позволяет не усложнять конструкцию вычислительных устройств при расширении набора поддерживаемых операций. Это и послужило причиной использования обратной польской записи в некоторых научных и программируемых микрокалькуляторах.

=== Пример вычисления выражений ===
Инфиксное выражение <math>(1 + 2) \times 4 + 3</math> в ОПН может быть записано так: <code> 1 2 + 4 × 3 +</code>

Вычисление производится слева направо, ввод интерпретируется как указано в приведённой ниже таблице (указано состояние стека после выполнения операции, вершина стека выделена <span style="color:red">красным цветом</span>):
{| class="standard"
!Ввод
!Операция
!Стек
|-
|1
|поместить в стек
|<span style="color:red">1</span>
|-
|2
|поместить в стек
|1, <span style="color:red">2</span>
|-
|<nowiki>+</nowiki>
|сложение
|<span style="color:red">3</span>
|-
|4
|поместить в стек
|3, <span style="color:red">4</span>
|-
|*
|умножение
|<span style="color:red">12</span>
|-
|3
|поместить в стек
|12, <span style="color:red">3</span>
|-
|<nowiki>+</nowiki>
|сложение
|<span style="color:red">15</span>
|-
|}

Результат, 15, в конце вычислений находится на вершине стека.

Клавиша «Ввод» (обозначаемая на калькуляторах как «Enter» или символом «↑») выполняет роль разделителя операндов, когда два операнда непосредственно следуют друг за другом. Если за операндом следует [[Знаки операций|знак операции]], то её нажатие не требуется, это сокращает количество действий, которые нужно выполнить для получения результата.

== Преобразование из инфиксной нотации ==
[[Дейкстра, Эдсгер Вайб|Эдсгер Дейкстра]] изобрёл алгоритм для преобразования выражений из [[инфиксная нотация|инфиксной нотации]] в ОПЗ. Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. Инфиксная нотация — это форма математических записей, которую использует большинство людей (например, <code>{{s|3 + 4}}</code> или <code>{{s|3 + 4 * (2 − 1)}}</code>). Как и алгоритм вычисления ОПЗ, [[алгоритм сортировочной станции]] основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операции. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.

=== Простой пример ===
Вход: <code>3 + 4</code>

Добавим <code>3</code> к выходной строке (если прочитано число, то оно сразу добавляется к выходной строке).

Помещаем <code>+</code> (или его Идентификатор) в стек операций.

Добавим <code>4</code> к выходной строке.

Мы прочитали всё выражение, теперь выталкиваем все оставшиеся в стеке операции в выходную строку. В нашем примере в стеке содержится только <code>+</code>.

Выходная строка: <code>3 4 +</code>

В данном примере проявляются некоторые правила: все числа переносятся в выходную строку сразу после прочтения; когда выражение прочитано полностью, все оставшиеся в стеке операции выталкиваются в выходную строку.

=== Алгоритм ===
* Пока есть ещё символы для чтения:
::* Читаем очередной символ.
::* Если символ является числом или постфиксной функцией (например, ! — [[факториал]]), добавляем его к выходной строке.
::* Если символ является префиксной функцией (например, sin — [[синус]]), помещаем его в стек.
::* Если символ является открывающей скобкой, помещаем его в стек.
::* Если символ является закрывающей скобкой:
:::: До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.
::::* Если существуют разные виды скобок, появление непарной скобки также свидетельствует об ошибке. Если какие-то скобки одновременно являются функциями (например, [x] — [[целая часть]]), добавляем к выходной строке символ этой функции.
::* Если символ является бинарной операцией '''''о1''''', тогда:
::: 1) пока на вершине стека префиксная функция…
::::: … ИЛИ операция на вершине стека приоритетнее '''''o1'''''
::::: … ИЛИ операция на вершине стека [[Ассоциативность (программирование)|левоассоциативная]] с приоритетом как у '''''o1'''''
::::: … ИЛИ операция на вершине стека [[Ассоциативность (программирование)|левоассоциативная]] с приоритетом как у '''''o1'''''
:::: … выталкиваем верхний элемент стека в выходную строку;
:::: … выталкиваем верхний элемент стека в выходную строку;
::: 2)перации система смотрит на предыдущий символ и определяет, чем будет минус, бинарной операцией или унарной функцией. Соответственно, в стеке и ОПЗ нужны разные символы для бинарного и унарного минуса.
::: 2) помещаем операцию '''''o1''''' в стек.
* Когда входная строка закончилась, выталкиваем все символы из стека в выходную строку. В стеке должны были остаться только символы операций; если это не так, значит в выражении не согласованы скобки.

==== Ограничения и модификации ====
Алгоритм предполагает, что исходная строка корректна (проверяются не все ошибки), и все префиксные/постфиксные функции унарные.

Модификацию для многоместных функций с фиксированным количеством аргументов см. [[Алгоритм сортировочной станции|в основной статье]].

Для операций вроде −''x'', являющихся как бинарными, так и унарными, нужна модификация: при обнаружении подобной операции система смотрит на предыдущий символ и определяет, чем будет минус, бинарной операцией или унарной функцией. Соответственно, в стеке и ОПЗ нужны разные символы для бинарного и унарного минуса.

=== Сложный пример ===
=== Сложный пример ===
[[Приоритет операции|Приоритеты]]:
[[Приоритет операции|Приоритеты]]:

Версия от 11:15, 5 ноября 2020

Не следует путать с (прямой) польской нотацией.

ом команд, по сравнению с обыет количество действий, которые нужно выполнить для получения результата.

Преобразова стека приоритетнее o1

… ИЛИ операция на вершине стека левоассоциативная с приоритетом как у o1
… выталкиваем верхний элемент стека в выходную строку;
2)перации система смотрит на предыдущий символ и определяет, чем будет минус, бинарной операцией или унарной функцией. Соответственно, в стеке и ОПЗ нужны разные символы для бинарного и унарного минуса.

Сложный пример

Приоритеты:

  • высокий: ^
  • средний: * /
  • низкий: + −
  • самый низкий: ()
Вход: 3 + 4 * 2 / (1 - 5)^2

Читаем «3»
 Добавим «3» к выходной строке
  Выход: 3

Читаем «+»
 Кладём «+» в стек
  Выход: 3
  Стек: +

Читаем «4»
 Добавим «4» к выходной строке
  Выход: 3 4
  Стек: +

Читаем «*»
 Кладём «*» в стек
  Выход: 3 4
  Стек: + *

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2
  Стек: + *

Читаем «/»
 Выталкиваем «*» из стека в выходную строку, кладём «/» в стек
  Выход: 3 4 2 *
  Стек: + /

Читаем «(»
 Кладём «(» в стек
  Выход: 3 4 2 *
  Стек: + / (

Читаем «1»
 Добавим «1» к выходной строке
  Выход: 3 4 2 * 1
  Стек: + / (

Читаем «−»
 Кладём «−» в стек
  Выход: 3 4 2 * 1
  Стек: + / ( −

Читаем «5»
 Добавим «5» к выходной строке
  Выход: 3 4 2 * 1 5
  Стек: + / ( -

Читаем «)»
 Выталкиваем «−» из стека в выходную строку, выталкиваем «(»
  Выход: 3 4 2 * 1 5 −
  Стек: + /

Читаем «^»
 Кладём «^» в стек
  Выход: 3 4 2 * 1 5 −
  Стек: + / ^

Читаем «2»
 Добавим «2» к выходной строке
  Выход: 3 4 2 * 1 5 − 2
  Стек: + / ^

Конец выражения
 Выталкиваем все элементы из стека в строку
  Выход: 3 4 2 * 1 5 − 2 ^ / +

Оптимизация выражений

Если вы пишете интерпретатор, то выходная строка, полученная после преобразования исходного выражения в обратную польскую нотацию, может храниться вместо исходного выражения для последующей интерпретации. Обратная польская нотация также позволяет компьютеру упрощать выражения.

Пример алгоритма упрощения выражения

Рассмотрим алгоритм, который осуществляет предвычисление констант в выражении. Дано выражение в ОПН. Нам понадобится стек для хранения смешанных данных (чисел и операторов).

Алгоритм подобен тому, который применяется для вычисления выражений. Мы просматриваем выражение слева направо.

Пока есть символы для чтения:

  • Читаем очередной символ.
  • Если символ является числом, помещаем его в стек.
  • Если символ является переменной, считая что переменная имеет значение null, помещаем символ в стек.
  • Если символ является оператором:
  • 1) (если все аргументы оператора, лежащие в стеке, имеют значение, отличное от null) выталкиваем аргументы оператора из стека и помещаем в стек результат операции;
  • 2) (если хотя бы один из аргументов имеет значение null) считая что результат операции null, кладём символ оператора в стек.

После того, как всё выражение просмотрено, то, что осталось в стеке, является оптимизированым выражением (операторы выражения лежат в стеке в обратном порядке).

Пример работы алгоритма

Выражение
Инфиксная нотация: exp(-1/2*x)
Обратная Польская нотация: -1 2 / x * exp

Читаем: «-1»
 Кладём «-1» в стек
  Стек: -1

Читаем: «2»
 Кладём «2» в стек
  Стек: -1 2

Читаем: «/»
 Вычисляем частное, результат кладём в стек
  Стек: -0.5

Читаем: «x»
 Кладём «x» в стек со значением null
  Стек: -0.5 x(null)

Читаем: «*»
 Кладём «*» в стек со значением null
  Стек: -0.5 x(null) *(null)

Читаем «exp»
 Кладём «exp» в стек со значением null
  Стек: -0.5 x(null) *(null) exp(null)

Результат оптимизации: -0.5 x * exp

Данный метод, очевидно, не включает всех возможных способов оптимизации.

Примеры реализации

В статье «Обратная польская запись: примеры реализации» собраны примеры реализации обратной польской записи на различных языках программирования.

Практические реализации

В качестве практического применения данной методики можно привести организацию байт-кода конфигураций прикладных решений системы 1С:Предприятие. Официального подтверждения компания 1С не дает, но пользователи данной системы на специализированных форумах приводят доказательства и алгоритмы, позволяющие декомпилировать исходные тексты.

Литература

  • Т. Пратт, М. Зелковиц. Языки программирования: разработка и реализация = Terrence W. Pratt, Marvin V. Zelkowitz. Programming Languages: Design and Implementation. — 4-е издание. — Питер, 2002. — 688 с. — (Классика Computer Science). — 4000 экз. — ISBN 5-318-00189-0.

Примечания

См. также

Языки программирования, использующие ОПН в качестве основной:

Ссылки

Источник — https://ru.wikipedia.org/w/index.php?title=Обратная_польская_запись&oldid=110306561