Veri Yapısı - İfade Ayrıştırma

Aritmetik ifade yazmanın yolu, notation. Bir aritmetik ifade, üç farklı ancak eşdeğer gösterimde, yani bir ifadenin özünü veya çıktısını değiştirmeden yazılabilir. Bu gösterimler -

  • Infix Notasyonu
  • Önek (Lehçe) Gösterimi
  • Postfix (Reverse-Polish) Notasyonu

Bu gösterimler operatörü ifadede nasıl kullandıkları olarak adlandırılır. Aynısını burada da bu bölümde öğreneceğiz.

Infix Notasyonu

İfade yazıyoruz infix gösterim, örneğin a - b + c, operatörlerin kullanıldığı yerlerde in- işlenenler arasında. Biz insanlar için infix notasyonunda okumak, yazmak ve konuşmak kolaydır, ancak aynı şey bilgisayar cihazlarında iyi gitmez. Enfix gösterimini işlemek için bir algoritma, zaman ve alan tüketimi açısından zor ve maliyetli olabilir.

Önek Gösterimi

Bu gösterimde operatör prefixişlenenlere ed, yani işleç işlenenlerin önüne yazılır. Örneğin,+ab. Bu, infix gösterimine eşdeğerdira + b. Önek gösterimi aynı zamandaPolish Notation.

Sonek Gösterimi

Bu gösterim stili olarak bilinir Reversed Polish Notation. Bu gösterim stilinde, operatörpostfixişlenenlere, yani operatör, işlenenlerden sonra yazılır. Örneğin,ab+. Bu, infix gösterimine eşdeğerdira + b.

Aşağıdaki tablo kısaca üç gösterimdeki farkı göstermeye çalışır -

Sr.No. Infix Notasyonu Önek Gösterimi Sonek Gösterimi
1 a + b + ab ab +
2 (a + b) ∗ c ∗ + abc ab + c ∗
3 bir ∗ (b + c) ∗ a + bc abc + ∗
4 a / b + c / d + / ab / cd ab / cd / +
5 (bir + b) ∗ (c + d) ∗ + ab + cd ab + cd + ∗
6 ((a + b) ∗ c) - d - ∗ + abcd ab + c ∗ d -

İfadeleri Ayrıştırma

Tartıştığımız gibi, infix notasyonlarını ayrıştırmak için bir algoritma veya program tasarlamanın çok verimli bir yolu değildir. Bunun yerine, bu ek gösterimleri önce sonek veya önek gösterimlerine dönüştürülür ve sonra hesaplanır.

Herhangi bir aritmetik ifadeyi ayrıştırmak için, operatör önceliğine ve ilişkiselliğine de dikkat etmemiz gerekir.

Öncelik

Bir işlenen iki farklı operatör arasında olduğunda, hangi operatör önce işleneni alacaksa, bir operatörün diğerlerine göre önceliğine göre karar verilir. Örneğin -

Çarpma işlemi toplamaya göre önceliğe sahip olduğundan, önce b * c değerlendirilecektir. Operatör önceliği tablosu daha sonra sağlanır.

İlişkisellik

İlişkilendirme, aynı önceliğe sahip operatörlerin bir ifadede göründüğü kuralı tanımlar. Örneğin, a + b - c ifadesinde hem + hem de - aynı önceliğe sahiptir, daha sonra ifadenin hangi kısmının önce değerlendirileceği, bu operatörlerin ilişkilendirilebilirliği ile belirlenir. Burada hem + hem de - ilişkisel bırakılmıştır, bu nedenle ifade şu şekilde değerlendirilecektir:(a + b) − c.

Öncelik ve ilişkilendirilebilirlik, bir ifadenin değerlendirme sırasını belirler. Aşağıda bir operatör önceliği ve ilişkilendirilebilirlik tablosu verilmiştir (en yüksekten en düşüğe) -

Sr.No. Şebeke Öncelik İlişkisellik
1 Üs alma ^ En yüksek Doğru İlişkilendirme
2 Çarpma (∗) ve Bölme (/) İkinci En Yüksek Sol İlişkili
3 Toplama (+) ve Çıkarma (-) En düşük Sol İlişkili

Yukarıdaki tablo operatörlerin varsayılan davranışlarını göstermektedir. İfade değerlendirmesinde herhangi bir zamanda, sıra parantez kullanılarak değiştirilebilir. Örneğin -

İçinde a + b*cifade kısmı b*cönce çarpma, toplamaya göre öncelikli olacak şekilde değerlendirilecektir. Burada parantez kullanıyoruza + b ilk olarak değerlendirilecek (a + b)*c.

Sonek Değerlendirme Algoritması

Şimdi sonek gösteriminin nasıl değerlendirileceğine dair algoritmaya bakacağız -

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

Uygulamayı C programlama dilinde görmek için lütfen buraya tıklayın .