Обратная польская запись

Эту статью следует викифицировать.
Пожалуйста, оформите её согласно общим правилам и указаниям.

Обратная польская нотация (ОПН) (Обратная польская запись, Постфиксная нотация, Бесскобочная символика Лукасевича, Польская инверсная запись, Полиз, англ. RPNReverse Polish Notation) — форма записи математических выражений, в которой операнды расположены перед операторами.

Содержание

История

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

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

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

Описание

Отличительной особенностью обратной польской нотации является то, что все аргументы (или операнды) расположены перед операцией (оператором). Это позволяет избавиться от необходимости использования скобок. Например, выражение 3 × (4 + 7) будет выглядеть как 3 4 7 + × (можно записать компактней: 4 7 + 3 ×).

Вычисления в обратной польской нотации основаны на стеке, это означает, что операнды достаются из стека, и результат вычисления кладётся обратно в стек. На первый взгляд это может выглядеть непонятно, однако, обратная польская нотация имеет важное приемущество — она невероятно проста для разбора, поэтому её реализации на компьютере требует мало ресурсов и выполняется быстро.

Практические выводы

  • Вычисление выполняется слева направо.
  • Операнды предшествуют своему оператору. При выполнении операции они удаляются.
  • Когда операция выполнена, результат сам становится операндом (для следующих операторов).
  • В обратной польской нотации нет скобок и нет приоритетов операций.
  • Большинство вычислений в Обратной Польской нотации записываются короче, нежели в инфиксной.

Пример вычисления выражения

Выражение ((1 + 2) × 4) + 3 в ОПН может быть записано так:

1 2 + 4 × 3 +

Вычисление производится следующим образом (указано состояние стека после выполнения операции):

Ввод Операция Стек
1 поместить в стек 1
2 поместить в стек 1, 2
+ сложение 3
4 поместить в стек 3, 4
* умножение 12
3 поместить в стек 12, 3
+ сложение 15

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

Другой способ представить работу стека в процессе вычисления представлен ниже (на примере калькулятора HP48S).

±--------------+
|             1 |  1 [ввод]
±--------------+
±--------------+
|             1 |
|             2 |  2
±--------------+
±--------------+
|             3 |  + 
±--------------+
±--------------+
|             3 |
|             4 |  4
±--------------+
±--------------+
|            12 |  * 
±--------------+
±--------------+
|            12 |
|             3 |  3
±--------------+
±--------------+
|            15 |  + 
±--------------+

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

Преобразование из инфиксной нотации

Эдскер Дейкстра изобрёл алгоритм для преобразования выражений из инфиксной нотации в ОПН. Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. Инфиксная нотация — это форма математических записей, которую использует большинство людей (например, 3 + 4 или 3 + 4 × ( 2 - 1 )). Как и алгоритм вычисления ОПН, алгоритм сортировочной станции основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операторы. Преобразующая программа читает входную строку последовательно символ за символом (символ, это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.

Простой пример

Вход: 3+4

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

Помещаем + (или его Идентификатор) в стек операторов.

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

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

Выходная строке: 3 4 +

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

Алгоритм

  • Пока есть ещё символы для чтения:
  • Читаем очередной символ.
  • Если символ является числом, добавить его к выходной строке.
  • Если символ является символом функции, помещаем его в стек.
  • Если символ является разделителем аргументов функции (то есть, запятая):
До тех пор, пока верхним элементом стека не станет открывающаяся скобка, выталкиваем элементы из стека в выходную строку. Если открывающаяся скобка не встретилась, это означает, что в выражении либо неверно поставлен разделитель, либо несогласованы скобки.
  • Если символ является оператором, о1, тогда:
1) пока…
…(если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…
…(если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…
…выталкиваем верхние элементы стека в выходную строку;
2) помещаем оператор o1 в стек.
  • Если символ является открывающейся скобкой, помещаем его в стек.
  • Если символ является закрывающейся скобкой, выталкиваем элементы из стека в выходную строку до тех пор, пока на вершине стека не окажется открывающаяся скобка. При этом открывающаяся скобка удаляется из стека, но в выходную строку не добавляется. Если после этого шага на вершине стека оказывается символ функции, выталкиваем его в выходную строку. Если стек закончился раньше, чем мы встретил открывающуюся скобку, это означает, что в выражении несогласованы скобки.
  • Когда входная строка закончилась, вытолкнуть все символы из стека в выходную строку. (В стеке должны были остаться только символы операторов; если это не так, значит в выражении несогласованы скобки.)

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

Приоритеты: 
* ^ высокий
* * / средний
* + - низкий
Вход: 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

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

Ссылки

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

Другие ссылки:

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home