imported>Master-lame-master в 13:01, 23 июня 2025

2025-06-23T13:01:46Z

Новая страница

{{не путать|Польская нотация|(прямой) польской нотацией}}
{{Математические нотации|logo=[[Файл:Postfix-dia.svg|125px]]}}
[[Файл:Typing the calculation for "8 times 6" into a pocket calculator HP-32SII which uses RPN logic.webm|thumb|upright|Нажатие клавиш для расчета восемь раз по шесть на HP-32SII (с использованием RPN) 1991 г.]]
'''Обра́тная по́льская за́пись''' ({{lang-en|Reverse Polish notation, RPN}}), также известна как '''по́стфиксная нота́ция''' (запись) — форма записи [[Математическое выражение|математических]] и [[Логическое выражение|логических]] выражений, в которой [[операнд]]ы расположены перед знаками [[Операция (программирование)|операций]]. Также именуется как ''обратная бесскобочная запись'', ''постфиксная нотация'', ''бесскобочная символика Лукасевича'', ''польская инверсная запись'', ''ПОЛИЗ''.

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

== История ==
Обратная польская нотация (ОПН) была разработана [[Австралия|австралийским]] [[философия|философом]] и специалистом в области [[теория вычислительных машин|теории вычислительных машин]] [[Хэмблин, Чарльз|Чарльзом Хэмблином]] в середине 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]] разработали настольный калькулятор [[HP 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>

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

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

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

== Преобразование из инфиксной нотации ==
[[Дейкстра, Эдсгер Вайб|Эдсгер Дейкстра]] изобрёл алгоритм для преобразования выражений из [[инфиксная нотация|инфиксной нотации]] в ОПЗ. Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. Как и алгоритм вычисления ОПЗ, [[алгоритм сортировочной станции]] основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операции. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.

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

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

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

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

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

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

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

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

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

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

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

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

* самый высокий: выражения, заключённые в скобки ( )
* высокий: ^
* средний: * /
* низкий: + −
Вход: 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''''', кладём символ оператора в стек.

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

=== Пример работы алгоритма ===
<source lang="html4strict">
Выражение
Инфиксная нотация: 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
</source>
Данный метод, очевидно, не включает всех возможных способов оптимизации.

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

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

== Литература ==
* {{книга|автор=Т. Пратт, М. Зелковиц|заглавие=Языки программирования: разработка и реализация|оригинал=Terrence W. Pratt, Marvin V. Zelkowitz. Programming Languages: Design and Implementation|издание=4-е издание|издательство=Питер|год=2002|серия=Классика Computer Science|страниц=688|isbn=5-318-00189-0|тираж=4000|ref=Пратт, Зелковиц}}

== Примечания ==
{{примечания}}

== См. также ==
Языки программирования, использующие ОПН в качестве основной:
* [[Forth (язык программирования)|Forth]]
* [[Factor (язык программирования)|Factor]]
* [[Postscript]]
* Язык стилей оформления [[BibTeX]]

== Ссылки ==
* [http://algolist.manual.ru/maths/misc/revpn.php Обратная польская нотация]
* http://www.univer.omsk.ru/students/m84/docs/pol_zap.html
* [http://martiros24.blogspot.ru/2016/06/blog-post.html Реализация польской инверсной записи (ПОЛИЗа) на PHP]

{{rq|
{{нет источников|дата=2024-05-10}}
{{нет сносок|дата=2024-05-10}}
}}
{{Внешние ссылки}}

[[Категория:Калькуляторы]]
[[Категория:Математические обозначения]]

Обратная польская запись - История изменений

imported>Master-lame-master в 13:01, 23 июня 2025