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

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

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

Гісторыя

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

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

Прыклады выкарыстання

Прыклад выкарыстання ў мове праграмавання Forth:

3 2 1 + *

Гл. таксама

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

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

Літаратура

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

Спасылкі

• Адваротная польская натацыя (руск.)
• http://www.univer.omsk.ru/students/m84/docs/pol_zap.html Архівавана 4 сакавіка 2016.
• Рэалізацыя адваротнага польскага запісу на PHP Архівавана 19 ліпеня 2012.