RPN: algorithm, mbinu na mifano

RPN mara moja ukawa msingi wa programu ya kompyuta duniani. Leo ni si yanajulikana. Kwa hiyo, Comic mfano, ikionyesha "reverse" mistari Polish sausage nje, bado inaweza kueleweka na baadhi programmers mwenye ujuzi. Si vizuri sana kueleza utani, lakini katika kesi hii itakuwa ni kikamilifu haki.

infix

programmers wote, na wanafunzi wengi ni ukoo na matumizi ya kampuni. Kwa mfano, kujieleza x + summation maadili kwa vigezo x na y kutumika pamoja ishara. Chini yanajulikana ni ukweli kwamba hii ni zilizokopwa kutoka hisabati nukuu, iitwayo infix nukuu, kwa kweli, ni tatizo kubwa kwa mashine. operator Hii inapata na pembejeo thamani mbili zimeandikwa upande wa kushoto na kulia. Katika programu nukuu kutumika kwa hiari na shughuli ishara. Kwa mfano, x + y inaweza kuandikwa kama kazi ya mara (x, y), ambapo compiler na hatimaye hubadilisha infix nukuu. Hata hivyo, kila mtu anajua hesabu ni nzuri sana kutotumia maneno hesabu, ambayo kuunda aina ya ndani mini-lugha katika karibu kila lugha ya programu.

formula translator

kwanza kweli mafanikio lugha Fortran programu imekuwa hivyo hasa kwa sababu ya kujieleza hesabu (yaani formula ..) Ni waongofu (matangazo) katika kanuni, hivyo jina lake - Mfumo tafsiri. Kabla ya hapo, walikuwa na kuandika, kwa mfano, folded katika mfumo wa kazi (na kuzidisha (b, c)). Katika COBOL tatizo la utekelezaji wa moja kwa moja uongofu formula ilichukuliwa vigumu sana kwa sababu programmers na kuandika mambo kama Ongeza Kwenye B Mutliply By C.

Kuna ubaya gani infix?

Tatizo ni, kwamba waendeshaji kuwa na mali kama vile umuhimu wa kwanza na associativity. Kwa sababu hiyo, ufafanuzi wa infix kazi inakuwa zisizo yasiyo na maana kazi. Kwa mfano, kuzidisha ina kipaumbele juu kuliko ya kuongezeka au kutoa, ambayo ina maana kwamba kujieleza 2 + 3 * 4 si sawa na jumla ya 2 na 3, kuyagawa kwa 4, kama itakuwa katika utendaji wa waendeshaji kutoka kushoto kwenda kulia. Kwa kweli, kuzidisha 3 na 4 na kuongeza 2. Mfano huo unaonyesha kwamba hesabu ya infix kujieleza mara nyingi inahitaji mabadiliko katika utaratibu wa waendeshaji na operands. Aidha, ni muhimu kutumia braces kuangalia nukuu wazi zaidi. Kwa mfano, (2 + 3) * (4 + 5) hawawezi kuandikwa bila mabano, kwa sababu 2 + 3 * 4 + 5 ina maana kwamba unahitaji kuzidisha 3 na 4 na kuongeza 2 na 5.

utaratibu ambao unataka mahesabu waendeshaji inahitaji muda kukumbuka. Kwa sababu hiyo, wanafunzi ambao kuanza kujifunza hesabu, mara nyingi kupata matokeo sahihi, hata kama shughuli halisi hufanywa kwa usahihi. Ni muhimu kufundisha amri ya kauli hatua kufikia moyo. Kwanza, hatua lazima ifanyike katika mabano, basi kuzidisha na kugawanya, na hatimaye kujumlisha na kutoa. Lakini kuna njia nyingine ya kuandika maneno hisabati kama infix nukuu ni moja ya uwezekano "lugha ndogo" kwamba unaweza kuongezwa kwa zaidi tu.

Kiambishi awali na postfix nukuu

