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

Пусть задано пpостое аpифметическое выpажение вида:

Совеpшим обход деpева, под котоpым будем понимать фоpмиpование стpоки символов из символов узлов и ветвей деpева. Обход будем совеpшать от самой левой ветви впpаво и узел пеpеписывать в выходную стpоку только после pассмотpения всех его ветвей. Результат обхода деpева имеет вид:

Хаpактеpные особенности выpажения (2) состоят в следовании символов опеpаций за символами опеpандов и в отсутствии скобок. Такая запись называется обpатной польской записью.

Обpатная польская запись обладает pядом замечательных свойств, котоpые пpевpащают ее в идеальный пpомежуточный язык пpи тpансляции. Во-пеpвых, вычисление выpажения, записанного в обpатной польской записи, может пpоводиться путем однокpатного пpосмотpа, что является весьма удобным пpи генеpации объектного кода пpогpамм. апpимеp, вычисление выpажения (2) может быть пpоведено следующим обpазом:

Во-втоpых, получение обpатной польской записи из исходного выpажения может осуществляться весьма пpосто на основе пpостого алгоpитма, пpедложенного Дейкстpой. Для этого вводится понятие стекового пpиоpитета опеpаций(табл. 1):

Пpосматpивается исходная стpока символов слева напpаво, опеpанды пеpеписываются в выходную стpоку, а знаки опеpаций заносятся в стек на основе следующих сообpажений:

Пpоцесс получения обpатной польской записи выpажения (1) схематично пpедставлен на pис. 2:

Источник

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

Два плюс два, умножить на два?

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

В математике существует древняя традиция помещать оператор между операндами (x+y), а не после операндов (xy+). Форма с оператором между операндами называется инфиксной записью. Форма с оператором после операндов называется постфиксной, или обратной польской записью в честь польского логика Я. Лукасевича (1958), который изучал свойства этой записи.
Обратная польская запись имеет ряд преимуществ перед инфиксной записью при выражении алгебраических формул. Во-первых, любая формула может быть выражена без скобок. Во-вторых, она удобна для вычисления формул в машинах со стеками. В-третьих, инфиксные операторы имеют приоритеты, которые произвольны и нежелательны. Например, мы знаем, что ab+c значит (ab)+c, а не a(b+c), поскольку произвольно было определено, что умножение имеет приоритет над сложением. Но имеет ли приоритет сдвиг влево перед операцией И? Кто знает? Обратная польская запись позволяет устранить такие недоразумения.

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

Алгоритм перевода в обратную польскую запись
Существует несколько алгоритмов для превращения инфиксных формул в обратную польскую запись. Мы рассмотрим переработанный алгоритм, идее которого предложена Э. Дейкстра (E.W. Dijkstra). Предположим, что формула состоит из переменных, двухоперандных операторов +,-,*,/,^, а также левой и правой скобок. Чтобы отметить конец формулы, мы будем вставлять символ после её последнего символа и перед первым символом следующей формулы.

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

Числа соответствуют следующим ситуациям:
1. Вагон на стрелке отправляется в Техас
2. Последний вагон, направившийся в Техас, разворачивается и направляется в Калифорнию
3. Вагон, находящийся на стрелке, и последний вагон, отправившийся в Техас, угоняются и исчезают
4. Остановка. Символы, находящиеся на Калифорнийской ветке, представляют собой формулу в обратной польской записи, если читать слева направо
5. Остановка. Произошла ошибка. Изначальная формула была некорректно сбалансирована

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

Пример вычисления выражения в обратной польской записи
Обратная польская запись идеально подходит для вычисления формул на компьютере со стеком. Формула состоит из n символов, каждый из которых является либо операндом, либо оператором. Алгоритм для вычисления формулы в обратной польской записи с использованием стека прост. Нужно просто прочитать обратную польскую запись слева направо. Если встречается операнд, его нужно пометить в стек. Если встречается оператор, нужно выполнить заданную им операцию.
В качестве примера рассмотрим вычисление следующего выражения: (8+2*5)/(1+3*2-4). Соответствующая формула в обратной польской записи выглядит так: 825*+132*+4-/
Число на вершине стека – это правый операнд (а не левый). Это очень важно дл операций деления, вычитания и возведения в степень, поскольку порядок следования операндов в данном случае имеет значение (в отличие от операций сложения и умножения). Другими словами, операция деления действует следующим образом: сначала в стек помещается числитель, потом знаменатель, и тогда операция даёт правильный результат. Отметим, что преобразовать обратную польскую запись в машинный код очень легко: нужно просто двигаться по формуле в обратной польской записи, записывая по одной команде для каждого символа. Если символ является константой или переменной, нужно вписывать команду помещения этой константы или переменной в стек, если символ является оператором, нужно вписывать команду выполнения это операции.

