RPN: algoritma, kaedah dan contoh

RPN sekali membentuk asas seorang pengaturcara komputer di dunia. Hari ini ia tidak begitu terkenal. Oleh itu, ilustrasi komik, yang menggambarkan "terbalik" gulung sosej Poland di luar, masih boleh disalah faham oleh sesetengah pengaturcara berpengetahuan. Tidak baik menjelaskan jenaka, tetapi dalam kes ini ia akan menjadi wajar.

memasang di antara

Semua pengaturcara, dan kebanyakan pelajar sudah biasa dengan penggunaan pengendali. Sebagai contoh, nilai ungkapan x + penjumlahan untuk pemboleh ubah x dan y tanda tambah yang digunakan. Kurang diketahui ialah hakikat bahawa ini dipinjam daripada matematik notasi, dipanggil memasang di antara notasi, sebenarnya, adalah satu masalah besar bagi mesin. operator ini menerima sebagai input dua nilai yang dirakam pada kiri dan kanan. Dalam pengaturcaraan notasi digunakan secara pilihan dengan tanda-tanda operasi. Sebagai contoh, x + y boleh ditulis sebagai fungsi kali ganda (x, y), di mana pengkompil dan akhirnya menukarkan memasang di antara notasi. Walau bagaimanapun, semua orang tahu matematik yang terlalu baik untuk tidak menggunakan ungkapan aritmetik, yang membentuk sejenis dalaman mini-bahasa dalam hampir setiap bahasa pengaturcaraan.

penterjemah formula

Pertama benar-benar berjaya bahasa pengaturcaraan Fortran telah menjadi begitu sebahagian besarnya kerana ungkapan aritmetik (iaitu formula ..) Ia ditukar (siaran) dalam kod, maka nama itu - Formula terjemahan. Sebelum itu, mereka terpaksa menulis, sebagai contoh, dilipat dalam bentuk fungsi (dan bertambah (b, c)). Dalam masalah COBOL melaksanakan formula penukaran automatik dianggap sangat sukar kerana pengaturcara terpaksa menulis perkara seperti Tambahkan A To B Mutliply Oleh C.

Apa yang salah dengan memasang di antara?

Masalahnya ialah, bahawa pengendali mempunyai ciri-ciri seperti keutamaan dan Kesekutuan. Oleh kerana itu, definisi fungsi memasang di antara menjadi tugas bukan remeh. Sebagai contoh, pendaraban mempunyai keutamaan lebih tinggi daripada penambahan atau penolakan, yang bermaksud bahawa ungkapan 2 + 3 * 4 tidak sama dengan jumlah 2 dan 3, didarab dengan 4, kerana ia akan berada dalam prestasi pengendali dari kiri ke kanan. Malah, darab 3 oleh 4 dan menambah 2. Contoh ini menunjukkan bahawa pengiraan ungkapan memasang di antara yang sering memerlukan perubahan dalam perintah pengusaha dan operan. Di samping itu, ia adalah perlu untuk menggunakan pendakap untuk melihat notasi lebih jelas. Sebagai contoh, (2 + 3) * (4 + 5) tidak boleh ditulis tanpa kurungan, kerana 2 + 3 * 4 + 5 bermakna bahawa anda perlu untuk membiak 3 oleh 4 dan menambah 2 dan 5.

Perintah di mana anda mahu untuk mengira pengendali memerlukan panjang ingat. Oleh kerana itu, pelajar-pelajar yang mula belajar aritmetik, sering mendapat keputusan yang salah, walaupun operasi sebenar dilakukan dengan betul. Ia adalah perlu untuk mengajar perintah penyata tindakan oleh jantung. Pertama, tindakan yang perlu dilakukan di dalam kurungan, kemudian darab dan bahagi, dan akhirnya penambahan dan penolakan. Tetapi ada cara lain untuk menulis ungkapan matematik seperti memasang di antara notasi hanya salah satu daripada mungkin "bahasa kecil" yang boleh ditambah kepada lebih.

Awalan dan postfix notasi

Dua daripada alternatif yang paling terkenal adalah untuk merakam pengendali sebelum atau selepas operan itu. Mereka dikenali sebagai awalan dan postfix notasi. Ahli logik Yan Lukasevich mencipta yang pertama pada tahun 1920. Beliau tinggal di Poland, jadi rekod yang dipanggil Poland. versi postfix, masing-masing, yang dipanggil Reverse Poland Notation (ARF). Satu-satunya perbezaan antara kedua-dua kaedah adalah arah di mana untuk membaca rekod (dari kiri ke kanan atau kanan ke kiri), jadi ia cukup untuk mempertimbangkan secara terperinci hanya salah seorang daripada mereka. Pengendali OPN ditulis selepas operan itu. Oleh itu, ungkapan AB + mewakili contoh RPN untuk A + B.

Nombor yang tidak terhad operan

Kelebihan segera not ialah, ia meringkaskan pengendali n-adic dan memasang di antara notasi adalah benar-benar hanya berfungsi dengan dua operan, t. E. Adakah memang sesuai hanya untuk operasi binari. Sebagai contoh, ABC @ adalah ungkapan Poland sebaliknya menggunakan tanda triadic iaitu nilai maksimum A, B dan C. Dalam kes ini pengendali bertindak di sebelah kiri tiga operan itu sendiri dan sepadan dengan fungsi panggilan @ (A, B, C). Jika anda cuba untuk menulis simbol @ sebagai memasang di antara, seperti A @ BC atau sesuatu seperti itu, ia menjadi jelas bahawa ia hanya tidak berfungsi.

Keutamaan diberikan oleh perintah itu

RPN mempunyai kelebihan yang lain dalam bahawa keutamaan pengusaha boleh diwakili oleh perintah penampilan mereka. Pada masa yang sama tidak perlu pendakap, walaupun mereka boleh dimasukkan sebagai watak-watak operasi untuk memudahkan penukaran dari memasang di antara notasi. Sebagai contoh, AB + C * - bersamaan jelas (A + B) * C, jadi pendaraban tidak boleh dikira sehingga tambahan yang dijalankan, yang memberikan operan kedua untuk pendaraban. Iaitu, jika dikira AB + C * oleh satu pengendali pada satu masa, kita akan mendapat AB + C * -> (AB +) * C -> (A + B) * C.

algoritma pengiraan

Pengendali OPN kelihatan sama seperti fungsi yang mengambil sebagai hujah dua nilai ditulis di sebelah kiri beliau. Di samping itu, ia adalah satu notasi semulajadi untuk digunakan dalam bahasa pengaturcaraan, kerana cara pengiraan sepadan dengan operasi timbunan dan keperluan untuk parsing dihapuskan. Sebagai contoh, penangkap dalam ungkapan 5 + 6 * 7 akan muncul sebagai 5, 6, 7 *, +, dan ia boleh dikira hanya dengan mengimbas dari kiri ke kanan dan menulis nilai dalam timbunan. Setiap kali tanda biasa operasi, dipilih oleh elemen atas 2 memori komputer, pengendali digunakan dan hasil yang dikembalikan kepada ingatan. Apabila keputusan akhir bersuara banyak akan berada di bahagian atas tindanan.

Sebagai contoh:

• S = () 5, 6, 7, *, + 5 diletakkan di atas tindanan.
• S = (5) 6, 7, *, + 6 diletakkan di atas tindanan.
• S = (5, 6), 7 *, 7 + meletakkan timbunan.
• S = (5, 6, 7), * 2 + pilih nilai dari timbunan, penggunaan * dan meletakkan hasil dalam timbunan.
• S = (5, 6 * 7) = (5, 42) + 2 nilai yang dipilih daripada timbunan, untuk memohon + dan meletakkan hasil dalam timbunan.
• S = (5 + 42) = (47) pengiraan selesai, hasilnya disimpan di bahagian atas tindanan.

Algoritma ini boleh disemak RPN berulang kali, tetapi setiap kali ia akan bekerja, tidak kira bagaimana kompleks ungkapan aritmetik.

OPN dan susunan berkait rapat. Contoh ini menunjukkan bagaimana untuk menggunakan memori untuk mengira nilai notasi Poland terbalik. Kurang jelas adalah bahawa anda boleh menggunakan tindanan, menukar memasang di antara ungkapan standard dalam kegagalan buah pinggang akut.

Contoh bahasa pengaturcaraan

