RPN: ալգորիթմ, մեթոդներ եւ օրինակներ

RPN մեկ անգամ հիմք է համակարգչային ծրագրավորող է աշխարհում. Այսօր դա ոչ այնքան հայտնի. Հետեւաբար, զավեշտական նկարազարդումը, պատկերող մի «հակառակ» լեհ երշիկ գլանափաթեթներ դուրս, դեռեւս կարող է սխալ հասկացվել որոշ բանիմաց ծրագրավորողների: Ոչ շատ լավ բացատրում է անեկդոտը, բայց այս դեպքում դա կլինի լիովին արդարացված է:

infix

Բոլոր ծրագրավորողների, եւ մեծ մասը ուսանողներ են ծանոթ օգտագործման օպերատորների: Օրինակ, արտահայտությունը x + գումարելու արժեքների համար x եւ y փոփոխականները օգտագործված գումարած նշան: Պակաս հայտնի է այն փաստը, որ դա պարտք է մաթեմատիկական նշում, որը կոչվում է infix նշում, ըստ էության, մի մեծ խնդիր է, որ մեքենաների. Այս օպերատորը ստանում ներմուծած երկու արժեքները հաշվառվում են ձախ եւ աջ. Ծրագրավորման նշում օգտագործվում ընտրովի հետ նշաններ գործողությունների: Օրինակ, x + y կարելի է գրել, որպես ֆունկցիա ապատիկի չափով (x, y), որի Կազմողի եւ, ի վերջո, նորադարձների Infix նշում: Սակայն, բոլորն էլ գիտեն, որ մաթեմատիկան շատ լավ է օգտագործել թվաբանական արտահայտություններ, որոնք կազմում մի տեսակ ներքին մինի-լեզվով գրեթե ամեն ծրագրավորման լեզու.

բանաձեւը թարգմանիչ

