Agbanwe ederede Polish: algorithm, ụzọ na ihe atụ

Akwụkwọ ndekọ Polish a na-agbanwe agbanwe bụbu ihe ndabere nke ụwa nke mmemme kọmputa. Taa, ọ bụghị nke a ma ama. Ya mere, ihe atụ na-atọ ọchị nke na-akọwa "nsụgharị Polish" laa azụ na bun, ụfọdụ ndị na-eme ihe ngosi nwere nghọta ka nwere ike nghọtahie. Ọ dịghị mma ịkọwa egwuregwu ahụ, ma na nke a, ọ ga-abụ onye ziri ezi.

Inye itinye

Ndị na-eme ihe nkiri na ọtụtụ ụmụ akwụkwọ maara nke ọma na ndị ọrụ. Dịka ọmụmaatụ, na okwu x + y, a na-eji ihe mgbakwunye na-agbakwụnye iji kwado ụkpụrụ nke variables x na y. Ihe a maara nke ọma bụ na nke a gbaziri site na mgbakọ na mgbakọ na mwepụ, nke a na-akpọ akwụkwọ ntinye aka, bụ n'ezie nnukwu nsogbu maka igwe. Onye ọrụ dị otú ahụ na-ewere dị ka ihe abụọ ntinye abanye n'aka ekpe na aka nri ya. Na mmemme, ọ dịghị mkpa iji akara ngosi na ihe ịrịba ama ọrụ. Dịka ọmụmaatụ, x + y nwere ike dee ya ka ọ bụrụ ọrụ ịgbakwunye (x, y), nke onye nchịkọta akụkọ na-emesị gbanwee akwụkwọ edemede ahụ. Otú ọ dị, onye ọ bụla maara mgbakọ na mwepụ nke ọma ka ọ ghara iji okwu edemede, nke na-etolite ụdị asụsụ nta n'ime ihe fọrọ nke nta ka ọ bụrụ asụsụ ọ bụla.

Ndị nsụgharị nke usoro

Asụsụ mbụ nke asụsụ mmemme Fortran na-enwe n'ezie n'ihi na a na-agbanwe okwu ndị a na-akọwa (ya bụ, usoro) n'ime ya (sụgharịrị) gaa na koodu, ya mere aha ya - Usoro mgbasa ozi TRANslation. Tupu, ha ga-ede ede, dịka ọmụmaatụ, n'ụdị ọrụ gbakwunye (a, ọtụtụ (b, c)). Na Kobol, enwere nsogbu nke imejuputa mgbanwe ntughari akpachara anya nke siri ike, ebe ọ bụ na ndị mmemme nwere ide ihe dị ka Add A To B Mutliply By C.

Kedu ihe na-ezighi ezi na ọnwu ahụ?

Nsogbu bụ na ndị ọrụ nwere ihe ndị dịka ibute ụzọ na mkpakọrịta. N'ihi nke a, nkọwa nke ọrụ nke itinye ọkụ ahụ na-aghọ ọrụ na-enweghị isi. Dịka ọmụmaatụ, ibute ihe ntanye dị elu karịa ntinye ma ọ bụ ntinye, nke a pụtara na okwu 2 + 3 * 4 adịghị ọnụ nha nke 2 na 3 nke a mụbara site na 4, dịka ọ ga-abụ ikpe mgbe ị na-eme ndị ọrụ site n'aka ekpe gaa n'aka nri. N'ezie, mụbaa 3 site na 4 ma gbakwunye 2. Ihe atụ a na-egosi na ịtụle okwu mmechi ahụ na-achọ mgbanwe n'ọkwa nke ndị ọrụ na ọrụ ha. Na mgbakwunye, anyị ga-eji ntinye aka iji mee ka nkọwa ahụ dokwuo anya. Dịka ọmụmaatụ, (2 + 3) * (4 + 5) enweghị ike dee ya n'enweghị akara aka, n'ihi na 2 + 3 * 4 + 5 pụtara na ị ga-amụba 3 site na 4 gbakwunye 2 na 5.

