Обратная польская нотация — это формат представления формул математики и логики, в котором операнды располагаются впереди знака операции.
Введение
В математических дисциплинах с давних времён принято размещать оператор между операндами, а не за ними. Например, (X+Z), но никак не (XZ+).
Формат записи, когда оператор располагается между операндами обозначается термином «инфиксная запись».
Формат записи, когда оператор располагается за операндами принято называть постфиксной записью или обратной польской нотацией.
Польской нотация названа в честь польского математика Я. Лукасевича, изучавшего особенности такой нотации. Обратная польская нотация обладает рядом достоинств, которых нет у инфиксной нотации при написании формул алгебры:
- Практически любую формулу возможно записать без применения скобок.
- Она очень практична при расчёте формул в стековых машинах. Стековой машиной считается алгоритмический формат, который выполняет все расчёты по обратной польской записи.
У инфиксных операторов существуют приоритетные свойства, которые являются произвольными и часто нежелательными. К примеру, известно, что xy + z означает (xy) + z, а никак не x(y + z), так как изначально считается, что операция умножения обладает приоритетным преимуществом перед сложением. Но обладает ли приоритетом, например, сдвиг в левую сторону перед логическим «И», никто не определял. Обратная польская запись предполагает устранение всех неопределённостей.
Обратная польская нотация
Обратную польскую нотацию разработал известный учёный, проводивший исследования в сфере теории вычислительных машин, Чарлз Хэмблин в пятидесятых годах прошлого века. Его нотация базировалась на польской нотации, которую предложил ещё в 1920-м году поляк Ян Лукасевич.
Одной из первых электронных вычислительных машин, которая использовала обратную польскую запись, была KDF9, разработанная English Electric Company. Компания представила эту машину в 1960-ом году. Примерно в то же время появился американский компьютер с обратной польской нотацией Burroughs B5000. Один из разработчиков этой машины Р. С. Бартон, позднее заявил, что сформулировал обратную польскую нотацию при изучении символьной логики без знания работ Хэмблина. Затем фирма Friden использовала принципы обратной польской нотации в настольных калькуляторах, в частности в модели EC-130, поступившей в продажу в 1964-ом году. А уже в 1968-ом году специалисты Hewlett-Packard спроектировали также настольный калькулятор 9100A, который базировался на обратной польской записи. Данная модель калькулятора дала обратной польской нотации широкую популярность в кругу инженерных работников и учёных.
Затем в семидесятые годы прошлого века был разработан программный язык Forth, который в своём составе имел два стека, на которых и выполнялись все вычислительные операции. В данном языке все действия с информационными данными представлялись в форме обратной польской записи. Но при наличии необходимости возможно было использовать и общепринятую форму представления арифметических действий (инфиксную). В 1976-ом году в СССР был выпущен промышленный калькулятор Б3-19М, в котором так же использовалась обратная польская запись.
Как уже указывалось выше, главным отличием обратной польской нотации выступает то обстоятельство, что все операнды располагаются перед символом арифметического действия или операции. В обобщённой форме обратная польская запись представляется так:
- Записать операционный набор следует в виде последовательной цепи операндов и знаков операций. В формуле операнды при письме должны разделяться пробелами.
- Формулу или выражение следует читать слева направо. Если в формуле стоит операционный знак, следует выполнить предписанное им действие над парой стоящих перед ним операндов в очерёдности их представления. Итог действия должен заменить в формуле соответствующие операнды и её знак. Затем вычисление продолжается далее с учётом этого правила.
- Общим результирующим итогом формулы или выражения будет итог последнего произведённого вычисления.
Рассмотрим конкретный пример, требуется найти результат следующего выражения:
13 3 4 • -
В привычной инфиксной записи это выглядит так: 13 – 3 • 4
Первым слева стоит знак умножения (•), поэтому она и выполняется первой, а сомножителями выступают числа три и четыре (они расположены непосредственно перед символом умножения). После выполнения умножения, выражение приобретает следующий вид 13 12 – (число двенадцать является итогом умножения и пишется взамен трёх символов 3 4 •). Видим, что вторым знаком операции является вычитание, что и делается над операндами 13 и 12. Итогом данного действия станет единица, которая и станет результатом всего выражения.
Обратная польская нотация может применяться и при большем числе операндов с соблюдением тех же правил. При применении знаков таких действий при выполнении вычисления формулы или выражения, операция использует соответствующее количество последних перед ней операндов.
Можно выделить такие основные особенности обратной польской нотации:
- Очерёдность осуществления действий непосредственно определяется очерёдностью расположения знаков операций в выражении. Это позволяет исключить применение скобок и приоритетность отдельных действий.
- Здесь не представляется возможным, как в инфиксной нотации, применять одинаковые знаки для унарных и бинарных операционных действий. Например, если при инфиксном представлении выражения 5 • (−3 + 8) символ – (минус) применяется как обозначение унарного действия (меняется на отрицательный знак числа), а здесь (10 – 15) • 3. Этот же минус используется для указания на бинарную операцию вычитания. То есть, назначение действия решает позиция местоположения знака. В обратной польской нотации такие вариации не допустимы.
- Обратная польская нотация позволяет записать выражение в более короткой форме, чем при инфиксной нотации, так как не нужно ставить скобки.
