Обратная польская запись
Материал из Википедии — свободной энциклопедии
Обратная польская нотация (ОПН) (Обратная польская запись, Постфиксная нотация, Бесскобочная символика Лукасевича, Польская инверсная запись, Полиз) — форма записи математических выражений, в которой операнды расположены перед операторами.
Содержание |
[править] История
Обратная польская нотация была разработана Австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 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)
КОН
КОН Перевести;
[править] Ссылки
Языки программирования, использующие ОПН в качестве основной:
Другие ссылки:
