RPN: algoritma, metode dan contoh

RPN sekali membentuk dasar dari seorang programmer komputer di dunia. Hari ini tidak begitu dikenal. Oleh karena itu, ilustrasi komik, yang menggambarkan "reverse" Polandia sosis gulungan luar, masih bisa disalahpahami oleh beberapa programmer berpengetahuan. Tidak sangat baik menjelaskan lelucon, tetapi dalam kasus ini akan sepenuhnya dibenarkan.

infiks

Semua programmer, dan sebagian besar siswa akrab dengan penggunaan operator. Sebagai contoh, nilai-nilai ekspresi x + penjumlahan untuk variabel x dan y digunakan tanda plus. Kurang dikenal adalah fakta bahwa ini dipinjam dari notasi matematika, disebut notasi infix, pada kenyataannya, adalah masalah besar untuk mesin. Operator ini menerima sebagai masukan dua nilai dicatat di sisi kiri dan kanan. Dalam pemrograman notasi yang digunakan opsional dengan operasi tanda-tanda. Sebagai contoh, x + y dapat ditulis sebagai fungsi dari lipatan (x, y), dimana compiler dan akhirnya mengubah notasi infix. Namun, semua orang tahu matematika terlalu baik untuk tidak menggunakan ekspresi aritmatika, yang membentuk semacam internal yang mini-bahasa di hampir setiap bahasa pemrograman.

rumus penerjemah

Pertama benar-benar sukses bahasa pemrograman Fortran telah menjadi begitu sebagian besar karena ekspresi aritmatika (yaitu rumus ..) Ini dikonversi (broadcast) dalam kode, maka nama itu - Formula Translation. Sebelum itu, mereka harus menulis, misalnya, dilipat dalam bentuk fungsi (dan berkembang biak (b, c)). Dalam masalah COBOL menerapkan rumus konversi otomatis dianggap sangat sulit karena programmer harus menulis hal-hal seperti Add A Untuk B Mutliply By C.

Apa yang salah dengan infiks?

Masalahnya adalah, bahwa operator memiliki sifat seperti didahulukan dan associativity. Karena itu, definisi fungsi infiks menjadi tugas non-sepele. Misalnya, perkalian memiliki hak lebih tinggi dari penambahan atau pengurangan, yang berarti bahwa ekspresi 2 + 3 * 4 tidak sama dengan jumlah dari 2 dan 3, dikalikan dengan 4, karena akan menjadi dalam kinerja operator dari kiri ke kanan. Bahkan, kalikan 3 dengan 4 dan menambahkan 2. Contoh ini menggambarkan bahwa perhitungan ekspresi infix sering membutuhkan perubahan dalam urutan operator dan operan. Selain itu, perlu untuk menggunakan kawat gigi untuk melihat notasi lebih jelas. Sebagai contoh, (2 + 3) * (4 + 5) tidak dapat ditulis tanpa tanda kurung, karena 2 + 3 * 4 + 5 berarti bahwa Anda harus kalikan 3 dengan 4 dan tambahkan 2 dan 5.

Urutan di mana Anda ingin menghitung operator membutuhkan lama mengingat. Karena itu, siswa yang mulai belajar aritmatika, sering mendapatkan hasil yang salah, bahkan jika operasi yang sebenarnya dilakukan dengan benar. Hal ini diperlukan untuk mengajarkan urutan laporan tindakan dengan hati. Pertama, tindakan harus dilakukan dalam tanda kurung, maka perkalian dan pembagian, dan akhirnya penambahan dan pengurangan. Tapi ada cara lain untuk menulis ekspresi matematika sebagai notasi infix hanya salah satu kemungkinan "bahasa kecil" yang dapat ditambahkan ke lebih.

Awalan dan postfix notasi

Dua alternatif yang paling terkenal adalah untuk merekam operator sebelum atau setelah operan nya. Mereka dikenal sebagai awalan dan postfix notasi. Ahli logika Yan Lukasevich menemukan yang pertama pada tahun 1920. Dia tinggal di Polandia, sehingga catatan disebut Polandia. versi Postfix, masing-masing, yang disebut reverse Polandia Notasi (ARF). Satu-satunya perbedaan antara kedua metode ini adalah arah di mana untuk membaca catatan (dari kiri ke kanan atau kanan ke kiri), sehingga cukup untuk mempertimbangkan secara detail hanya salah satu dari mereka. Operator OPN ditulis setelah operan nya. Dengan demikian, ekspresi AB + merupakan contoh RPN untuk A + B.

Unlimited jumlah operan

Keuntungan langsung dari notasi adalah bahwa hal itu merangkum operator n-adic dan notasi infiks benar-benar hanya bekerja dengan dua operan, t. E. Apakah inheren hanya cocok untuk operasi biner. Misalnya, ABC @ adalah ekspresi Polandia terbalik menggunakan tanda triadic yang merupakan nilai maksimum dari A, B dan C. Dalam hal ini operator bertindak di sebelah kiri dari tiga operan sendiri dan sesuai dengan fungsi panggilan @ (A, B, C). Jika Anda mencoba untuk menulis simbol @ sebagai infix, seperti A @ SM atau sesuatu seperti itu, menjadi jelas bahwa itu hanya tidak bekerja.

Prioritas yang diberikan oleh perintah

RPN memiliki keuntungan lain di bahwa prioritas operator dapat diwakili oleh urutan penampilan mereka. Pada saat yang sama tidak perlu kawat gigi, meskipun mereka dapat dimasukkan sebagai operasi karakter untuk memfasilitasi konversi dari notasi infix. Misalnya, AB + C * - ambigu setara (A + B) * C, sehingga perkalian tidak dapat dihitung sampai penambahan dilakukan, yang memberikan operan kedua untuk perkalian. Artinya, jika dihitung AB + C * oleh salah satu operator pada satu waktu, kita mendapatkan AB + C * -> (AB +) * C -> (A + B) * C.

