L'albero delle espressioni è un albero utilizzato per rappresentare le varie espressioni. La struttura dati ad albero viene utilizzata per rappresentare le istruzioni espressive. In questo albero, il nodo interno denota sempre gli operatori.
- I nodi foglia indicano sempre gli operandi.
- Le operazioni vengono sempre eseguite su questi operandi.
- L'operatore presente nella profondità dell'albero ha sempre la massima priorità.
- L'operatore che si trova poco in profondità nell'albero ha sempre la priorità più bassa rispetto agli operatori che si trovano in profondità.
- L'operando sarà sempre presente ad una profondità dell'albero; quindi è considerato il massima priorità tra tutti gli operatori
- In sintesi possiamo riassumerlo come il valore presente alla profondità dell'albero ha la massima priorità rispetto agli altri operatori presenti in cima all'albero.
- L'utilizzo principale di questi alberi delle espressioni è l'utilizzo valutare, analizzare E modificare le varie espressioni.
- Viene utilizzato anche per scoprire l'associatività di ciascun operatore nell'espressione.
- Ad esempio, l'operatore + è associativo a sinistra e / è associativo a destra.
- Il dilemma di questa associatività è stato risolto utilizzando gli alberi delle espressioni.
- Questi alberi delle espressioni sono formati utilizzando una grammatica libera dal contesto.
- Abbiamo associato una regola nelle grammatiche libere dal contesto davanti ad ogni produzione grammaticale.
- Queste regole sono note anche come regole semantiche e, utilizzando queste regole semantiche, possiamo facilmente costruire alberi delle espressioni.
- È una delle parti principali della progettazione del compilatore e appartiene alla fase di analisi semantica.
- In questa analisi semantica, utilizzeremo le traduzioni guidate dalla sintassi e, sotto forma di output, produrremo l'albero di analisi annotato.
- Un albero di analisi annotato non è altro che la semplice analisi associata all'attributo type e a ciascuna regola di produzione.
- L'obiettivo principale dell'utilizzo degli alberi delle espressioni è creare espressioni complesse che possano essere facilmente valutate utilizzando questi alberi delle espressioni.
- È immutabile e, una volta creato un albero delle espressioni, non possiamo cambiarlo o modificarlo ulteriormente.
- Per apportare ulteriori modifiche, è necessario costruire interamente il nuovo albero delle espressioni.
- Viene anche utilizzato per risolvere la valutazione delle espressioni suffisso, prefisso e infisso.
Gli alberi delle espressioni svolgono un ruolo molto importante nel rappresentare il file livello linguistico codice sotto forma di dati, che vengono memorizzati principalmente nella struttura ad albero. Viene utilizzato anche nella rappresentazione della memoria del lambda espressione. Utilizzando la struttura dati ad albero, possiamo esprimere l'espressione lambda in modo più trasparente ed esplicito. Viene creato innanzitutto per convertire il segmento di codice nel segmento di dati in modo che l'espressione possa essere facilmente valutata.
L'albero delle espressioni è un albero binario in cui ogni nodo esterno o foglia corrisponde all'operando e ogni nodo interno o padre corrisponde agli operatori, quindi ad esempio l'albero delle espressioni per 7 + ((1+8)*3) sarebbe:
Sia S l'albero delle espressioni
Se S non è nullo, allora
Se S.value è un operando, allora
Restituisce valore S
x = risolvi(S.sinistra)
y = risolvi(S.destra)
Restituisce calcolo(x, y, S.valore)
Nell'esempio sopra, l'albero delle espressioni utilizzava una grammatica libera dal contesto.
Abbiamo alcune produzioni associate ad alcune regole di produzione in questa grammatica, conosciute principalmente come regole semantiche . Possiamo definire la produzione del risultato dalle corrispondenti regole di produzione utilizzando queste regole semantiche. Qui abbiamo utilizzato il parametro value, che calcolerà il risultato e lo riporterà al simbolo iniziale della grammatica. S.left calcolerà il figlio sinistro del nodo e, analogamente, il figlio destro del nodo può essere calcolato utilizzando il parametro S.right.
Utilizzo dell'albero delle espressioni
- L'obiettivo principale dell'utilizzo degli alberi delle espressioni è creare espressioni complesse che possano essere facilmente valutate utilizzando questi alberi delle espressioni.
- Viene utilizzato anche per scoprire l'associatività di ciascun operatore nell'espressione.
- Viene anche utilizzato per risolvere la valutazione delle espressioni suffisso, prefisso e infisso.
Implementazione di un albero delle espressioni
Per implementare l'albero delle espressioni e scrivere il suo programma, ci verrà richiesto di utilizzare una struttura dati stack.
Poiché sappiamo che lo stack si basa sul principio LIFO last in first out, l'elemento dati inserito di recente nello stack viene estratto ogni volta che è necessario. Per la sua implementazione vengono utilizzate le due operazioni principali dello stack, push e pop. Utilizzando l'operazione push, inseriremo l'elemento dati nello stack e, utilizzando l'operazione pop, rimuoveremo l'elemento dati dallo stack.
Principali funzioni dello stack nell'implementazione dell'albero delle espressioni:
Prima di tutto, eseguiremo la scansione dell'espressione data da sinistra a destra, quindi controlleremo uno per uno il carattere identificato,
- Se un carattere scansionato è un operando, applicheremo l'operazione push e lo inseriremo nello stack.
- Se un carattere scansionato è un operatore, applicheremo l'operazione pop al suo interno per rimuovere i due valori dallo stack per renderli figli, dopodiché reimposteremo il nodo genitore corrente nello stack.
Implementazione dell'albero delle espressioni nel linguaggio di programmazione C
// 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> L'output del programma sopra è:
X + Y * Z / W
Implementazione dell'albero delle espressioni nel linguaggio di programmazione C++
// 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> L'output del programma sopra è:
X + Y * Z / W
Implementazione dell'albero delle espressioni nel linguaggio di programmazione Java
// 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>