Usoro nke ndị ọrụ ga-agbakọ ga-achọ ogologo oge n'isi. N'ihi nke a, ụmụ akwụkwọ na-amalite ịmụta ihe na-emekarị ihe na-ezighi ezi, ọbụlagodi na ọ bụ n'eziokwu na arụ ọrụ ahụ n'ụzọ ziri ezi. Ọ dị mkpa ịmụta ihe ndị ọrụ na-eme site n'obi. Nke mbụ, ihe ndị a na-eme na brackets, mgbe ahụ ịkọ ụda na nkewa, na ntinye gbakwunyere na nrugharị ga-arụ. Ma e nwere ụzọ ndị ọzọ nke ederede okwu mgbakọ na mwepụ, n'ihi na ntinye ederede bụ naanị otu n'ime "obere asụsụ" nwere ike ịtinyekwuo.

Nkọwapụta na nkọwa postfix

Uzo abuo kachasi nma karia ndi mmadu bu ihe edeputara onye ozo tupu ma obu mgbe ndi oru ya. A maara ha dịka ọkwa iwu na ọkwa postfix. Ezigbo uche Jan Lukasevich mepụtara nke mbụ n'ime ha n'afọ ndị 1920. O biri na Poland, ya mere a na-akpọ ihe ndekọ ahụ Polish. Postfix mbipute, n'otu n'otu, natara aha nke mbido Polish notation (OPN). Nanị ihe dị iche n'etiti ụzọ abụọ ahụ bụ ntụziaka nke a ga-agụnye ntinye (aka ekpe gaa n'aka nri ma ọ bụ aka ekpe), ya mere ọ ga-ezu iji tụlee nanị otu n'ime ha n'ụzọ zuru ezu. Na OPN, a na-edezi onye ọrụ ahụ mgbe ọ na-arụ ọrụ. Ya mere, okwu AB + bụ ihe atụ nke mgbanwe Polish ndekọ maka A + B.

Ọnụ ọgụgụ ole na ole nke operands

Ihe na-eme ngwa ngwa bụ ịkọwapụta ya bụ na onye ọrụ n-adic na-ejikọta ya n'ozuzu ya, na ntinye ederede na-arụ ọrụ nanị site na ope ọrụ abụọ, ya bụ, ọ bụ site na ọdịdị ya ka ọ dị mma maka ọrụ ọnụọgụ abụọ. Dịka ọmụmaatụ, ABC @ bụ okwu Polish na-agbanwe agbanwe na-eji akara atọ, nke na - achọpụta uru kachasị elu site na A, B na C. N'okwu a, onye ọrụ ahụ na-arụ ọrụ 3 n'akụkụ aka ekpe ma kwekọọ na oku nke ọrụ @ (A, B, C). Ọ bụrụ na ị gbalịrị dee akara ngosi ahụ dịka ihe ntanye, dịka ọmụmaatụ A @ BC ma ọ̄ bụ ihe yiri ya, mgbe ahụ ọ bịara doo anya na nke a anaghị arụ ọrụ.

E nyere iwu tupu iwu ahụ

Otu ederede Polish na-enwe ihe ọzọ ka mma na na ihe kachasị mkpa nke ndị ọrụ nwere ike ịnọchite anya ha. Agaghị achọ nne na nna, ọ bụ ezie na ha nwere ike ịsonye dị ka ihe nnọchiteanya azụmahịa iji mee ka a gbanwee ya na ntinye akwụkwọ. Dị ka ihe atụ, AB + C * bụ otu ọnụahịa bara uru (A + B) * C, ebe ọ bụ na a pụghị ịgbakọ ọtụtụ ihe ruo mgbe agwụ agwụ, nke na-enye ọrụ nke abụọ maka mmegharị ụba. Nke ahụ bụ, ma ọ bụrụ na a na-agbakọpụta AB + C maka onye ọrụ n'otu oge, mgbe ahụ anyị na-enweta AB + C * -> (AB +) * C -> (A + B) * C.

