Адваротная польская натацыя

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

Стэкавай машынай завецца алгарытм, які праводзіць вылічэнні па зваротнай польскай натацыі (гл. ніжэй прыклад вылічэння выразаў).

Гісторыя

Зваротная польская натацыя была распрацавана аўстралійскім філосафам і спецыялістам у галіне тэорыі вылічальных машын Чарльзам Хэмблінам у сярэдзіне 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 з падтрымкай АПН стаў першым навуковым кішэнным калькулятарам.

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

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

Вызначэнне

Каб даць індуктыўнае вызначэнне постфікснай натацыі, пазначым выраз у інфікснай натацыі $E$, $E_1$, $E_2$, эквівалентныя ім выразы з постфікснай натацыі $\dot E$ , $\dot E_1$, $\dot E_2$ адпаведна; $o$ — адвольны бінарны аператар, тады:

1. Калі $E$ — зменная ці канстанта, то $\dot E$ ёсць $E$.

2. Калі $E$ — выраз віду $E_1 o E_2$, то $\dot E$ ёсць $\dot E_1 \dot E_2 o$.

3. Калі $E$ — выраз віду $(E_1)$, то $\dot E$ ёсць $\dot E_1$.

Апісанне

Адметнай асаблівасцю зваротнай польскай натацыі з'яўляецца тое, што ўсе аргументы (ці аперанды) размеркаваны перад знакам аперацыі. У агульным выглядзе запіс выглядае наступным чынам:

• Запіс набору аперацый складаецца з паслядоўнасці аперандаў і знакаў аперацый. Аперанды ў выразе пры пісьмовым запісе падзяляюцца прабеламі.
• Выраз чытаецца злева направа. Калі ў выразе сустракаецца знак аперацыі, выконваецца адпаведная аперацыя над двума апошнімі сустрэтымі перад ім аперандамі ў чарзе іх запісу. Вынік аперацыі замяняе ў выразе паслядоўнасць яе аперандаў і яе знак, пасля чаго выраз вылічаецца далей па тым жа правіле.
• Вынікам вылічэння выраза становіцца вынік апошняй вырабленай аперацыі.

Напрыклад, разгледзім вылічэнне выраза 7 2 3 * - (эквівалентны выраз у інфікснай натацыі: 7-2*3).

1. Першы знак па чарзе аперацыі — «*», таму першай выконваецца аперацыя множання над аперандамі 2 і 3 (яны стаяць апошнімі перад знакам). Выраз пры гэтым пераўтвараецца да віду 7 6 - (вынік множання — 6, — змяняе тройку «2 3 *»).
2. Другі знак аперацыі — «-». Выконваецца аперацыя аднімання над аперандамі 7 і 6.
3. Вылічэнне скончана. Вынік апошняй аперацыі складае 1, гэта і ёсць вынік вылічэння выраза.

Відавочнае пашырэнне зваротнага польскага запісу на унарныя, тэрнарныя і аперацыі з любой іншай колькасцю аперандаў: пры ужыванні знакаў такіх аперацый у вылічэнні выраза аперацыя выкарыстоўваецца да адпаведнай колькасці апошніх сустрэтых аперандаў.

Асаблівасці зваротнага польскага запісу наступныя:

• Паслядоўнасць выканання аперацый адназначна задаецца чаргой размяшчэння знакаў аперацый у выразе, таму знікае неабходнасць ужывання дужак і ўвядзення прыярытэтаў ды асацыятыўнасці аперацый.
• У адрозненні ат інфікснага запісу, немагчыма ужываць адны і тыя ж знакі дзеля запісу унарных і бінарных аперацый. Так, у інфіксным запісе выраз 5 * (-3 + 8) выкарыстоўвае знак «мінус» як сімвал унарнай аперацыі (змена знака лічбы), а выраз (10 - 15) * 3 выкарыстоўвае гэты ж знак дзеля пазначэння бінарнай аперацыі (адніманне). Пэўная аперацыя вызначаецца тым, у якой пазіцыі знаходзіцца знак. Адваротны польскі запіс не дазваляе гэтага: запіс 5 3 - 8 + * (умоўны аналаг першага выраза) будзе інтэрпрэтаваны як памылковы, бо немагчыма вызначыць, што «мінус» пасля 5 і 3 пазначае не адніманне; у выніку будзе зроблена спроба вылічыць спачатку 5 - 3, потым 2 + 8, пасля чаго высветліцца, што для аперацыі множання не хапае аперандаў. Каб усё ж запісаць гэты выраз, прыйдзецца ці перафармуляваць яго, альбо увесці для аперацыі змены знака асобнае абазначэнне, напрыклад, «±»: 5 3 ± 8 + *.
• Таксама, як і ў інфікснай натацыі, у АПН адно і тое ж вылічэнне можа быць запісана у некалькіх розных варыянтах. Напрыклад, выраз (10 - 15) * 3 у АПН можна запісаць як 10 15 - 3 *, а можна — як 3 10 15 - *
• З-за адсутнасці дужак адваротны польскі запіс карацей за інфіксны. За гэты конт пры вылічэннях на калькулятарах павялічваецца хуткасць работы аператара (змяншаецца колькасць націскаемых клавіш), а ў праграмуемых прыладах скарачаецца аб'ём тых частак праграмы, якія апісваюць вылічэнні. Апошняе можа быць немалаважна для партатыўных і інтэграваных вылічальных прылад, якія маюць жорсткія абмежаванні на аб'ём памяці.

