RPN: алгоритм, әдістері мен мысалдар

RPN рет әлемде компьютерлік бағдарламашы негіз қалыптасты. Бүгін, бұл соншалықты жақсы белгілі емес. Сондықтан, тыс «кері» поляк шұжық орамды бейнеленген комикс мульфильм, әлі күнге дейін кейбір хабардар бағдарламашылары дұрыс түсінбеген болады. өте жақсы әзіл түсіндіру, бірақ бұл жағдайда ол толық қақылы болады емес.

infix

Барлық бағдарламашылар, және ең студенттер операторларының пайдалану таныс. Мысалы, айнымалылар х және у үшін өрнек х + суммациясы құндылықтар плюс белгісін пайдаланылады. Аз-ақ белгілі, бұл infix нотация деп аталатын математика белгілерді, алынған фактісі, шын мәнінде, машиналар үшін үлкен проблема болып табылады. Кіріс екі маңызы сол және оң жағында жазылады Бұл оператор алады. бағдарламалау нотации белгілері операциялармен қосымша пайдалануға. Мысалы, х + у компилятор және ақыр соңында infix белгілерді түрлендіреді онда есеге функциясы (х, у), сондай-ақ жазуға болады. Алайда, әркім математика әрбір дерлік бағдарламалау тілінде ішкі мини-тілі түрін қалыптастыру арифметикалық өрнектерді пайдалануға емес тым жақсы біледі.

формуласы аудармашы

Бірінші шынымен сәтті Fortran бағдарламалау тілі арифметикалық өрнек, өйткені, сондықтан, негізінен айналды (яғни формула ..) Бұл оның атауы, демек, коды (таратылымын) түрлендіріледі - Формула аударма. Бұған дейін, олар, мысалы, функциялары түрінде бүктелген (және (В, С) көбейту), жазуға тура келді. бағдарламашылар С B Mutliply үшін А қосу сияқты нәрселерді жазуға тура келді, өйткені COBOL автоматты түрлендіру формуланы жүзеге асыру мәселесі өте қиын болып саналған

Қандай infix дұрыс болып табылады?

Мәселе операторлары Басымдылықтар және қауымдастық сияқты қасиеттері бар, яғни. Осыған байланысты, infix функцияның анықтамасы емес тривиальная міндет болып. Мысалы, көбейту, ол солдан оңға қарай операторларының орындау болар еді ретінде өрнек 2 + * 4 3, 4 көбейтілген 2 және 3 сомасына, тең емес екенін білдіреді, ол қосу немесе есептеу қарағанда жоғары басымдыққа ие. Шын мәнінде, 4 3 көбейту және 2. Қосу Бұл мысал infix білдіру есептеу жиі операторлары мен операндтар мақсатында өзгертуді талап екенін көрсетеді. Сонымен қатар, ол неғұрлым айқын белгілерді қарап жақша пайдалану қажет. 2 + 3 * 4 + 5 4 3 көбейту және 2 және 5 қосу керек екенін білдіреді, өйткені. Мысалы, (2 + 3) * (4 + 5), жақшасыз жазылған мүмкін емес

Сіз операторларды есептеу келетін тәртібі ұзақ есте талап етеді. Осыған байланысты, арифметика білу үшін бастау студенттер, жиі нақты операциялар дұрыс орындалады, тіпті егер дұрыс нәтиже алу. Ол жатқа іс-қимыл есептілігін тәртібін үйрету қажет. Біріншіден, іс-шаралар көбейту және бөлу, содан кейін жақшада жүзеге асырылады, және, ақырында, қосу және азайту керек. infix Нотация ғана тағы бір қосуға болады ықтимал «шағын тілдері» Бірақ математикалық өрнектерді жазу тағы бір жолы бар.

Префикс және Postfix нотации

Ең танымал балама екі оның операндтар дейін немесе кейін оператор жазуға болады. Олар префикс және Постфиксный белгілерді ретінде белгілі. Логиком Ян Lukasevich 1920 жылы бірінші ойлап. Ол Польша өмір сүрген, сондықтан жазба поляк деп аталады. Кері поляк нотации (АРФ) деп аталатын тиісінше Postfix нұсқасы,. ол егжей-тегжейлі Олардың бір ғана қарауға жеткілікті, сондықтан осы екі әдістерін арасындағы жалғыз айырмашылық, (солдан оңға немесе оңнан солға қарай) жазба оқып үшін бағыт болып табылады. ОПН оператор өз операндтар кейін жазылған. Осылайша, өрнек AB + A + В үлгі RPN білдіреді

операндтар шектелмеген саны

белгілер дереу артықшылығы N-адического операторы және infix нотация шынымен тек екі операндтар, т жұмыс істейді болып қорытындылайды табылады. E. тек екілік операциялар үшін мәні бойынша жарамды. Мысалы, ABC @ оператор үш операнд өзі сол бойынша әрекет етеді және функциясы қоңырау @ (A, B, C) сәйкес келеді, бұл жағдайда А, В және С максималды мәні болып табылады трехчастной белгісін пайдалану кері поляк білдіру болып табылады. Егер сіз осындай @ б.э.д. немесе осы тәрізді нәрсе ретінде, infix ретінде @ символы жазып көріңіз болса, ол жай ғана жұмыс істемейді, бұл анық.

бұйрығымен берілді басым