Mbili ya njia mbadala wengi maalumu ni kurekodi operator kabla au baada ya operands yake. Zinajulikana kama kiambishi awali na postfix nukuu. Logician Yan Lukasevich zuliwa kwanza mwaka wa 1920. Yeye aliishi katika Poland, hivyo rekodi inaitwa Kipolishi. Postfix version, kwa mtiririko huo, zinazoitwa Reverse Kipolishi nukuu (ARF). tofauti kati ya njia hizi mbili ni mwelekeo ambao kusoma rekodi (kutoka kushoto kwenda kulia au haki ya kushoto), hivyo inatosha kufikiria kwa kina moja tu wao. operator OPN imeandikwa baada operands yake. Hivyo, usemi AB + inawakilisha mfano RPN kwa A + B.

Unlimited idadi ya operands

faida ya haraka ya nukuu ni kwamba muhtasari n-ADIC operator na infix nukuu kweli tu kazi na operands mbili, t. E. Je asili mzuri kwa ajili ya shughuli za binary. Kwa mfano, ABC @ ni kinyume Polish kujieleza kwa kutumia triadic alama ambayo ni kiwango cha juu ya A, B na C. Katika hali hii operator vitendo upande wa kushoto wa tatu operand yenyewe na ni mfano wa kazi simu @ (A, B, C). Kama kujaribu kuandika @ ishara kama infix, kama vile @ BC au kitu kama hicho, inakuwa wazi kwamba ni tu haina kazi.

kipaumbele kutokana na amri ya

RPN ina faida nyingine kwa kuwa kipaumbele cha waendeshaji inaweza kuwakilishwa kwa amri ya muonekano wao. Wakati huo huo kamwe haja braces, ingawa inaweza kuwa ni pamoja na shughuli za wahusika ili kuwezesha kubadilika kutoka infix nukuu. Kwa mfano, AB + C * - thabiti sawa (A + B) * C, hivyo kuzidisha haiwezi mahesabu mpaka Aidha kufanywa, ambayo inatoa operand pili kwa kuzidisha. Hiyo ni, kama mahesabu AB + C * na mtoa moja kwa wakati mmoja, sisi kupata AB + C * -> (AB +) * C -> (A + B) * C.

hesabu algorithm

OPN operator kuonekana kama vile kazi hiyo inachukua kama hoja thamani mbili zilizoandikwa upande wa kushoto kwake. Aidha, ni nukuu ya asili kwa matumizi ya lugha ya programu, kama ilivyo desturi ya hesabu yake inalingana na shughuli stack na haja ya kuchanganua ni kuondolewa. Kwa mfano, arrester katika usemi 5 + 6 * 7 itaonekana kama 5, 6, 7 *, +, na inaweza mahesabu tu kwa skanning kutoka kushoto kwenda kulia na kuandika maadili katika stack. Kila ishara ya kawaida ya kazi, kuchaguliwa na kipengele juu ya 2 ya kumbukumbu ya kompyuta, mwendeshaji hutumiwa na matokeo akarudi kumbukumbu. Wakati wa mwisho kutokana na hesabu kujieleza itakuwa katika juu ya stack.

Kwa mfano:

• S = () 5, 6, 7, *, + 5 na kuwekwa juu ya stack.
• S = (5) 6, 7, *, + 6 kuwekwa kwenye stack.
• S = (5, 6), 7 *, 7 + mahali stack.
• S = (5, 6, 7), * 2 + kuchagua maadili kutoka stack, matumizi * na mahali matokeo katika stack.
• S = (5, 6 * 7) = (5, 42) + 2 thamani zilizochaguliwa kutoka stack, kuomba + na kuweka matokeo katika stack.
• S = (5 + 42) = (47) hesabu kukamilika, matokeo kuhifadhiwa katika juu ya stack.

algorithm hii inaweza kuchunguzwa RPN kurudia, lakini kila wakati kazi, bila kujali magumu kujieleza Hesabu.

OPN na mwingi ni uhusiano wa karibu. Mfano huu inaonyesha jinsi ya kutumia kumbukumbu mahesabu ya thamani ya reverse Kipolishi nukuu. Chini ya wazi ni kwamba unaweza kutumia stack, kuwabadili kiwango infix kujieleza kushindwa kwa figo.

Mifano ya lugha ya programu

Pascal RPN barabara kama hii (inaonyesha sehemu ya mpango).

