Обратният полски запис някога е бил в основата на света на компютърния програмист. Днес тя не е толкова добре позната. Ето защо хумористичната илюстрация, изобразяваща обратната страна на полската наденица извън кифлите, все още може да бъде непонятна за някои известни програмисти. Не е добро обяснение за шега, но в този случай тя ще бъде напълно оправдана.
Infix Record
Всички програмисти и повечето студенти са запознати с използването на операторите. Например, в израза x + за добавяне на стойностите на променливите x и y, се използва символът за добавяне. По-малко известно е, че знакът, заимстван от математиката, наречен инфиксна нотация, всъщност е основен проблем за машините. Такъв оператор приема като вход две стойности, записани вляво и вдясно от него. При програмирането използването на символи с операционни знаци е по избор. Например, x + y може да бъде записано като функция от компилация (x, y), в която компилаторът в крайна сметка трансформира инфиксната нотация. Все пак, всеки знае, че математиката е твърде добре, за да не използва аритметични изрази, които формират един вид вътрешен мини-език в почти всеки език за програмиране.
Преводачи на формула
Първият истински успешен програмен език за Fortran стана толкова до голяма степен, защото аритметичните изрази (т.е. формулите) бяха трансформирани в него (преведени) в код, откъдето идва името му - FORmula TRANslation. Преди това трябваше да записват, напримерпод формата на функции съставляват (а, умножете (б, в)). В Кобол проблемът за внедряването на автоматична трансформация на формула се счита за много труден, тъй като програмистите трябваше да напишат неща като 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.
Редът, в който е необходимо да се изчислят операторите, изисква дълго запаметяване. Поради това учениците, начинаещи изучават аритметика, често получават неправилни резултати, дори ако действителните операции се изпълняват правилно. Необходимо е да се научи процедурата на операторите наизуст. Първо, трябва да се извършат действия в скоби, след това умножение и деление и накрая добавяне и изваждане. Но има и други начини за писане на математически изрази, тъй като инфиксната нотация е само един от възможните "малки езици", които могат да бъдат добавени към по-голямото.
Префикс и постфикс
Два от най-известните алтернативни варианти са записа на оператора преди или след неговите операнди. Те са известни като префикс и постфикс нотации. Логиката Jan Lukasiewicz излезе с първата от тях през 1920-те. Той е живял в Полша, така че записът се нарича полски. Постфиксният вариант, съответно, получи името на обратната полска нотация (OPN). Единствената разлика между тези два метода е в посоката, в която трябва да прочетете записа (от ляво на дясно или от дясно на ляво), така че просто разгледайте един от тях в подробности. В OPN операторът се записва след неговите операнди. Така че, изразът AB + е пример за обратен полски запис за A + B.
Неограничен брой операнди
Прякото предимство на нотацията е, че то се обобщава от n-адичен оператор, а инфиксната нотация всъщност работи само с два операнда, т.е. Например, ABC @ е обратен полски израз, използващ триадичен символ, който намира максималната стойност A, B и C. В този случай операторът оперира върху 3 операнда вляво от себе си и отговаря на повикването на функция @ (A, B, C). Ако се опитате да напишете символ "@" като инфикс, като A @ BC или нещо подобно, тогава става ясно, че просто не работи.
Приоритет се дава със заповед
В обратния полски запис има и друго предимство, че приоритетът на операторите може да бъде представен по реда на тяхното възникване. В този случай скобите никога няма да бъдат необходими, въпреки че те могат да бъдат включени като признаци за улесняване на операциитепреобразуване с инфикс нотация. Например, AB + C * е уникален еквивалент (A + B) * C, тъй като умножението не може да бъде изчислено, докато не се извърши добавянето на втория операнд за операцията по умножение. Тоест, ако AB + C * се изчислява от един оператор в даден момент, тогава A B + C * - & gt; (A B +) * C - & gt; (A + B) * C.
Алгоритъм за изчисление
В OPC операторът изглежда същото като функция, която приема като два аргумента стойностите, записани вляво от него. В допълнение, това е естествена нотация за използване в езиците за програмиране, тъй като хода на неговите изчисления съответства на операции на стека и нуждата от парсване не съществува. Например, в OPC, изразът 5 + 6 * 7 ще изглежда като 567 *, +, и може да се изчисли просто чрез сканиране от ляво на дясно и записване на стойности в стека. При всяко откриване на транзакция се избират два горни елемента от паметта на машината, използва се операторът и резултатът се връща в паметта. Когато достигнете края на израза, резултатът от изчисленията ще се появи в горната част на стека. Например:
S = () 567 *, + постави 5 в стека.
S = 6 7 *, + постави 6 в стека.
S = (5 6) 7 *, + постави 7 в стека.
S = (567) *, + изберете 2 стойности от стека, приложите * и поставете резултата в стек.
S = (5 6 * 7) = (542) + изберете 2 стойности от стека, приложите + и поставете резултата в стека.
S = (5 + 42) = (47) Изчислението е завършено, резултатът е в горната част на стека.
Този алгоритъм може да бъде проверен многократно, но всеки път, когато той работи, независимо от това колкоаритметичният израз е сложен. OPN и стекове са тясно свързани помежду си. Примерът по-долу илюстрира как паметта може да се използва за изчисляване на стойността на обратната полска нотация. По-малко очевидно е, че можете да използвате стека, трансформирайки стандартните инфикс изрази в TNF.
Примери на езици за програмиране
В езика Pascal, обратният полски запис се прилага приблизително (показана част от програмата). Четенето на числа и оператори в цикъл се нарича процедура, която определя дали даден знак е номер или знак на операцията. В първия случай стойността се записва в стека, а във втората над двете горни числа на стека, съответното действие се изпълнява и резултатът се записва. toktype: = num; да се чете в); ако в ['+', '-', '*', '/'] след това започнете, ако eoln след това cn: = 'else else (cn); ако cn = '' тогава случай от '+': toktype: = add; '-': toktype: = sub; '*': toktype: = мен; '/': toktype: = div последното друго започва, ако c = '-' след това sgn: = -1 иначе грешка: = с & lt; & gt; "+"; c: = cn краен край; if (не грешка) и (toktype = num) след това getnumber; ако въведете & lt; & gt; num започва: = ro; x: = ro; ако няма грешка тогава случай, toktype на add: z: = x + y; sub: z: = x-y; me: z: = x * y; div: z: = x /y краен бутон (z); С-реализация на обратния полски запис (част от програмата е дадена): за (s = strtok (s, w); s; s = strtok (0 w)) {a = strtod (s & e); ако (е> s) натиснете (а); #define rpnop (x) printf ("% c:", * s), b = (pop), a = (pop), натиснете (x) друго, ако (* s == '+') rpnop (a + b) ) иначе, ако (* s == '-') rpnop (a - b); иначе, ако (* s == '*') rpnop (a * b); иначе, ако (* s == '/') rpnop (a /b); #undef rpnop}
Хардуерна реализация
В онези времена, когато компютърните технологии бяха много скъпи, се смяташе за добра идея да принудят хората да използват OPN. През 60-те години на миналия век, както и днес, е било възможно да се закупят калкулатори, които работят обратноПолски рекорд. За да добавите 2 и 3, трябва да въведете 2 и 3 и да кликнете върху бутона плюс. На пръв поглед въвеждането на операнди на оператора изглеждаше трудно и трудно за запомняне, но след известно време някои от тях бяха пристрастени към този начин на мислене и не можеха да разберат защо другите настояват за глупав запис, който е толкова сложен и толкова ограничен. Burroughs дори изгради мейнфрейм, който нямаше никаква друга RAM освен стека. Единственото нещо, което колата направи - използваше алгоритми и методи за обратно фокусиране в централния стек. Всички нейни операции се разглеждат като оператори на OPN, чиито действия се разпростират до n горни стойности. Например, командата Return е взела адрес от горната част на стека и т.н. Архитектурата на такава машина е проста, но не достатъчно бърза, за да се конкурира с по-общите архитектури. Мнозина обаче все още съжаляват, че такъв прост и елегантен подход към компютрите, където всяка програма е израз на NPN, не намира своето продължение. Един път калкулаторите с обратния полски рекорд се радват на популярност, а някои все още им дават предимство. Освен това са разработени езици, ориентирани към стека като Forth. Днес тя е малко използвана, но все още причинява носталгия от предишните си потребители.
И така, какъв е смисълът да се шегуваме за обратния полски колбас?
Ако се вземе предвид оператор на колбас, тогава в инфиксната нотация той трябва да е вътре в хляба, както при обичайните хот-доги. В обратния полски запис е надяснодве половини, е готов да стигне между тях след изчислението. Сега започва най-трудната част - горчица. Тя вече е на колбас, която вече е изчислена като единствен оператор. Смята се, че горчицата също трябва да бъде показана като необработена и следователно трябва да бъде преместена вдясно от наденицата.