algoritma perhitungan

Operator OPN tampak sama dengan fungsi yang mengambil sebagai argumen dua nilai yang tertulis di kirinya. Selain itu, itu adalah notasi alami untuk digunakan dalam bahasa pemrograman, seperti cara perhitungannya sesuai dengan operasi stack dan kebutuhan untuk parsing dihilangkan. Sebagai contoh, arester dalam ekspresi 5 + 6 * 7 akan muncul sebagai 5, 6, 7 *, +, dan dapat dihitung hanya dengan pemindaian dari kiri ke kanan dan menulis nilai-nilai dalam tumpukan. Setiap kali tanda umum dari operasi, yang dipilih oleh unsur atas 2 dari memori komputer, operator yang digunakan dan hasilnya kembali ke memori. Ketika hasil akhir dari ekspresi perhitungan akan berada di atas tumpukan.

Sebagai contoh:

• S = () 5, 6, 7, *, + 5 ditempatkan di stack.
• S = (5) 6, 7, *, + 6 ditempatkan pada stack.
• S = (5, 6), 7 *, 7 + menempatkan tumpukan.
• S = (5, 6, 7), * 2 + memilih nilai-nilai dari stack, penggunaan * dan menempatkan hasilnya dalam stack.
• S = (5, 6 * 7) = (5, 42) + 2 nilai yang dipilih dari tumpukan, untuk menerapkan + dan menempatkan hasilnya dalam stack.
• S = (5 + 42) = (47) perhitungan selesai, hasilnya disimpan di atas tumpukan.

algoritma ini dapat diperiksa RPN berulang kali, tapi setiap kali ia akan bekerja, tidak peduli bagaimana kompleks ekspresi aritmatika.

OPN dan tumpukan terkait erat. Contoh ini menunjukkan bagaimana menggunakan memori untuk menghitung nilai notasi Polandia terbalik. Kurang jelas adalah bahwa Anda dapat menggunakan stack, mengubah ekspresi infix standar pada gagal ginjal akut.

Contoh bahasa pemrograman

Pascal RPN menyadari seperti ini (menunjukkan bagian dari program).

Untuk membaca angka dan operator dalam siklus yang disebut prosedur, yang menentukan apakah nomor atau tanda tanda operasi. Dalam kasus pertama, nilai yang disimpan dalam stack, dan yang kedua dari dua angka tumpukan atas yang sesuai tindakan dilakukan dan hasilnya disimpan.

toktype: = num;

membaca (s);

jika c di [ '+', '-', '*', '/'] kemudian mulai

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

jika cn = '' kemudian

kasus

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

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

akhir

lain mulai

jika = '-' kemudian sgn: = -1 lain error: = c <> '+';

dengan: = cn

akhir

berakhir;

jika (tidak error) dan (toktype = num) maka getNumber;

jika toktype <> num kemudian mulai

y = pop; x: = pop;

jika tidak error maka

Kasus toktype dari

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

akhir

dorongan (z);

C-implementasi RPN (ditampilkan bagian dari program):

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

a = strtod (s, & e);

if (e> s) dorongan (a);

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

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

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

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

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

rpnop #undef

}

implementasi hardware

Pada hari-hari, ketika teknologi komputer sangat mahal, hal itu dianggap ide yang baik untuk memaksa orang untuk menggunakan surge arrester. Pada tahun 1960-ies., Seperti sekarang, adalah mungkin untuk membeli kalkulator, yang bekerja dalam notasi Polandia terbalik. Untuk menambahkan 2 dan 3 dari mereka harus memasukkan 2, kemudian 3, dan tekan tombol "plus". Pada pandangan pertama, operan masukan ke operator tampak rumit dan sulit untuk diingat, tapi setelah beberapa saat beberapa kecanduan cara berpikir dan tidak bisa mengerti mengapa orang lain bersikeras infix bodoh, yang begitu rumit dan begitu terbatas.

perusahaan Burroughs bahkan membangun sebuah mainframe, yang tidak memiliki memori lain, kecuali tumpukan. Satu-satunya hal yang membuat mesin - menerapkan algoritma dan metode RPN untuk tumpukan pusat. Semua usaha dianggap sebagai operator arrester, yang berlaku untuk nilai-nilai n atas. Sebagai contoh, tim mengambil Kembali Alamat dari puncak stack, dan sebagainya. D. Arsitektur seperti mesin sederhana, tetapi tidak cukup cepat untuk bersaing dengan arsitektur yang lebih umum. Namun, banyak masih menyesal fakta bahwa pendekatan seperti yang sederhana dan elegan untuk komputasi di mana setiap program adalah ekspresi OPN, ditemukan kelanjutan.

Suatu kali kalkulator dengan RPN yang populer, dan beberapa orang masih memberi mereka preferensi. Selain itu, mereka mengembangkan bahasa tumpukan-berorientasi, seperti Forth. Hari ini adalah sedikit digunakan, tapi masih nostalgia dari mantan pengguna nya.

Jadi apa arti lelucon tentang sosis Reverse Polish?

Jika kita berasumsi bahwa operator sosis, notasi infix, itu harus dalam gulungan seperti pada hot dog konvensional. RPN terletak tepat di dua bagian mendapatkan diantaranya siap setelah perhitungan. Sekarang sampai pada bagian yang sulit - mustard. Dia sudah di sosis, t. E. Sudah dihitung sebagai operator unary. Hal ini diyakini bahwa mustard juga harus ditampilkan sebagai uncalculated dan karena itu harus dipindahkan ke kanan sosis ... Tetapi adalah mungkin, ini akan membutuhkan tumpukan terlalu besar ...