Зваротная польская запіс: алгарытм, метады і прыклады

Зваротная польская запіс некалі складала аснову свету камп'ютэрнага праграміста. Сёння яна ўжо не так добра вядомая. Таму жартоўная ілюстрацыя, якая паказвае «зваротную» польскую каўбасу за межамі булачкі, усё яшчэ можа апынуцца незразуметым некаторымі добра дасведчанымі праграмістамі. Не вельмі добра тлумачыць жарт, але ў дадзеным выпадку гэта будзе ў поўнай меры апраўдана.

Инфиксная запіс

Усе праграмісты і большасць школьнікаў знаёмыя з выкарыстаннем аператараў. Напрыклад, у выразе х + у для падсумоўвання значэнняў зменных х і ў выкарыстаны знак складання. Менш вядома тое, што гэта запазычанае з матэматыкі абазначэнне, званае инфиксной натацыяй, на самай справе ўяўляе вялікую праблему для машын. Такі аператар прымае ў якасці ўваходных два значэння, запісаныя злева і справа ад яго. У праграмаванні выкарыстоўваць натацыю са знакамі аперацый неабавязкова. Напрыклад, х + у можна запісаць у выглядзе функцыі скласці (х, у), у якую кампілятар ў рэшце рэшт і пераўтворыць инфиксную натацыю. Аднак усе ведаюць матэматыку занадта добра, каб не выкарыстоўваць арыфметычныя выразы, якія ўтвараюць свайго роду ўнутраны міні-мова амаль у кожнай мове праграмавання.

транслятары формул

Першы сапраўды паспяховы мова праграмавання Fortran стаў такім у асноўным таму, што арыфметычныя выразы (т. Е. Формулы) у ім ператваралася (трансляваліся) у код, адкуль і адбылося яго назва - FORmula TRANslation. Да гэтага іх даводзілася запісваць, напрыклад, у выглядзе функцый скласці (а, памножыць (b, c)). У Коболе праблема рэалізацыі аўтаматычнага пераўтварэння формул лічылася вельмі цяжкай, паколькі праграмістам даводзілася пісаць такія рэчы, як Add A To B Mutliply By C.

Што не так з инфиксом?

Праблема заключаецца ў тым, што аператары валодаюць такімі ўласцівасцямі, як прыярытэт і асацыятыўнасць. З-за гэтага вызначэнне функцыі инфикса становіцца нетрывіяльнай задачай. Напрыклад, прыярытэт множання вышэй, чым складання або аднімання, і гэта азначае, што выраз 2 + 3 * 4 не роўна суме 2 і 3, памножанай на 4, як гэта б было пры выкананні аператараў злева направа. На самай справе варта памножыць 3 на 4 і дадаць 2. Гэты прыклад ілюструе, што вылічэнне инфиксного выразы часта патрабуе змянення парадку аператараў і іх аперанд. Акрамя таго, даводзіцца выкарыстоўваць дужкі, каб натацыя выглядала больш ясна. Напрыклад, (2 + 3) * (4 + 5) нельга запісаць без дужак, таму што 2 + 3 * 4 + 5 азначае, што неабходна памножыць 3 на 4 і дадаць 2 і 5.

Парадак, у якім неабходна вылічаць аператары, патрабуе доўгага запамінання. З-за гэтага школьнікі, пачаткоўцы вывучаць арыфметыку, часта атрымліваюць няправільныя вынікі, нават калі фактычна аперацыі выконваюцца правільна. Неабходна вучыць парадак дзеяння аператараў на памяць. Спярша павінны выконвацца дзеянні ў дужках, затым множанне і дзяленне і, нарэшце, складанне і адніманне. Але ёсць і іншыя спосабы запісу матэматычных выразаў, паколькі инфиксная натацыя з'яўляецца ўсяго толькі адным з магчымых «малых моў», якія можна дадаць да большага.

Прэфіксны і постфиксная натацыя

