RPN: algorithm, fomba fiasa sy ny ohatra

RPN indray mandeha namorona ny fototry ny solosaina programa eto amin'izao tontolo izao. Amin'izao fotoana izao dia tsy fantatra tsara. Noho izany, dia fanoharana tantara an-tsary, maneho ny "mamadika" Poloney saosisy horonana ivelany, mety mbola ho azon'ny olona sasany manam-pahalalana rindrambaiko. Tsy manazava tsara ny vazivazy, fa amin'ity tranga ity dia ho tanteraka nohamarinina.

tsofoka

Rindrambaiko rehetra, ary ny ankamaroan'ny mpianatra efa zatra ny fampiasana ny mpandraharaha. Ohatra, ny teny hoe X + summation sanda ho an'ny hiovaova X sy Y efa nampiasaina miampy famantarana. Tsy tsara fantatra dia ny hoe izany dia nindramina avy amin'ny matematika tarehimarika, antsoina hoe tsofoka tarehimarika, raha ny marina, dia olana lehibe ho an'ny milina. Izany mpandraharaha mandray roa ny soatoavina toy ny torohevitra voasoratra eo amin'ny ankaviany sy mahitsy. Ao amin'ny fandaharana tarehimarika optionally ampiasaina amin'ny famantarana asa. Ohatra, X + Y azo soratana toy ny asa ny vala (x, y), izay ny compiler ary farany dia niova fo tsofoka tarehimarika. Na dia izany aza, ny olona rehetra mahafantatra ny kajy tsy tsara loatra hampiasa rafitrisa teny, izay mamorona karazana anatiny mini-teny amin'ny fiteny efa ho isaky ny fandaharana.

raikipohy mpandika teny

Tena nahomby voalohany Fortran fiteny fandaharana no lasa betsaka noho ny fanehoan-kevitra rafitrisa (izany hoe raikipohy ..) Tsy niova fo (fandaharana) ao amin'ny fehezan-dalàna, noho izany ny anarany hoe: - raikipohy fandikan-teny. Talohan'ny izany, dia tsy maintsy nanoratra, ohatra, aforitra tao amin'ny endriky ny asa (sy mihabetsaha (b, c)). In COBOL olana ny fametrahana mandeha ho azy raikipohy fiovam-po no heverina ho tena sarotra satria ny rindrambaiko maintsy manoratra ny zavatra toy Add A To B Mutliply By C.

Inona no maharatsy ny tsofoka?

Ny olana dia, ny mpandraharaha toy izany sy ny fananana toy ny tiana associativity. Noho izany, ny famaritana ny asa tsofoka lasa tsy misy dikany asa. Ohatra, fampitomboana manana ambony tiana noho ny koa na subtraction, izay midika fa ny teny hoe 2 + 3 * 4 Tsy mitovy ny isan'ny 2 sy 3, ampitomboina 4, tahaka ny mety hatao amin'ny fanatanterahana ny mpandraharaha avy any ankavia miankavanana. Raha ny marina, maro 3 amin'ny 4 sy manampy 2. Hita avy amin'izany fa ny fikajiana ny tsofoka maneho hevitra matetika dia mitaky fiovana eo ny baikon'i mpandraharaha sy ny operands. Ankoatra izany, dia ilaina ny mampiasa vy fanitsiana tongotra mba hijery mazava kokoa ny tarehimarika. Ohatra, (2 + 3) * (4 + 5) tsy hay soratana raha tsy misy ny fononteny, satria 2 + 3 * 4 + 5 dia midika fa mila maro 3 amin'ny 4 sy hametraka ny 2 sy 5.

Ny lamina izay te-kajy ny mpandraharaha mitaky ela mahatsiaro. Noho izany, ireo mpianatra izay manomboka mianatra rafitrisa, matetika no mahazo ny vokatra ratsy, na dia ny tena asa ireo araka ny tokony ho tanterahana. Dia ilaina ny mampianatra ny lamin 'asa fanambarana amin'ny alalan'ny fo. Voalohany, ny asa tsy maintsy tanterahina amin'ny fonon, dia fampitomboana sy ny fizarana, ary farany sy subtraction koa. Kanefa misy fomba hafa ny fanoratana toy ny matematika teny tsofoka tarehimarika ihany ny iray amin'ireo azo atao "fiteny kely" izay mety hanampy ho bebe kokoa.

Tovona sy ny postfix tarehimarika