Kusoma idadi na waendeshaji katika mzunguko kuitwa utaratibu, ambayo huamua kama ishara ya simu au ishara utendaji. Katika kesi ya kwanza, thamani kuhifadhiwa katika stack, na ya pili ya mbili namba stack juu ya hatua sambamba ni kazi na matokeo ni kuhifadhiwa.

toktype: = num;

kusoma (s);

kama c katika [ '+', '-', '*', '/'] kwa wakati huo kuanza

kama eoln kisha cn: = '' mwingine kusoma (cn);

kama cn = '' kisha

kesi ya

'+': Toktype: = kuongeza; '-': toktype: = ndogo;

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

mwisho

mwingine kuanza

ikiwa = '-' basi SGN: = -1 mwingine kosa: = c <> '+',

kwa: = cn

mwisho

mwisho,

kama (si kosa) na (toktype = num) kisha getnumber;

kama toktype <> num kisha kuanza

y = pop, x: = pop,

kama si kosa basi

kesi toktype ya

kuongeza: z: = x + y; ndogo: z: = x-y, mul: z: = x * y; div: z: = x / y

mwisho

kushinikiza (z);

C-utekelezaji RPN (umeonyesha sehemu ya mpango):

kwa (s = strtok (watu, w); s; s = strtok (0, w)) {

a = strtod (watu, & e);

kama (e> watu) kushinikiza (a);

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

mwingine kama (* s == '+') rpnop (a + b);

mwingine kama (* s == '-') rpnop (- b);

mwingine kama (* s == '*') rpnop (* b);

mwingine kama (* s == '/') rpnop (/ b);

#undef rpnop

}

utekelezaji vifaa

Katika siku hizo, wakati teknolojia ya kompyuta na ghali sana, ilidhaniwa wazo nzuri kwa nguvu watu kutumia vizimio kuongezeka. Mwaka 1960-Mwanachama., Kama sasa, ina uwezo wa kununua calculators, ambayo kazi katika reverse Kipolishi nukuu. Kuongeza 2 na 3 kati yao lazima uweke 2, kisha 3, na vyombo vya habari "pamoja na" button. Kwa mtazamo wa kwanza, pembejeo operands kwa operator ilionekana ngumu sana kukumbuka, lakini baada ya muda baadhi ni addicted na mkabala huu wa mawazo na hakuweza kuelewa ni kwa nini watu wengine kusisitiza juu infix mjinga, ambayo ni ngumu na hivyo ni mdogo.

Burroughs kampuni hata kujengwa mainframe, ambayo haikuwa na kumbukumbu nyingine, ila stack. Kitu pekee ambayo inafanya mashine - kutumika mipangilio na njia za RPN kwa stack ya kati. All wa shughuli zake zilichukuliwa kama vizimio waendeshaji, ambayo inatumika kwa maadili ya juu n. Kwa mfano, timu alichukua Return ya anwani kutoka juu ya mnara, na kadhalika. D. usanifu wa mashine ya hayo ilikuwa rahisi, lakini si kasi ya kutosha kushindana na usanifu zaidi ya kawaida. Wengi, hata hivyo, bado majuto ukweli kwamba mfumo huo rahisi na ya kifahari ya kompyuta ambapo kila mpango ilikuwa usemi wa OPN, iligundua muendelezo wake.

Moja wakati calculators na RPN zilikuwa maarufu, na baadhi ya watu bado kuwapa upendeleo. Aidha, wao maendeleo ya lugha stack-oriented, kama vile Nne. Leo hii ni kutumika kwa kidogo, lakini bado nostalgic kutoka kwa watumiaji wake wa zamani.

Hivyo ni nini maana utani kuhusu Reverse Kipolishi sausage?

Kama sisi kudhani kwamba alama ya sausage, infix nukuu, inapaswa kuwa ndani ya roll kama katika kawaida moto mbwa. RPN iko haki katika nusu mbili kupata therebetween tayari baada hesabu. Sasa inakuja sehemu ngumu - haradali. Yeye ni tayari kwenye sausage, t. E. Tayari mahesabu kama alama unary. Inaaminika kuwa haradali lazima pia umeonyesha kama uncalculated na kwa hiyo lazima wakiongozwa na haki ya sausage ... Lakini inawezekana, hii itahitaji stack kubwa mno ya ...