Двума найбольш вядомымі альтэрнатыўнымі варыянтамі з'яўляецца запіс аператара да або пасля яго аперанд. Яны вядомыя як прэфіксны і постфиксная натацыі. Логік Ян Лукасевич прыдумаў першую з іх у 1920-я гады. Ён жыў у Польшчы, таму запіс называюць польскай. Постфиксный варыянт, адпаведна, атрымаў назву зваротнай польскай натацыі (ОПН). Адзіная розніца паміж гэтымі двума метадамі складаецца ў напрамку, у якім варта чытаць запіс (злева направа ці справа налева), таму досыць падрабязна разгледзець толькі адзін з іх. У ОПН аператар запісваецца пасля яго аперанд. Так, выраз АВ + ўяўляе сабой прыклад зваротнай польскай запісы для A + B.

Неабмежаваны лік аперанд

Непасрэдным перавагай натацыі з'яўляецца тое, што яна абагульняецца n-адическим аператарам, а инфиксная натацыя на самай справе працуе толькі з двума аперанда, т. Е. Па сваёй прыродзе падыходзіць толькі для бінарных аперацый. Так, напрыклад, ABC @ з'яўляецца зваротным польскім выразам з выкарыстаннем триадического знака, які знаходзіць максімальнае значэнне з A, B і C. У гэтым выпадку аператар дзейнічае на 3 аперанда злева ад сябе і адпавядае выкліку функцыі @ (A, У, З). Калі паспрабаваць запісаць сімвал @ в якасці инфиксного, напрыклад A @ BC ці нешта падобнае, то становіцца зразумела, што гэта папросту не працуе.

Прыярытэт задаецца парадкам

Зваротная польская запіс мае яшчэ адна перавага ў тым, што прыярытэт аператараў можа быць прадстаўлены парадкам іх з'яўлення. Пры гэтым ніколі не спатрэбяцца дужкі, хоць яны могуць быць уключаны ў якасці знакаў аперацый, каб палегчыць канвертацыю з инфиксной натацыяй. Напрыклад, АВ + С * - адназначны эквівалент (А + У) * З, так як множанне не можа быць вылічана, пакуль не будзе выканана складанне, якое дае другі аперанд для аперацыі множання. То бок, калі вылічаецца AB + C * па адным аператару за раз, то атрымаецца AB + C * -> (AB +) * C -> (A + B) * C.

алгарытм вылічэнні

У ОПН аператар выглядае гэтак жа, як функцыя, якая прымае ў якасці аргументаў два значэння, запісаныя злева ад яе. Акрамя таго, гэта натуральная натацыя для выкарыстання ў мовах праграмавання, паколькі ход яе вылічэнняў адпавядае стековых аперацыях і неабходнасць у сінтаксічным аналізе адпадае. Напрыклад, у ОПН выраз 5 + 6 * 7 будзе выглядаць як 5, 6, 7 *, +, і яно можа быць вылічана проста шляхам сканавання злева направа і запісы значэнняў у стэк. Кожны раз, калі сустракаецца знак аперацыі, выбіраюцца 2 верхніх элемента з машыннай памяці, прымяняецца аператар і вынік вяртаецца ў памяць. Пры дасягненні канца выразы вынік вылічэнняў апынецца ў вяршыні стэка.

напрыклад:

• S = () 5, 6, 7, *, + змясціць 5 у стэк.
• S = (5) 6, 7, *, + змясціць 6 у стэк.
• S = (5, 6) 7, *, + змясціць 7 у стэк.
• S = (5, 6, 7) *, + выбраць 2 значэння з стэка, прымяніць * і змясціць вынік у стэк.
• S = (5, 6 * 7) = (5, 42) + выбраць 2 значэння з стэка, прымяніць + і змясціць вынік у стэк.
• S = (5 + 42) = (47) вылічэнне завершана, вынік знаходзіцца ў вяршыні стэка.

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

ОПН і стэкі цесна звязаныя паміж сабой. Прыведзены прыклад наглядна дэманструе, як можна выкарыстоўваць памяць, каб вылічыць значэнне ў зваротнай польскай натацыі. Менш відавочна, што можна выкарыстоўваць стэк, пераўтварыўшы стандартныя инфиксные выразы ў ОПН.

Прыклады на мовах праграмавання

На мове Паскаль зваротная польская запіс рэалізуецца прыкладна так (прыведзена частка праграмы).

