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

Материал из Википедии — свободной энциклопедии
Это старая версия этой страницы, сохранённая 217.66.71.118 (обсуждение) в 09:35, 22 октября 2007 (→Ссылки: стилевые правки). Она может серьёзно отличаться от текущей версии.
Перейти к навигации Перейти к поиску

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

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

История

Обратная польская нотация была разработана австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 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 меньше приоритета оператора, находящегося на вершине стека…
…выталкиваем верхние элементы стека c большим либо равным приоритетом в выходную строку;
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

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

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

Глагол

 ПЕР
   Стек: РЯД 20H ИЗ ЗНАК;
 
 ЗАДАЧА Преимущество(зн: ЗНАК): ЦЕЛ;
 УКАЗ
   ВЫБРАТЬ зн ИЗ
     '*', '/': ВОЗВРАТ 3
   | '-', '+': ВОЗВРАТ 2
   | '(', ')': ВОЗВРАТ 1
   ИНАЧЕ ВОЗВРАТ 0 КОН
 КОН Преимущество;
 
 ЗАДАЧА Добавить(зн: ЗНАК);
 УКАЗ
   ЕСЛИ ДЛИНА(Стек) = РАЗМЕР(Стек) ТО Вывод.Цепь("Ошибка: стек переполнен."); СТОП(0) КОН;
   Стек[ДЛИНА(Стек)] := зн
 КОН Добавить;
 
 ЗАДАЧА Удалить(): ЗНАК;
 ПЕР
   зн: ЗНАК;
 УКАЗ
   ЕСЛИ ДЛИНА(Стек) = 0 ТО Вывод.Цепь("Ошибка: стек пуст."); СТОП(0) КОН;
   зн := Стек[ДЛИНА(Стек)-1];
   Стек[ДЛИНА(Стек)-1] := 0X;
   ВОЗВРАТ зн
 КОН Удалить;
 
 ЗАДАЧА Перевести(вход-, выход+: РЯД ИЗ ЗНАК);
 ПЕР
   сч1, сч2: УЗКЦЕЛ;
   зн: ЗНАК;
 УКАЗ
   зн := 0X; сч2 := 0;
   ОТ сч1 := 0 ДО ДЛИНА(вход)-1 ВЫП
     ЕСЛИ вход[сч1] = ")" ТО
       ПОКА Стек[ДЛИНА(Стек)-1] # "(" ВЫП
         выход[сч2] := Удалить();
         УВЕЛИЧИТЬ(сч2)
       КОН;
       зн := Удалить()
     АЕСЛИ вход[сч1] = "(" ТО
       Добавить(вход[сч1])
     АЕСЛИ (вход[сч1] = "+") ИЛИ (вход[сч1] = "-") ИЛИ (вход[сч1] = "/") ИЛИ (вход[сч1] = "*") ТО
       ЕСЛИ ДЛИНА(Стек) = 0 ТО Добавить(вход[сч1]) ИНАЧЕ
         ЕСЛИ Преимущество(вход[сч1]) > Преимущество(Стек[ДЛИНА(Стек)-1]) ТО
           Добавить(вход[сч1])
         ИНАЧЕ
           ПОКА (ДЛИНА(Стек) # 0) И (Преимущество(вход[сч1]) <= Преимущество(Стек[ДЛИНА(Стек)-1])) ВЫП
             выход[сч2] := Удалить(); УВЕЛИЧИТЬ(сч2)
           КОН;
           Добавить(вход[сч1])
         КОН
       КОН
     АЕСЛИ Знак.Буква(вход[сч1]) ТО
       выход[сч2] := вход[сч1];
       УВЕЛИЧИТЬ(сч2)
     КОН
   КОН;
   ПОКА ДЛИНА(Стек) # 0 ВЫП
     выход[сч2] := Удалить();
     УВЕЛИЧИТЬ(сч2)
   КОН
 КОН Перевести;.

Ссылки

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

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

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