RPN операторларының басым олардың пайда бұйрығымен ұсынылуы мүмкін тағы бір артықшылығы бар. олар infix белгілерді айырбастауды жеңілдету үшін таңбалар операциялар ретінде енгізілуі мүмкін, бірақ сол уақытта, жақша қажет ешқашан. Мысалы, AB + C * - біржақты балама (A + B) * C, сондықтан көбейту көбейту үшін екінші операнд беретін, орындалатын Сонымен дейін есептелген мүмкін емес. > (AB +) * C - -> (A + B) * C. Яғни бір уақытта бір оператор есептік AB + C * егер, болып табылады, біз AB + 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) есептеу аяқталды, нәтиже дестесін жоғарғы сақталады.

қарамастан, қалай күрделі арифметикалық өрнек, Бұл алгоритм бірнеше рет режиміне RPN тексеруге болады, бірақ әр уақытта ол жұмыс істейтін болады.

ОПН және стеки тығыз байланысты. Бұл мысал кері поляк белгілерді мәнін есептеу үшін жадты пайдалану жолын көрсетеді. Кем айқын сіз ЖБЖ стандартты infix өрнек айырбастау, стек пайдалануға болады.

Бағдарламалау тілдерін мысалдары

Паскаль RPN осы (бағдарламаның бір бөлігін көрсетеді) сияқты түсіндім.

таңбалауышы саны немесе белгісі пайдалануға анықтайды цикл деп аталатын тәртіппен, сандарды және операторларды оқу үшін. Бірінші жағдайда, мән дестесін сақталады, және әрекет тиісті екі жоғарғы стек Сандардың екінші жүзеге асырылады және нәтиже сақталады.

toktype: = NUM;

оқу (лар);

C Егер [ '+', '-', '*', '/'], содан кейін басталады

eoln егер содан кейін CN: = '' басқа (CN) оқып;

Содан кейін «CN = 'болса

А жағдайда

'+': Toktype: = қосу; '-': toktype: = кіші;

'*': Toktype: = мул; '/': Toktype: = DIV

соңы

басқа басталады

егер а = '-', содан кейін SGN: = -1 басқа қате: = C <> '+';

бар: = CN

соңы

соңы;

(Жоқ қате) егер және (toktype = NUM), содан кейін getnumber;

toktype <> шт, содан кейін басталады, егер

у = поп; X: = поп;

онда қате жоқ болса

туралы toktype жағдайда

қосу: Z: = х + у; тармақшасында: Z: = х-у; мул: Z: = X * Y; DIV: Z: = х / у

соңы

басу (Z);

C-іске асыру RPN (бағдарламаның көрсетілген бөлігі):

{(S = функциясын (0,) W S = функциясын (с, W); с) үшін

а = strtod (с, & е);

егер (е> S) басу (а);

#define rpnop (х) printf ( «% C:», * с), B = поп (), а = поп (), басу (х)

басқа (* S == '+') rpnop (А + В) болса;

басқа (* S == '-') егер rpnop (а - б);

басқа, егер (* S == '*') rpnop (A * B);

басқа rpnop (A / B) (* S == '/') болса;

#undef rpnop

}

аппараттық іске асыру

компьютерлік технологиялар өте қымбат болған кезде сол күндері, ол асқын пайдалануға адамдарды мәжбүр үшін жақсы идея ойладым. 1960-шы жылдары., Қазір ретінде, ол кері поляк нотации жұмыс калькуляторды, сатып алу мүмкін болды. Олардың 2 және 3 қосу үшін, содан кейін 3, 2 енгізіңіз де, «плюс» түймесін басу керек. Бір қарағанда, оператор үшін кіріс операндтар есте күрделі және қиын болып көрінген, бірақ біраз уақыттан кейін кейбір ойлау осы жолда тәуелді болып табылады және басқа да соншалықты күрделі болып табылады және сондықтан шектелген ақымақ infix, талап неге түсіне алмады.

Burroughs компаниясы тіпті бумасының қоспағанда, басқа ешқандай жад болған ЭЕМ-ге, салынған. машинаны құрайды жалғыз нәрсе - орталық стек алгоритмдері мен әдістері RPN қолданылады. оның қызметінің барлық жоғарғы N құндылықтарды қолданылады шектеулеріне операторлар, ретінде қарастырылды. Мысалы, мұндай машинаның сәулет қарапайым болды, бірақ емес тез жеткілікті көп таралған сәулет бәсекеге, команда дестесін жоғарғы жағынан кері мекен-жайы алды, және тағы басқалар. D.. Көптеген, алайда, әлі де әр бағдарлама ОПН білдіру болды, онда есептеу үшін осындай қарапайым және әсем тәсіл осы фактіні өкінішпен, өз жалғасын тапты.

RPN Бір рет калькуляторлар танымал болды, және кейбір адамдар әлі күнге дейін оларға артықшылық береді. Сонымен қатар, олар, мысалы, Төртінші ретінде стек бағдарланған тілдерді, дамыған. Бүгінде бұл аз пайдаланылады, бірақ оның бұрынғы пайдаланушылардың әлі ностальгический.

Сондықтан Кері поляк шұжық туралы мағынасы әзіл қандай?

біз шұжық деп операторы, infix белгілер болжауға болса, онда ол кәдімгі ыстық ит сияқты ролл шегінде болуы тиіс. RPN оң екі таймнан есептеу кейін дайын Санағыш алу орналасқан. қыша - Енді қиын бөлігі келеді. Ол, шұжық туралы қазірдің өзінде унарный оператор ретінде есептеледі т. Е. болып табылады. Бұл тым үлкен дестесін талап етеді, қыша, сондай-ақ ретінде непосчитанных көрсетілуі тиіс деп саналады, сондықтан шұжық оңға жылжыту керек ... Бірақ бұл мүмкін ...