Ny roa amin'ireo malaza indrindra dia ny fomba hafa an-tsoratra ny mpandraharaha aloha na taorian'ny operands. Izy ireo fantatra amin'ny hoe tovona sy ny postfix tarehimarika. Logician Yan Lukasevich namorona ny voalohany tamin'ny 1920. Ary nonina tany Polonina, toy izany koa ny firaketana an-tsoratra atao hoe poloney. Postfix dikan, tsirairay avy, atao hoe Reverse Poloney ny fivoasana (ARF). Ny hany maha samy hafa ny fomba roa ireo dia ny tari-dalana izay hamaky ny firaketana an-tsoratra (avy eo ankavia miankavanana, na zo ankavia), ka dia ampy ny mandinika amin'ny an-tsipiriany fotsiny ny iray tamin'izy ireo. Ny OPN mpandraharaha voasoratra araka ny operands. Noho izany, ny teny hoe AB + RPN maneho ohatra ho an'ny A + B.

Tsy manam-petra isan'ny operands

Ny mahatsara ny tarehimarika avy hatrany dia fa mamintina ny n-adic mpandraharaha sy ny tsofoka tarehimarika tena ihany no miasa amin'ny operands roa, t. E. no tena hoe mety mimari-droa ihany no ho an'ny asa. Ohatra, ABC @ no mifanohitra poloney hoe mampiasa triadic marika izay ny ambony indrindra ilaina ny A, B sy C. Amin'ity tranga ity ny mpandraharaha miasa eo amin'ny ankaviany ny telo operand ihany, ary mifanitsy amin'ny andraikitra iray amin'ny antso @ (A, B, C). Raha miezaka ny hanoratra ny @ mariky toy ny tsofoka, toy ny @ BC na zavatra toy izany, dia lasa mazava fa tsy miasa tsotra izao.

Ny laharam-pahamehana ny baiko nomen'ny

RPN manana tombony hafa ao fa ny laharam-pahamehana ny mpandraharaha dia azo aseho amin'ny alalan'ny ny lamin 'ny bika aman'endriny. Mandritra izany fotoana izany tsy mila vy fanitsiana, na dia mety ho tafiditra toy ny tarehin-tsoratra asa mba hanamorana ny fiovam-po avy amin'ny tsofoka tarehimarika. Ohatra, AB + C * - Mazava be mitovy (A + B) * C, toy izany koa ny fampitomboana tsy azo kajy mandra-nahatanteraka koa, izay manome ny faharoa ho an'ny fampitomboana operand. Izany hoe, raha toa ny kajy AB + C * iray mpandraharaha amin'ny fotoana, dia mahazo AB + C * -> (AB +) * C -> (A + B) * C.

kajy algorithm

Ny mpandraharaha OPN mijery izany ho toy ny asa izay maka tahaka ny fanehoan-kevitra roa soatoavina voasoratra teo amin'ny ankavia. Ankoatra izany, dia voajanahary tarehimarika ho an'ny fiteny ampiasaina ao amin'ny fandaharana, araka ny fanaon'ny ny fikajiana niisa mifanaraka amin'ny asa sy ny ilana parsing no intsony. Ohatra, ny arrester ao amin'ny fitenenana 5 + 6 * 7 hiseho toy ny 5, 6, 7 *, + ary azo kajy fotsiny scanning avy eo ankavia miankavanana sy manoratra ny soa toavina ao amin'ny niisa. Isaky ny famantarana mahazatra ny fandidiana, nifidy ny ambony singa 2 ny solosaina fitadidiana, ny mpandraharaha no ampiasaina sy ny vokatry niverina tany fahatsiarovana. Raha ny vokatra farany amin'ny fikajiana ny teny ho ao an-tampon'ny stack.

Ohatra:

• S = () 5, 6, 7, *, + 5 napetraka eo amin'ny stack.
• S = (5) 6, 7, *, + 6 napetraka eo amin'ny stack.
• S = (5, 6), 7 *, 7 + mametraka ny stack.
• S = (5, 6, 7), * 2 + misafidy soatoavina avy amin'ny niisa, fampiasana + sy mametraka ny vokatry ao amin'ny stack.
• S = (5, 6 * 7) = (5, 42) + 2 soatoavina fidiana avy ao amin'ny niisa, mba hampihatra ireo + ary ny vokatry ao amin'ny stack.
• S = (5 + 42) = (47) fikajiana vita, ny vokatra dia voatahiry ao an-tampon-stack.

Zavatra tsy ampy algorithm afaka RPN imbetsaka, fa isaky ny asa, na dia saro-takarina ny rafitrisa fanehoan-kevitra.

OPN sy stacks dia mifamatotra. Izany ohatra maneho ny fomba mampiasa ny fahatsiarovana mba manao kajy ny hasarobidin'ny ny mifanohitra poloney tarehimarika. Tsy dia mazava fa afaka mampiasa ny niisa, mamelombelona fitsipika fitenenana tsofoka in Matsilo renal tsy fahombiazana.

Ohatra ny fandaharana fiteny

