İfade ağacı, çeşitli ifadeleri temsil etmek için kullanılan bir ağaçtır. Ağaç veri yapısı ifadesel ifadeleri temsil etmek için kullanılır. Bu ağaçta iç düğüm her zaman operatörleri belirtir.
- Yaprak düğümler her zaman işlenenleri belirtir.
- İşlemler her zaman bu işlenenler üzerinde gerçekleştirilir.
- Ağacın derinliklerinde bulunan operatör her zaman en yüksek önceliğe sahiptir.
- Ağacın derinliklerinde fazla bulunmayan operatör, derinlikte yatan operatörlere göre her zaman en düşük önceliğe sahiptir.
- İşlenen her zaman ağacın derinliklerinde yer alacaktır; bu nedenle kabul edilir en yüksek öncelik tüm operatörler arasında.
- Kısaca ağacın derinliğinde bulunan değerin, ağacın tepesinde bulunan diğer operatörlere göre en yüksek önceliğe sahip olması şeklinde özetleyebiliriz.
- Bu ifade ağaçlarının ana kullanımı, değerlendirmek, analiz etmek Ve değiştirmek çeşitli ifadeler.
- Ayrıca ifadedeki her operatörün ilişkilendirilebilirliğini bulmak için de kullanılır.
- Örneğin, + operatörü sol ilişkiseldir ve / operatörü sağ ilişkiseldir.
- Bu çağrışımsallığın ikilemi ifade ağaçları kullanılarak giderilmiştir.
- Bu ifade ağaçları bağlamdan bağımsız bir dilbilgisi kullanılarak oluşturulur.
- Bağlamdan bağımsız dilbilgilerinde her dilbilgisi üretiminin önüne bir kural bağladık.
- Bu kurallara anlam kuralları da denir ve bu anlam kurallarını kullanarak ifade ağaçlarını kolayca oluşturabiliriz.
- Derleyici tasarımının ana parçalarından biridir ve anlamsal analiz aşamasına aittir.
- Bu semantik analizde sözdizimine yönelik çevirileri kullanacağız ve çıktı biçiminde açıklamalı ayrıştırma ağacını üreteceğiz.
- Açıklamalı bir ayrıştırma ağacı, type özelliği ve her üretim kuralıyla ilişkili basit ayrıştırmadan başka bir şey değildir.
- İfade ağaçlarını kullanmanın temel amacı karmaşık ifadeler oluşturmaktır ve bu ifade ağaçları kullanılarak kolaylıkla değerlendirilebilir.
- Değiştirilemez ve bir ifade ağacı oluşturduğumuzda onu değiştiremeyiz veya daha fazla değiştiremeyiz.
- Daha fazla değişiklik yapabilmek için yeni ifade ağacının bütünüyle oluşturulması gerekmektedir.
- Ayrıca son ek, önek ve iç ek ifade değerlendirmesini çözmek için de kullanılır.
İfade ağaçları, ifadeyi temsil etmede çok önemli bir rol oynar. Dil seviyesi esas olarak ağaç benzeri yapıda depolanan veri biçimindeki kod. Aynı zamanda hafıza temsilinde de kullanılır. lambda ifade. Ağaç veri yapısını kullanarak lambda ifadesini daha şeffaf ve açık bir şekilde ifade edebiliriz. İfadenin kolayca değerlendirilebilmesi için öncelikle kod segmentini veri segmentine dönüştürmek için oluşturulur.
İfade ağacı, her harici veya yaprak düğümün işlenene karşılık geldiği ve her dahili veya ana düğümün operatörlere karşılık geldiği bir ikili ağaçtır, dolayısıyla örneğin 7 + ((1+8)*3) için ifade ağacı şu şekilde olacaktır:
İfade ağacı S olsun
S boş değilse, o zaman
S.value bir işlenen ise, o zaman
S.değerini döndür
x = çöz(S.sol)
y = çöz(S.sağ)
Dönüş hesaplaması(x, y, S.değeri)
Yukarıdaki örnekte, ifade ağacı bağlamdan bağımsız dilbilgisi kullanmıştır.
Bu gramerde bazı üretim kurallarıyla ilişkili, esas olarak şu şekilde bilinen bazı üretimlerimiz var: anlam kuralları . Bu anlamsal kuralları kullanarak karşılık gelen üretim kurallarından sonuç üretmeyi tanımlayabiliriz. Burada sonucu hesaplayacak ve dilbilgisinin başlangıç sembolüne döndürecek değer parametresini kullandık. S.left, düğümün sol çocuğunu hesaplayacaktır ve benzer şekilde düğümün sağ çocuğu da S.right parametresi kullanılarak hesaplanabilir.
İfade ağacının kullanımı
- İfade ağaçlarını kullanmanın temel amacı karmaşık ifadeler oluşturmaktır ve bu ifade ağaçları kullanılarak kolaylıkla değerlendirilebilir.
- Ayrıca ifadedeki her operatörün ilişkilendirilebilirliğini bulmak için de kullanılır.
- Ayrıca son ek, önek ve iç ek ifade değerlendirmesini çözmek için de kullanılır.
İfade ağacının uygulanması
İfade ağacını uygulamak ve programını yazmak için yığın veri yapısını kullanmamız gerekecek.
Yığın son giren ilk çıkar LIFO prensibine dayandığını bildiğimiz için yığına yeni eklenen veri elemanı gerektiğinde dışarı atılmıştır. Uygulanması için yığının iki ana işlemi olan push ve pop kullanılır. Push işlemini kullanarak veri öğesini yığının içine iteceğiz ve pop işlemini kullanarak veri öğesini yığından kaldıracağız.
İfade ağacı uygulamasında yığının ana işlevleri:
Öncelikle verilen ifadeyi soldan sağa doğru tarayacağız, ardından tanımlanan karakteri tek tek kontrol edeceğiz,
- Taranan karakter bir işlenen ise, push işlemini uygulayacağız ve onu yığının içine iteceğiz.
- Taranan bir karakter bir operatörse, iki değeri yığından kaldırmak ve onları alt öğe yapmak için pop işlemini uygulayacağız ve ardından mevcut ana düğümü yığına geri iteceğiz.
İfade ağacının C Programlama dilinde uygulanması
// C program for expression tree implementation #include #include /* The below structure node is defined as a node of a binary tree consists of left child and the right child, along with the pointer next which points to the next node */ struct node { char info ; struct node* l ; struct node* r ; struct node* nxt ; }; struct node *head=NULL; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newnode(char data) { struct node* node = (struct node*) malloc ( sizeof ( struct node ) ) ; node->info = data ; node->l = NULL ; node->r = NULL ; node->nxt = NULL ; return ( node ) ; } void Inorder(struct node* node) { if ( node == NULL) return ; else { /* first recur on left child */ Inorder ( node->l ) ; /* then print the data of node */ printf ( '%c ' , node->info ) ; /* now recur on right child */ Inorder ( node->r ) ; } } void push ( struct node* x ) { if ( head == NULL ) head = x ; else { ( x )->nxt = head ; head = x ; } // struct node* temp ; // while ( temp != NULL ) // { // printf ( ' %c ' , temp->info ) ; // temp = temp->nxt ; // } } struct node* pop() { // Poping out the top most [pointed with head] element struct node* n = head ; head = head->nxt ; return n ; } int main() { char t[] = { 'X' , 'Y' , 'Z' , '*' , '+' , 'W' , '/' } ; int n = sizeof(t) / sizeof(t[0]) ; int i ; struct node *p , *q , *s ; for ( i = 0 ; i <n ; i++ ) { if read character is operator then popping two other elements from stack and making a binary tree ( t[i]="=" '+' || '-' '*' ' '^' s="newnode" t [ i ] p="pop()" q="pop()" s->l = q ; s->r = p; push(s); } else { s = newnode ( t [ i ] ) ; push ( s ) ; } } printf ( ' The Inorder Traversal of Expression Tree: ' ) ; Inorder ( s ) ; return 0 ; } </n> Yukarıdaki programın çıktısı:
X + Y * Z / W
İfade ağacının C++ Programlama dilinde uygulanması
// C++ program for expression tree #include using namespace std ; /* The below class node is defined as a node of a binary tree consists of left child and the right child, along with the pointer next which points to the next node */ class node { public: char info ; node* l ; node* r ; node* nxt = NULL ; node ( char c ) { this->info = c ; l = NULL ; r = NULL ; } node() { l = NULL ; r = NULL ; } friend class Stack ; friend class tree ; } ; class Stack { node* head = NULL ; public: void push ( node* ) ; node* pop() ; friend class tree ; } ; class tree { public: void inorder ( node* x ) { // cout<<'tree in inorder traversal is: '<l ) ; cout <info <r } void stack::push( node* x { if ( head="=" null we are inserting here nodes at the top of stack [following lifo principle] else x->nxt = head ; head = x ; } } node* Stack::pop() { // Poping out the top most [ pointed with head ] element node* p = head ; head = head->nxt ; return p ; } int main() { string str = 'XYZ*+W/' ; // If you wish take input from user: //cout << 'Insert Postorder Expression: ' <> s; Stack s ; tree t ; node *p, *q, *re; int n = str.length() ; for ( int i = 0 ; i <n ; i++ ) { if ( str[ i ]="=" '+' || '-' '*' ' '^') re="new" node( str[i] p="s.pop()" q="s.pop()" re->l = q ; re->r = p ; s.push(re) ; } else { re = new node( str[ i ] ) ; s.push(re) ; } } cout << ' The Inorder Traversal of Expression Tree: ' ; t.inorder(re) ; return 0 ; } </n></'tree> Yukarıdaki programın çıktısı:
X + Y * Z / W
İfade ağacının Java Programlama dilinde uygulanması
// Java program for expression tree import java.util.* ; /* The below class node is defined as a node of a binary tree consists of left child and the right child, along with the pointer next which points to the next node */ class Node { char info ; Node l , r ; public Node(char data) { this.info = data ; l = null ; r = null ; } } public class Main { public static boolean isOperator ( char ch ) { if ( ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^' ) { return true ; } return false ; } public static Node Tree ( String postfix ) { Stack st = new Stack(); Node t1,t2,temp ; for ( int i = 0 ; i <p> <strong>The output of the above program is:</strong> </p> <pre> X + Y * Z / W </pre> <hr>