P.S. Исходные коды вы, как всегда, можете скачать на моём сайте, пока он не ляжет под хабраэффектом.
P.P.S. Теперь все могут написать свой калькулятор. С блэкджеком и скобками.

Источник

Разбор выражений. Обратная польская нотация

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

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

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

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

Например, следующее выражение:

в обратной польской нотации записывается следующим образом:

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

Очевидно, этот простой алгоритм выполняется за , т.е. порядка длины выражения.

Разбор простейших выражений

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

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

Будем идти по строке слева направо. Если текущий элемент — цифра или переменная, то положим в стек значение этого числа/переменной. Если текущий элемент — открывающая скобка, то положим её в стек. Если текущий элемент — закрывающая скобка, то будем выталкивать из стека и выполнять все операции до тех пор, пока мы не извлечём открывающую скобку (т.е., иначе говоря, встречая закрывающую скобку, мы выполняем все операции, находящиеся внутри этой скобки). Наконец, если текущий элемент — операция, то, пока на вершине стека находится операция с таким же или большим приоритетом, будем выталкивать и выполнять её.

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

Вот реализация данного метода на примере обычных операций :

Таким образом, мы научились вычислять значение выражения за , и при этом мы неявно воспользовались обратной польской нотацией: мы расположили операции в таком порядке, когда к моменту вычисления очередной операции оба её операнда уже вычислены. Слегка модифицировав вышеописанный алгоритм, можно получить выражение в обратной польской нотаци и в явном виде.

Унарные операции

Теперь предположим, что выражение содержит унарные операции (т.е. от одного аргумента). Например, особенно часто встречаются унарный плюс и минус.

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

Можно заметить, что перед унарной операцией всегда стоит либо другая операция, либо открывающая скобка, либо вообще ничего (если она стоит в самом начале строки). Перед бинарной операцией, напротив, всегда стоит либо операнд (число/переменная), либо закрывающая скобка. Таким образом, достаточно завести какой-нибудь флаг для указания того, может ли следующая операция быть унарной или нет.

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

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

Кроме того, надо заметить, что унарные операции фактически являются правоассоциативными — если подряд идут несколько унарных операций, то они должны обрабатываться справа налево (для описания этого случая см. ниже; приведённый здесь код уже учитывает правоассоциативность).

Реализация для бинарных операций и унарных операций :

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

Правоассоциативность

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

Таким образом, единственные отличия нужно внести в функцию calc:

Источник

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

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

Содержание

История

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

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

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

Описание

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

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

Особенности обратной польской записи следующие:

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

Общий порядок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

Haskell

Ссылки

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

ca:Notació polonesa inversa cs:Postfixová notace da:Omvendt polsk notation de:Umgekehrte Polnische Notation en:Reverse Polish notation es:Notación polaca inversa fi:Käänteinen puolalainen notaatio fr:Notation polonaise inverse he:כתיב פולני hr:Obrnuta poljska notacija hu:Fordított lengyel jelölés it:Notazione polacca inversa ja:逆ポーランド記法 ko:역폴란드 표기법 pl:Odwrotna notacja polska pt:Notação polonesa inversa simple:Postfix notation sl:Obrnjen poljski zapis sr:Обрнута пољска нотација sv:Omvänd polsk notation

Источник

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

Постфиксная нотация

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

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

Содержание

История

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

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

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

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

Определение

1. Если — переменная или константа, то есть .

2. Если — выражение вида , то есть .

3. Если — выражение вида , то есть .

Описание

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

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

Особенности обратной польской записи следующие:

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

Общий порядок

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

Примечания

Ссылки

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

Источник