Struktur Data - Penguraian Ekspresi

Cara penulisan ekspresi aritmatika dikenal sebagai a notation. Ekspresi aritmatika dapat ditulis dalam tiga notasi yang berbeda tetapi ekuivalen, yaitu tanpa mengubah esensi atau keluaran ekspresi. Notasi ini adalah -

• Notasi Infix
• Notasi Awalan (Polandia)
• Notasi Postfix (Reverse-Polish)

Notasi ini dinamai seperti bagaimana mereka menggunakan operator dalam ekspresi. Kita akan mempelajari hal yang sama di sini di bab ini.

Notasi Infix

Kami menulis ekspresi dalam infix notasi, misalnya a - b + c, di mana operator digunakan in-di antara operan. Mudah bagi kita manusia untuk membaca, menulis, dan berbicara dalam notasi infix tetapi hal yang sama tidak berjalan baik dengan perangkat komputasi. Algoritme untuk memproses notasi infiks bisa jadi sulit dan mahal dalam hal konsumsi waktu dan ruang.

Notasi Awalan

Dalam notasi ini, operator adalah prefixed ke operan, yaitu operator ditulis di depan operan. Sebagai contoh,+ab. Ini setara dengan notasi infiksnyaa + b. Notasi prefiks juga dikenal sebagaiPolish Notation.

Notasi Postfix

Gaya notasi ini dikenal sebagai Reversed Polish Notation. Dalam gaya notasi ini, operatornya adalahpostfixed ke operan yaitu, operator ditulis setelah operan. Sebagai contoh,ab+. Ini setara dengan notasi infiksnyaa + b.

Tabel berikut secara singkat mencoba menunjukkan perbedaan di ketiga notasi -

Sr.No.	Notasi Infix	Notasi Awalan	Notasi Postfix
1	a + b	+ ab	ab +
2	(a + b) ∗ c	∗ + abc	ab + c ∗
3	a ∗ (b + c)	∗ a + bc	abc + ∗
4	a / b + c / d	+ / ab / cd	ab / cd / +
5	(a + b) ∗ (c + d)	∗ + ab + cd	ab + cd + ∗
6	((a + b) ∗ c) - d	- ∗ + abcd	ab + c ∗ d -

Ekspresi Parsing

Seperti yang telah kita diskusikan, ini bukanlah cara yang sangat efisien untuk mendesain algoritma atau program untuk mengurai notasi infiks. Sebaliknya, notasi infiks ini pertama-tama diubah menjadi postfix atau notasi awalan dan kemudian dihitung.

Untuk mengurai ekspresi aritmatika apa pun, kita perlu memperhatikan prioritas operator dan asosiativitas juga.

Hak lebih tinggi

Ketika operan berada di antara dua operator yang berbeda, operator mana yang akan mengambil operan terlebih dahulu, ditentukan oleh prioritas operator di atas yang lain. Misalnya -

Karena operasi perkalian lebih diutamakan daripada penjumlahan, b * c akan dievaluasi terlebih dahulu. Tabel prioritas operator disediakan nanti.

Asosiatif

Asosiatif mendeskripsikan aturan di mana operator dengan prioritas yang sama muncul dalam ekspresi. Misalnya, dalam ekspresi a + b - c, baik + dan - memiliki prioritas yang sama, lalu bagian ekspresi mana yang akan dievaluasi terlebih dahulu, ditentukan oleh asosiasi operator tersebut. Di sini, + dan - dibiarkan asosiatif, sehingga ekspresi akan dievaluasi sebagai(a + b) − c.

Presedensi dan asosiatif menentukan urutan evaluasi ekspresi. Berikut adalah tabel prioritas dan asosiasi operator (dari tertinggi ke terendah) -

Sr.No.	Operator	Hak lebih tinggi	Asosiatif
1	Eksponensial ^	Paling tinggi	Asosiatif Kanan
2	Perkalian (∗) & Pembagian (/)	Tertinggi Kedua	Asosiatif Kiri
3	Penjumlahan (+) & Pengurangan (-)	Terendah	Asosiatif Kiri

Tabel di atas menunjukkan perilaku default operator. Kapan pun dalam evaluasi ekspresi, urutan dapat diubah dengan menggunakan tanda kurung. Misalnya -

Di a + b*c, bagian ekspresi b*cakan dievaluasi terlebih dahulu, dengan perkalian sebagai diutamakan daripada penjumlahan. Kami di sini menggunakan tanda kurung untuka + b untuk dievaluasi terlebih dahulu, seperti (a + b)*c.

Algoritma Evaluasi Postfix

Sekarang kita akan melihat algoritma tentang bagaimana mengevaluasi notasi postfix -

Step 1 − scan the expression from left to right 
Step 2 − if it is an operand push it to stack 
Step 3 − if it is an operator pull operand from stack and perform operation 
Step 4 − store the output of step 3, back to stack 
Step 5 − scan the expression until all operands are consumed 
Step 6 − pop the stack and perform operation

Untuk melihat implementasinya dalam bahasa pemograman C, silahkan klik disini .