Saat menulis kode, kadang -kadang kita menghadapi situasi di mana kita perlu mengurai empat ekspresi aritmatika sendiri. Artikel ini secara singkat memperkenalkan penggunaan JavaScript untuk mengimplementasikan penguraian empat ekspresi aritmatika sederhana.
1. Akrab dengan konsepnya
Notasi infiks (atau notasi infiks) adalah metode representasi rumus aritmatika atau logis umum. Operator berada di tengah operan dalam bentuk infiks (Contoh: 3 + 4). Artinya, kami menggunakan ekspresi aritmatika yang paling umum digunakan. Ekspresi infix lebih mudah dipahami manusia, tetapi tidak mudah untuk analisis komputer.
Notasi Polandia terbalik (RPN, atau Notasi Polandia terbalik) adalah metode ekspresi matematika yang diperkenalkan oleh ahli matematika Polandia Jan Vukasevich pada tahun 1920. Dalam notasi Polandia terbalik, semua operator ditempatkan di belakang operan, sehingga juga disebut notasi akhiran. Notasi Polandia terbalik tidak memerlukan tanda kurung untuk mengidentifikasi prioritas operator. Notasi Polandia terbalik mudah untuk menggunakan struktur tumpukan untuk mengurai dan menghitung ekspresi, jadi di sini kita menguraikan empat ekspresi elemen, yang pertama kali dikonversi dari ekspresi infix ke ekspresi polesan terbalik. Kemudian hitung nilainya.
2. Proses Konversi
Konversi ekspresi infix menjadi ekspresi akhiran (algoritma bidang penjadwalan)
1. Masukkan antrian dan buat tanda
2. Jika tanda adalah angka, tambahkan ke antrian output
3. Jika itu adalah operator (+-*/), bandingkan dengan operator di bagian atas tumpukan di tumpukan output. Jika prioritas kurang dari atau sama dengan operator di bagian atas tumpukan, pop up operator di bagian atas tumpukan dan tambahkan ke antrian output (loop sampai kondisi di atas tidak terpenuhi), dan akhirnya mendorong operator ke tumpukan.
4. Jika itu adalah braket kiri, dorong ke dalam tumpukan
5. Jika itu adalah braket yang dekat, operator terus muncul dari tumpukan dan ditambahkan ke antrian output, dan tahu bahwa elemen di bagian atas tumpukan adalah braket kiri. Braket kiri muncul dan tidak menambahkan antrian output. Jika tidak ada braket kiri yang ditemukan, itu berarti bahwa kurung dalam ekspresi asli asimetris dan ada kesalahan.
6. Jika antrian input kosong dan masih ada operator di tumpukan, jika operator di bagian atas tumpukan adalah braket kiri, itu berarti bahwa ekspresi asli memiliki kurung yang tidak cocok. Masukkan operator di tumpukan satu per satu dan tambahkan ke antrian output.
7. Selesai
3. Konversi implementasi kode
fungsi isoperator (value) {var operatorString = "+-*/()"; return operatorString.indexof (value)> -1} function getPrioraty (value) {switch (value) {case '+': case '-': return 1; case '*: case'/': return 2; default: return 0;}}}}}}}}}}}}}: getPrioraty (o2);} fungsi dal2rpn (exp) {var inputStack = []; var outputStack = []; var outputqueue = []; untuk (var i = 0, len = exp.length; i <len; i ++) {var cur = ixt [i]; if (cur! = 'len; i ++) {var cur = ixt [i]; if (cur! =' len; i ++) {var cur = ix [i]; if (cur! = 'len; i ++) {var cur = ix [i]; if (cur! satu'); while (inputstack.length> 0) {var cur = inputStack.shift (); if (isOperator (cur)) {if (cur == '(') {outputStack.push (cur);} lain jika (cur == ')') {var po = outputStack.pop (); while (po! = '(' && outputStack.length> 0) {outputqueue.push (po); po = outputStack.pop ();} if (po! = '(') {throw "error: outputed () output. 0) {outputqueue.push (outputStack.pop ());} outputStack.push (cur);}} else {outputqueue.push (angka baru (cur));}} console.log ('Langkah dua'); if (outputStack.length> 0) {if (output '); iPut. outputStack [outputStack.length - 1] == '(') {throw "error: unmatched ()";} while (outputStack.length> 0) {outputqueue.push (outputStack.pop ());}} konsol.log ('langkah tiga'); outputqueue outputqueue. 2 ')); console.log (dal2rpn (' 1 + 2 + 3 ')); konsol.log (dal2rpn (' 1 + 2 * 3 ')); Console.log (dal2rpn (' 1 + 2 * 3 - 4 /5 ')); konsol. 2) * (3 - 4) / 5 ')); console.log (dal2rpn (' (1 + 2) * ((3 - 4) / 5) '));4. Evaluasi Ekspresi Polandia Terbalik
1. Pop up tanda dari antrian input
2. Jika itu operan, tambahkan ke tumpukan output
3. Jika itu adalah operator, pop dua operan dari tumpukan output dan hitung, dan dorong nilai yang dihitung ke dalam tumpukan output.
4. Operasi Loop. Jika antrian input kosong dan hanya ada satu angka pada tumpukan output, nomor ini adalah hasilnya, jika tidak, akan ada operan yang tidak perlu.
5. Hitung Kode
fungsi evalrpn (rpnqueue) {var outputStack = []; while (rpnqueue.length> 0) {var cur = rpnqueue.shift (); if (! isoperator (cur)) {outputStack.push (cur);} else {if (outputStack.length <2) outputStack.pop (); var fir = outputStack.pop (); outputStack.push (getResult (fir, sec, cur));}} if (outputStack.length! = 1) {lempar "ekspresi unvalid";} else {outputStack [0];}}6. Kesimpulan
Representasi Polandia terbalik tidak digunakan ketika Anda pertama kali bersentuhan dengannya, tetapi setelah terbiasa dengan itu, Anda akan menemukan bahwa idenya sebenarnya sangat sederhana, tidak seperti representasi infix, yang memiliki berbagai prioritas, dan ada tanda kurung, yang merupakan logika yang sangat merepotkan. Representasi Polandia terbalik relatif ringkas, dan tidak perlu mempertimbangkan prioritas sama sekali, dan tidak perlu menggunakan kurung, dan kurung dan kawat gigi untuk mengganggu situasi.