Առաջին իսկապես հաջողված Fortran ծրագրավորման լեզու է դարձել, որպեսզի հիմնականում այն պատճառով, որ թվաբանությունը արտահայտությունը (այսինքն բանաձեւ ..) Այն փոխանակվել (եթեր) կոդում, հետեւաբար անունը դրա - Formula թարգմանություն. Մինչ այդ, նրանք ստիպված են գրել, օրինակ, folded է ձեւով գործառույթների (եւ բազմապատկել (բ, գ)): Ի COBOL խնդրի իրականացման Ավտոմատիկա փոխարկման բանաձեւը համարվում էր շատ դժվար է, քանի որ ծրագրավորողների էր գրել, որ նման բաներ Ավելացնել Ա Բ Mutliply `C.

Ինչ վատ բան կա Infix:

Խնդիրն այն է, որ օպերատորները ունեն այնպիսի հատկություններ, ինչպիսիք են հանդիսանում associativity: Այս պատճառով է, որ սահմանումը Infix ֆունկցիայի դառնում ոչ չնչին խնդիր է. Օրինակ, բազմապատկում ունի բարձր գերակա քան Բացի դրանից, կամ հանման, որը նշանակում է, որ արտահայտությունը 2 + 3 * 4 հավասար չէ գումարի 2 եւ 3, բազմապատկած 4, քանի որ դա կլինի կատարման օպերատորների ձախից աջ. Ի դեպ, բազմապատկել 3-ի 4 եւ ավելացնել 2. Այս օրինակը ցույց է տալիս, որ հաշվարկը Infix արտահայտվելու հաճախ պահանջում է փոփոխություն կարգի օպերատորների եւ օպերանդներից. Ի լրումն, դա անհրաժեշտ է օգտագործել braces է նայել ավելի հստակ նշում: Օրինակ, (2 + 3) * (4 + 5) չեն կարող գրվել առանց փակագծերի, քանի որ 2 + 3 * 4 + 5 նշանակում է, որ դուք պետք է բազմապատկել 3-ի 4 եւ ավելացնել 2 եւ 5.

Կարգը, որը դուք ուզում եք հաշվարկել օպերատորների պահանջում է երկար կհիշի: Այս պատճառով, ուսանողները, ովքեր սկսում են սովորել, թվաբանություն, հաճախ սխալ արդյունքները, նույնիսկ եթե փաստացի գործողությունները կատարվում են ճիշտ: Անհրաժեշտ է ուսուցանել կարգը գործողությունների հայտարարություններով անգիր. Նախ, որ ակցիան պետք է իրականացվի փակագծերի, ապա բազմապատկման եւ բաժանման, եւ վերջապես գումարումն ու հանումը: Սակայն կա մեկ այլ միջոց է գրելու մաթեմատիկական արտահայտություններ, ինչպես infix նշում է միայն մեկը, հնարավոր «փոքր լեզուներով», որը կարող է ավելացվել է ավելի.

Բնորոշիչ եւ postfix նշում

Երկու առավել հայտնի այլընտրանքների պետք է արձանագրել, օպերատորին առաջ կամ հետո նրա օպերանդներից: Նրանք հայտնի են որպես նախաբան եւ PostFix նշում. Logician Յան Lukasevich հորինել առաջինն է 1920 թ. Նա ապրում է Լեհաստանում, ուստի ռեկորդային կոչվում լեհական: Postfix տարբերակ, համապատասխանաբար, որը կոչվում է Reverse լեհերենից նշագրմամբ (ՀՅԴ): Միակ տարբերությունն այս երկու եղանակներից է ուղղությունը, որը պետք է կարդալ ռեկորդը (ձախից աջ կամ աջ ձախ), այնպես որ, այն բավականացնում է համարում մանրամասն միայն դրանցից մեկը: Որ opn օպերատորը գրված հետո իր օպերանդներից: Այսպիսով, արտահայտությունը AB + ներկայացնում է օրինակ RPN համար + B.

Անսահմանափակ թվով օպերանդներից

Անմիջական առավելությունն նշում է, որ այն ամփոփում n-Adic օպերատորին եւ infix նշում է, իրոք, աշխատում է միայն երկու օպերանդներից, ք. E. են ժառանգաբար հարմար է միայն երկուական գործողությունների. Օրինակ, ABC @ հակառակ Լեհաստանի արտահայտությունը օգտագործելով triadic նշանն է առավելագույն արժեքը A, B եւ C- ի: Այս դեպքում օպերատորը գործում է ձախ երեք operand բուն եւ համապատասխանում է ֆունկցիա call @ (A, B, C): Եթե դուք փորձեք գրել @ խորհրդանիշը, որպես Infix, ինչպես, օրինակ, Ա @ Ք.ա. կամ նման բան, որ, պարզ է դառնում, որ դա պարզապես չի աշխատում:

Գործում առաջնահերթությունը տրվում է հրամանով

RPN ունի եւս մեկ առավելություն է, որ առաջնայնությունը օպերատորները կարող են ներկայացված լինել կարգով իրենց արտաքինը. Միեւնույն ժամանակ, երբեք պետք braces, թեեւ նրանք կարող են ներառվել, քանի որ կերպարները գործողությունները հեշտացնել դարձի է infix նշում. Օրինակ, AB + C * - աներկբա համարժեք (A + B) * C, այնպես որ բազմապատկում չի կարող հաշվարկվել, քանի դեռ Բացի կատարված, որը տալիս է երկրորդ օպերանդ համար բազմապատկում: Այսինքն, եթե հաշվարկային AB + C * - ի կողմից մեկ օպերատորի է մի ժամանակ, մենք ստանում ենք AB + C * -> (AB +) * C -> (A + B) * C.

հաշվարկման ալգորիթմ

The opn օպերատորը նայում է նույնը, որպես ֆունկցիա, որը վերցնում է որպես փաստարկներ երկու արժեքները գրված իր ձախ կողմում. Ի լրումն, դա բնական նշում օգտագործման համար ծրագրավորման լեզուների, քանի որ եղանակը դրա հաշվարկման համապատասխանում է բուրգ գործառնությունների եւ անհրաժեշտությունը, վերլուծել է վերացվի: Օրինակ, պարպիչ արտահայտության 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 բազմիցս, բայց ամեն անգամ, երբ դա կաշխատի, անկախ նրանից, թե որքան բարդ է թվաբանական արտահայտության:

Opn եւ stacks սերտորեն կապված. Այս օրինակը ցույց է տալիս, թե ինչպես կարելի է օգտագործել հիշողություն հաշվարկել արժեքը հակառակ լեհական նշում: Ավելի ակնհայտ է, որ դուք կարող եք օգտագործել բուրգ, converting ստանդարտ Infix արտահայտությունը սուր երիկամային անբավարարություն:

Օրինակներ ծրագրավորման լեզուների

Pascal RPN հասկացա, նման (ցույց է տալիս մասը ծրագրի):

Է կարդալ համարները եւ օպերատորների ցիկլի կոչվող կարգը, որը սահմանում է, թե արդյոք բառանիշի համարը, կամ ժեստերի շահագործման. Առաջին դեպքում, արժեքը պահվում է գրապահոց, իսկ երկրորդը, որ երկու վերին բուրգ համարները համապատասխան գործողությունների կատարվում է եւ արդյունքը պահվում:

toktype: = num;

կարդալ (ներ);

եթե գ [ '+', '', '*', '/'], ապա սկսում

եթե eoln ապա CN = '' ուրիշ կարդալ (CN);

եթե CN = '', ապա

դեպքը մի

+ ': Toktype: = Ավելացնել; '': Toktype: = ենթակետի;

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

վերջ

ուրիշ սկսում

եթե = '-', ապա sgn: = -1 ուրիշ սխալ: = c <> '+';

հետ: = CN

վերջ

վերջ;

եթե (ոչ սխալ) եւ (toktype = NUM), ապա getnumber.

եթե toktype <> num ապա սկսում

y = փոփ. x: = փոփ.

եթե ոչ սխալ, ապա

դեպքը toktype Հյուրատետր

ավելացնել: z = x + y. ենթակետի: z: = x-y. MUL: z = x * y. div: z = x / y

վերջ

հրում (z);

C-իրականացումը RPN (ցույց է տրված մասն է ծրագրի):

համար (ներ = strtok (ներ, Վտ), ներ; s = strtok (0, W)) {

ա = strtod (ներ, եւ ե)

եթե (ե> ներ) հրում (ա).

#define rpnop (x) printf ( "% գ.« * ներ), բ = փոփ (), որը = փոփ (), հրում (x)

էլ, եթե (* s == '+') rpnop (a + b).

էլ, եթե (* s == '') rpnop (ա - բ)

էլ, եթե (* վ == *) rpnop (ա * բ)

էլ, եթե (* s == '/') rpnop (ա / բ)

#undef rpnop

}

մետիզ implementations

Այդ օրերին, երբ համակարգչային տեխնոլոգիաների էր, շատ թանկ է, այն էր, որ լավ գաղափար է ստիպել մարդկանց օգտագործել աճին arresters: 1960-ական թվականներին, ինչպես հիմա, ապա դա հնարավոր էր ձեռք բերել հաշվիչներ, որոնք աշխատում է հակառակ Լեհաստանի նշում. Է ավելացնել 2-րդ եւ 3 նրանցից պետք է մուտքագրեք 2, ապա 3, եւ սեղմեք «գումարած» կոճակը: Առաջին հայացքից, ապա ներմուծած օպերանդներից է օպերատորի թվում էր բարդ եւ դժվար է հիշել, սակայն որոշ ժամանակ անց ոմանք էլ թմրամոլ այս մտածելակերպին եւ չի կարող հասկանալ, թե ինչու մյուսները պնդում են, հիմար Infix, որն այնքան բարդ է եւ այնքան սահմանափակ է.

Burroughs ընկերությունը նույնիսկ կառուցել է mainframe, որը չուներ այլ հիշողությունը, բացառությամբ գրապահոց: Միակ բանը, որ ստիպում է մեքենան դիմել ալգորիթմներ եւ մեթոդների RPN է կենտրոնական բուրգ: Իր բոլոր գործողությունների են որպես arresters օպերատորների, որը կիրառվում է վերին n արժեքներին: Օրինակ, որ թիմը գրավեց հետադարձ հասցե է վերեւից գրապահոց, եւ այլն: D. ճարտարապետությունը նման մի մեքենա պարզ էր, բայց ոչ բավականաչափ արագ է մրցակցել ավելի տարածված կառուցվածքները: Շատերը, սակայն, միեւնույն է, ափսոսում է այն փաստը, որ նման պարզ ու էլեգանտ մոտեցումը computing, որտեղ ամեն մի ծրագիր էր արտահայտությունն opn, գտավ իր շարունակությունը:

Մեկ անգամ հաշվիչներ հետ RPN հայտնի էին, եւ որոշ մարդիկ դեռ տալ նրանց նախապատվությունը: Ի լրումն, նրանք մշակեցին մի դեղ-oriented լեզուներով, ինչպիսիք են Forth: Այսօր դա քիչ է օգտագործվում, բայց դեռեւս nostalgic իր նախկին օգտագործողների.

Այսպիսով, ինչ է նշանակում jokes about Reverse Լեհաստանի երշիկ.

Եթե ենթադրենք, որ օպերատորը երշիկ, որ infix նշում, որ դա պետք է լինի, որ ժապավենը, ինչպես պայմանական տաք շուն. Որ RPN գտնվում է հենց երկու halves ստանալ պատրաստ therebetween հաշվարկից հետո: Այժմ գալիս է դժվար մասը մանանեխ. Նա արդեն երշիկ, ք. E. Արդեն հաշվարկվում է որպես unary օպերատորի. Ենթադրվում է, որ մանանեխի նույնպես պետք է ցույց է որպես չհաշվարկված եւ, հետեւաբար, պետք է տեղափոխվի դեպի աջ երշիկ ... Բայց դա հնարավոր է, դա պահանջում է շատ մեծ բուրգ ...