Для счытвання лікаў і аператараў у цыкле выклікаецца працэдура, якая вызначае, ці з'яўляецца токен лікам або знакам аперацыі. У першым выпадку значэнне запісваецца ў стэк, а ў другім над двума верхнімі лікамі стэка выконваецца адпаведныя дзеянне і вынік захоўваецца.

toktype: = num;

read (с);

if з in [ '+', '-', '*', '/'] then begin

if eoln then cn: = '' else read (cn);

if cn = '' then

case з of

'+': Toktype: = add; '-': toktype: = sub;

'*': Toktype: = mul; '/': Toktype: = div

end

else begin

if з = '-' then sgn: = -1 else error: = с <> '+';

з: = cn

end

end;

if (not error) and (toktype = num) then getnumber;

if toktype <> num then begin

у: = Рор; х: = Рор;

if not error then

case toktype of

add: z: = х + у; sub: z: = х-у; mul: z: = х * У; div: z: = х / у

end

push (z);

C-рэалізацыя зваротнай польскай запісу (прыведзены частка праграмы):

for (s = strtok (s, w); s; s = strtok (0, w)) {

a = strtod (s, & e);

if (e> s) push (a);

#define rpnop (x) printf ( "% з:", * s), b = pop (), a = pop (), push (x)

else if (* s == '+') rpnop (a + b);

else if (* s == '-') rpnop (a - b);

else if (* s == '*') rpnop (a * b);

else if (* s == '/') rpnop (a / b);

#undef rpnop

}

апаратныя рэалізацыі

У тыя часы, калі вылічальная тэхніка каштавала вельмі дорага, лічылася добрай ідэяй прымушаць людзей карыстацца ОПН. У 1960-х гг., Як і сёння, можна было купіць калькулятары, якія працуюць у зваротнай польскай запісу. Для складання 2 і 3 у іх неабходна ўвесці 2, затым 3 і націснуць кнопку "плюс". На першы погляд, увод аперанд да аператара здаваўся складаным і цяжка запамінальным, але праз некаторы час некаторыя заахвоціліся да такога ладу мыслення і не маглі зразумець, чаму астатнія настойваюць на дурной инфиксной запісу, якая так складаная і так абмежаваная.

Кампанія Burroughs нават пабудавала мэйнфрэйм, у якога не было ніякай іншай аператыўнай памяці, акрамя стэка. Адзінае, што рабіла машына, - ўжывала алгарытмы і метады зваротнай польскай запісу да цэнтральнага стэку. Ўсе яе аперацыі расцэньваліся як аператары ОПН, дзеянне якіх распаўсюджвалася на n верхніх значэнняў. Напрыклад, каманда Return брала адрас з вяршыні стэка і т. Д. Архітэктура такой машыны была простай, але недастаткова хуткай, каб канкурыраваць з больш агульнымі архітэктурамі. Многія, аднак, да гэтага часу шкадуюць аб тым, што такі просты і элегантны падыход да вылічэннях, дзе кожная праграма была выразам ОПН, не знайшоў свайго працягу.

Адзін час калькулятары з зваротнай польскай запісам карысталіся папулярнасцю, і некаторыя да гэтага часу аддаюць ім перавагу. Акрамя таго, былі распрацаваны стэк-арыентаваныя мовы, такія як Forth. Сёння ён мала выкарыстоўваецца, але да гэтага часу выклікае настальгію з боку былых яго карыстальнікаў.

Так у чым сэнс жарты аб зваротнай польскай сасіскі?

Калі лічыць сасіску аператарам, то ў инфиксной натацыі яна павінна знаходзіцца ўнутры булкі, як у звычайным хот-доге. У зваротнай польскай запісы яна знаходзіцца правей двух паловак, гатовая патрапіць паміж імі пасля вылічэнні. Цяпер пачынаецца самая цяжкая частка - гарчыца. Яна ўжо знаходзіцца на сасіскі, т. Е. Ужо вылічаная як унарный аператар. Існуе меркаванне, што гарчыца таксама павінна быць паказана як невычисленная і, такім чынам, павінна быць перамешчаны направа ад сасіскі ... Але магчыма, для гэтага спатрэбіцца занадта вялікі стэк ...