Pascal RPN sedar seperti ini (menunjukkan sebahagian daripada program ini).

Untuk membaca nombor dan pengendali dalam kitaran dipanggil prosedur, yang menentukan sama ada nombor atau tanda operasi token. Dalam kes pertama, nilai yang disimpan dalam tindanan, dan kedua tindakan sama dua nombor timbunan atas dilakukan dan hasilnya disimpan.

toktype: = num;

membaca (s);

jika c dalam [ '+', '-', '*', '/'] kemudian mula

jika eoln kemudian cn: = '' pun membaca (cn);

jika cn = '' kemudian

kes seorang

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

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

akhir

pun bermula

jika a = '-' kemudian SGN: = -1 ralat lain: = c <> '+';

dengan: = cn

akhir

berakhir;

jika (tidak ralat) dan (toktype = num) maka getnumber;

jika toktype <> num kemudian mula

y = pop; x: = pop;

jika tidak kesilapan kemudian

kes toktype daripada

menambah: z = x + y; sub: z = x-y; mul: z = x * y; div: z = x / y

akhir

tolak (z);

C-pelaksanaan RPN (ditunjukkan sebahagian daripada program ini):

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

a = strtod (s, & e);

jika (e> s) tolak (a);

# menentukan rpnop (x) printf ( "% c:", * s), b = pop (), a = pop (), tolak (x)

lain jika (* s == '+') rpnop (a + b);

lain jika (* s == '-') rpnop (a - b);

lain jika rpnop (* s == '*') (a * b);

lain jika (* s == '/') rpnop (a / b);

rpnop #undef

}

pelaksanaan perkakasan

Pada masa itu, apabila teknologi komputer adalah sangat mahal, ia dianggap satu idea yang baik untuk memaksa orang ramai untuk menggunakan arresters lonjakan. Pada tahun 1960-ies., Seperti sekarang, ia adalah mungkin untuk membeli kalkulator, yang bekerja dalam notasi Poland terbalik. Untuk menambah 2 dan 3 daripada mereka mesti memasukkan 2, kemudian 3, dan tekan butang "plus". Pada pandangan pertama, operan input kepada pengendali kelihatan rumit dan sukar untuk diingati, tetapi selepas itu ada yang ketagih kepada cara pemikiran ini dan tidak dapat memahami mengapa orang lain mendesak memasang di antara bodoh, yang begitu rumit dan sebagainya adalah terhad.

syarikat Burroughs walaupun membina kerangka utama, yang tidak mempunyai memori yang lain, kecuali timbunan. Satu-satunya perkara yang membuat mesin - digunakan algoritma dan kaedah RPN kepada timbunan pusat. Semua operasinya dianggap sebagai pengendali arresters, yang terpakai kepada nilai-nilai n atas. Sebagai contoh, pasukan mengambil Pulang Alamat dari bahagian atas timbunan, dan sebagainya. D. Seni bina mesin itu adalah mudah, tetapi tidak cukup pantas untuk bersaing dengan seni bina yang lebih biasa. Banyak, bagaimanapun, masih menyesal hakikat bahawa pendekatan yang mudah dan elegan untuk pengkomputeran di mana setiap program adalah satu ungkapan OPN, mendapati penerusannya.

Satu kalkulator masa dengan RPN adalah popular, dan sesetengah orang masih memberikan mereka keutamaan. Selain itu, mereka membangunkan bahasa timbunan berorientasikan, seperti Forth. Hari ini ia adalah sedikit digunakan, tetapi masih nostalgia daripada pengguna bekas.

Jadi apa yang jenaka makna tentang Reverse Poland sosej?

Jika kita menganggap bahawa pengendali sosej, notasi memasang di antara, ia perlu berada dalam roll seperti dalam hot dog konvensional. The RPN terletak betul-betul di kedua-dua bahagian mendapatkan therebetween bersedia selepas pengiraan. Sekarang datang bahagian yang sukar - mustard. Dia sudah pada sosej, t. E. Sudah dikira sebagai pengendali unari. Adalah dipercayai bahawa mustard juga perlu ditunjukkan sebagai uncalculated dan oleh itu perlu dipindahkan ke kanan sosej ... Tetapi ia adalah mungkin, ini akan memerlukan timbunan terlalu besar ...