Na ngụkọta algorithm

Na OPN, onye ọrụ ahụ dị ka ọrụ nke na-ewe dị ka arụmụka ụkpụrụ abụọ edere n'aka ekpe ya. Na mgbakwunye, nke a bụ ihe ebumpụta ụwa maka iji mee ihe na asụsụ mmemme, ebe ọ bụ na usoro nhazi ya kwekọrọ n 'arụ ọrụ nchịkọta na njedebe maka nkwụsị. Dịka ọmụmaatụ, na ARS, okwu 5 + 6 * 7 ga-adị ka 5, 6, 7 *, +, a pụkwara ịgbakọ ya site n'ịgụ site n'aka ekpe gaa n'aka nri na ederede na nchịkọta. Oge ọ bụla a na-ahụ ihe ịrịba ama ọrụ ahụ, a na-ahọrọ 2 elu nke sitere na ebe nchekwa igwe, a na-eji onye ọrụ ahụ eme ihe na nzaghachi a na-echeta. Mgbe njedebe nke okwu ahụ ruru, ihe nchoputa ga-abụ n'elu elu.

Dịka ọmụmaatụ:

• S = () 5, 6, 7, *, + tinye 5 na nchịkọta.
• S = (5) 6, 7, *, + tinye 6 na nchịkọta.
• S = (5, 6) 7, *, + tinye 7 na nchịkọta.
• S = (5, 6, 7) *, + họrọ ụkpụrụ 2 site na nchịkọta, tinye * ma tinye nsonaazụ na nchịkọta.
• S = (5, 6 * 7) = (5, 42) + họrọ ụkpụrụ 2 site na nchịkọta, tinye + ma tinye nsonaazụ na nchịkọta.
• S = (5 + 42) = (47) ngụkọta zuru ezu, ihe si na ya pụta n'elu nchịkọta ahụ.

Enwere ike ichota algọridim a na-abanye na Polish na-abanye ọtụtụ ugboro, mana oge ọ bụla ọ ga-arụ ọrụ, n'agbanyeghị otú okwu ahụ si dị mgbagwoju anya.

Nchịkọta na nchịkọta nwere njikọ chiri anya. Ihe atụ ahụ dị n'elu na-egosiputa otú e nwere ike isi tinye ebe nchekwa iji kọwaa uru dị na Polish ntụgharị. O doro anya na ị nwere ike iji nchịkọta ahụ site na ịgbanye okwu okwu mmechi na njedebe.

Ihe atụ na asụsụ mmemme

N'asụsụ Pascal, a na-emejupụta ndekọ ederede Polish nke dị ka nke a (akụkụ nke usoro ihe a).

Iji gụọ nọmba na ndị ọrụ na akaghị aka, a na-akpọ usoro a na-ekpebi ma akara ahụ bụ nọmba ma ọ bụ akara ọrụ. N'okwu mbụ, a na-edeba uru ahụ na nchịkọta, mgbe na nke abụọ, a na-arụ ọrụ kwekọrọ na ọnụ ọgụgụ abụọ dị elu nke nchịkọta ahụ ma zọpụta ya.

Toktype: = num;

Gụọ (c);

Ọ bụrụ na iji ['+', '-', '*', '/'] malite

Ọ bụrụ na eoln mgbe ahụ cn: = '' ọzọ gụọ (cn);

Ọ bụrụ na cn = '' mgbe ahụ

Ileba anya

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

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

Ọgwụgwụ

Nmalite

Ọ bụrụ na c = '-' wee sgn: = -1 ọzọ njehie: = c <> '+';

Na: = cn

Ọgwụgwụ

Ọgwụgwụ;

Ọ bụrụ (ọ bụghị njehie) na (toktype = nọmba) wee nweta;

Ọ bụrụ na toktype <> num wee malite

Y: = po; X: = po;

Ọ bụrụ na ọ bụghị njehie ahụ