Вылічэнні на стэке

Агульны парадак

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

1. Апрацоўка уваходнага сімвала
   • Калі на уваход пададзены аперанд, ён змяшчаецца на вяршыню стэка.
   • Калі на уваход пададзены знак аперацыі, то адпаведная аперацыя выконваецца над патрабуемай колькасцю значэнняў, вынятых з стэка, узятых у чарзе дадання. Вынік выкананай аперацыі змяшчаецца на вяршыню стэка.
2. Калі уваходны набор сімвалаў апрацаваны не цалкам, перайсці да кроку 1.
3. Пасля поўнай апрацоўкі ўваходнага набору сімвалаў вынік вылічэння выраза змяшчаецца на вяршыні стэка.

Рэалізацыя стэкавай машыны, як праграмная, так і апаратная, надзвычай простая і можа быць вельмі эфектыўнай. Адваротны польскі запіс цалкам уніфікаваны — ён прынцыпова аднолькава запісвае унарныя, бінарныя, тэтрарныя і адвольныя іншыя аперацыі, а таксама зварот да функцый, што дазваляе не ўскладняць канструкцыю вылічальных прылад пры пашырэнні набору падтрымліваемых аперацый. Гэта і сталася прычынай выкарыстання адваротнага польскага запісу ў некаторых навуковых і праграмуемых мікракалькулятарах.

Прыклад вылічэння выразаў

Выраз $(1 + 2) \times 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 |  + 
+----+

Клавіша «Увод» (пазначана на калькулятарах як «Enter» ці сімвалам «↑») выконвае ролю падзельніка аперандаў, калі два аперанды непасрэдна ідуць адзін за адным. Калі за аперандам ідзе знак аперацыі, то яе націсканне не патрабуецца, гэта скарачае колькасць дзеянняў, якія патрэбна выканаць дзеля атрымання выніку.

Пераўтварэнне з інфікснай натацыі

Эдсгер Дэйкстра вынайшаў алгарытм для пераўтварэння выразаў з інфікснай натацыі ў АПН. Алгарытм атрымаў назву «сартавальная станцыя», за падабенства яго аперацый з тым, што адбываецца на чыгуначных сартавальных станцыях. Інфіксная натацыя — гэта форма матэматычных запісаў, якую ужывае большасць людзей (напрыклад, 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

Дадзены метад, відавочна, не ўключае ўсіх магчымых спосабаў аптымізацыі.

Прыклады рэалізацыі

У артыкуле «Зваротны польскі запіс: прыклады рэалізацыі» сабраны прыклады рэалізацыі зваротнага польскага запісу на разнастайных мовах праграмавання.

Літаратура

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

Спасылкі

Мовы праграмавання, якія ужываюць АПН у якасці асноўнай:

• Forth
• Factor
• Postscript
• Мова стыляў афармлення BibTeX

Вонкавыя спасылкі

• Адваротная польская натацыя
• http://www.univer.omsk.ru/students/m84/docs/pol_zap.html
• Міні-лекцыя, прысвечаная ОПН (на англ., з анімацыяй) — Аўтар: Bob Brown
• Рэалізацыя Польскага Інверснага Запісу на PHP
• Пераўтварэнне выраза з інфікснай натацыі ў АПН з дапамогай алгарытма Дэйкстры на C#