Pascal RPN tonga saina toy izao (dia mampiseho ny ampahany amin'ny fandaharana).

Raha hamaky ny isa sy ny mpandraharaha ao amin'ny tsingerina atao hoe procédure, izay mamaritra raha isa famantarana na ny famantarana fandidiana. Ao amin'ny tranga voalohany, ny vidin'ny voatahiry ao amin'ny niisa, ary ny faharoa ny roa niisa isa ambony dia tanterahina mifanaraka asa sy ny vokatra no voatahiry.

toktype: = Nom;

vakio (s);

raha d in [ '+', '-', '*', '/'] dia manomboka

raha eoln dia CN: = '' olon-kafa hamaky (CN);

raha CN = '' dia

tranga iray

'+': Toktype: = manampy; '-': toktype: = Sub;

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

farany

manomboka hafa

Raha misy = '-' dia sgn: = -1 hafa hadisoana: = d <> '+';

amin'ny: = CN

farany

farany;

Raha (tsy diso) ary (toktype = Nom) dia getnumber;

raha toktype <> Nom dia manomboka

Y = Pop; X: = Pop;

raha tsy fahadisoana avy eo

tranga toktype ny

ampiana hoe: Z: = X + Y; zana: Z: = x-Y; mul: Z: = X * Y; DIV: Z: = x / y

farany

hanoto (z);

C-fampiharana RPN (aseho ampahany amin'ny fandaharana):

ho an'ny (s = strtok (s, w), S, S = strtok (0, w)) {

ny = strtod (s, & e);

raha (e> s) hanoto (a);

#define rpnop (x) printf ( "% c:", * s), amin '= Pop (), iray = Pop (), hanoto (x)

hafa, raha (* s == '+') rpnop (a + b);

hafa, raha (== * s '-') rpnop (a - b);

hafa, raha (* s == '*') rpnop (a * b);

hafa, raha (* s == '/') rpnop (a / b);

#undef rpnop

}

Hardware implementations

Tamin'izany andro izany, raha solosaina lafo be ny teknolojia, dia nihevitra hevitra tsara ny manery ny olona hampiasa firongatry arresters. Tamin'ny 1960-ies., Tahaka ny ankehitriny, dia azo atao ny hividy ny kajy, izay miasa ao mifanohitra poloney tarehimarika. Mba hametraka ny 2 sy 3 amin'izy ireo dia tsy maintsy miditra 2, dia 3, ary tsindrio ny "Plus" bokotra. Raha vao jerena, ny fahan'ny operands ny mpandraharaha dia toa sarotra sy sarotra ny mitadidy, fa nony afaka kelikely sasany Andevozin'ny izany fomba fisainana ka tsy hahatakatra hoe nahoana ny hafa mikiry adala tsofoka, izay tena sarotra ary toy izany koa dia voafetra ihany.

Burroughs orinasa mihitsy aza nanao mainframe, izay tsy nanana fahatsiarovana hafa, afa-tsy stack. Ny hany zavatra izay mahatonga ny milina - nampihatra ny algorithms sy ny fomba RPN ny foibe stack. Ny asa rehetra dia heverina ho toy arresters mpandraharaha, izay mihatra amin'ny ambony N soatoavina. Ohatra, ny ekipa nandray ny Return Address avy any an-tampon-niisa, sy ny sisa. D. Ny trano ny milina toy izany dia tsotra, fa tsy mba mifady ampy hifaninana amin'ny Architectures mahazatra kokoa. Maro, na izany aza, mbola malahelo ny zava-misy fa toy izany tsotra sy kanto ny fomba computing izay fandaharana rehetra dia fanehoan'Andriamanitra ny OPN, nahita ny fitohizan'ny.

Fotoana iray amin'ny RPN kajy, dia mpitia, ary ny olona sasany mbola hanome azy mifidy. Ankoatra izany, dia lasa mitodika niisa-teny, toy ny sisa. Ankehitriny dia kely efa nampiasaina, fa mbola nostalgic avy amin'ny mpampiasa teo aloha.

Koa inona no dikan'ny vazivazy momba ny Reverse poloney saosisy?

Raha mihevitra fa ny mpandraharaha ny saosisy, ny tsofoka tarehimarika, dia tokony ho ao anatin'ny horonan-taratasy toy ny ao amin'ny mahazatra mafana alika. Ny RPN no misy marina ampahany roa ho vonona therebetween aorian'ny kajy. Ary tonga ny sarotra anjara - tsinapy. Izy no efa eo amin'ny saosisy, t. E. Efa kajy toy ny unary mpandraharaha. Misy mihevitra fa voantsinapy dia tokony aseho ihany koa toy ny uncalculated ka noho izany dia tokony ho voatosika ny zon'ny ny saosisy ... Fa azo atao, izany dia mitaky be loatra gazety Ny ...