Ihe gbasara toktype nke

Tinye: z: = x + y; Sub: z: = x-y; Mul: z: = x * y; Div: z: = x / y

Ọgwụgwụ

Push (z);

C-mmejuputa ederede ederede Polish (akuku nke usoro ihe enyere):

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

A = strtod (s, & e);

Ọ bụrụ na (e> s) push (a);

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

Ọ bụrụ na (* s == '+') rpnop (a + b);

Ọ bụrụ na (* s == '-') rpnop (a - b);

Ọ bụrụ na (* s == '*') rpnop (a * b);

Ọ bụrụ na (* s == '/') rpnop (a / b);

#undef rpnop

}

Mmezi ngwa ngwa

N'oge ndị ahụ, mgbe nkà na ụzụ kọmputa dị oké ọnụ, a na-ewere ya dị ka ezi echiche ịmanye ndị mmadụ iji OPN. N'afọ ndị 1960, dị ka taa, ọ ga-ekwe omume ịzụta ndị na-arụ ọrụ na ntụgharị ederede Polish. Iji tinye 2 na 3 n'ime ha, tinye 2, wee pịa 3 ma pịa bọtịnụ gbakwunyere. N'ileghachi anya na mbụ, ọrụ nke opera ndị ọrụ ahụ yiri ihe mgbagwoju anya ma sie ike icheta, ma mgbe oge ụfọdụ gasịrị, echiche ndị a wee ghara ịghọta ihe mere ndị ọzọ ji ekwusi ike na ndekọ nzuzu nke dị mgbagwoju anya na nke a kpaara ókè.

Burroughs ọbụna wuru isi ihe na-enweghị RAM ọ bụla, ma e wezụga nchịkọta. Naanị ihe igwe ahụ mere bụ itinye algọridim na ụzọ ntụgharị Polish na-edegara na stack. A na-ewere ọrụ niile ya dị ka ndị ọrụ OPN, ndị ọrụ ya na-abawanye na n. Dịka ọmụmaatụ, iwu mbugha weghaara adreesị site na n'elu nchịkọta ahụ, wdg. Ịdị mma nke igwe dị otú ahụ dị mfe, ma ọ bụghị ngwa ngwa iji merie ụlọ ọrụ ndị ọzọ. Otú ọ dị, ọtụtụ ndị ka na-akwa ụta na ụzọ dị mfe ma mara mma maka nhazi, ebe usoro ihe omume ọ bụla bụ ngosipụta nke OPN, ahụghị n'ihu ya.

N'otu oge, ndị na-eji usoro mgbanwe Polish eme ihe na-ewu ewu, ụfọdụ na-ahọrọ ha. Tụkwasị na nke ahụ, e mepewo asụsụ ndị a na-atụkọta na staple dịka Forth. Taa, ọ bụ ntakịrị ihe eji eme ihe, mana ọ ka na-eme ka ndị ọrụ mbụ ya ghara ịnwụ.

Ya mere, olee ihe ị ga-eji na-egwu egwu banyere nkedo azụ Polish?

Ọ bụrụ na ị tụlee onye ọrụ ntanetị ahụ, mgbe ahụ na ntinye akwụkwọ, ọ ga-adị n'ime akwụkwọ mpịakọta ahụ, dịka na nkịta dị ọkụ. N'akwụkwọ ndị Poland na-edegharị, ọ bụ n'aka nri nke abụọ ahụ, dị njikere ịkụ n'etiti ha mgbe nchịkọta. Ugbu a amalite akụkụ kachasị ike - mọstad. Ọ bụ ugbua na soseji, ya bụ, a gbasowo ya dị ka onye ọrụ na-enweghị ọrụ. Enwere echiche na mkpuru mọstad kwesiri ka egosiputa na enweghi ihe edeputara ya, ma, ya mere, a ghaghariri ya n'aka nri nke soseji ... Ma ma eleghị anya, ọ ga-ewe nnukwu nchịkọta ...