L'arbre d'expressió és un arbre utilitzat per representar les diverses expressions. L'estructura de dades d'arbre s'utilitza per representar les declaracions d'expressió. En aquest arbre, el node intern sempre denota els operadors.
- Els nodes fulla sempre denoten els operands.
- Les operacions es realitzen sempre sobre aquests operands.
- L'operador present a la profunditat de l'arbre sempre té la màxima prioritat.
- L'operador, que no es troba gaire a la profunditat de l'arbre, sempre té la prioritat més baixa en comparació amb els operadors que es troben a la profunditat.
- L'operand sempre es presentarà a una profunditat de l'arbre; per tant es considera el màxima prioritat entre tots els operadors.
- En resum, podem resumir-ho ja que el valor present a una profunditat de l'arbre té la màxima prioritat en comparació amb els altres operadors presents a la part superior de l'arbre.
- L'ús principal d'aquests arbres d'expressió és que està acostumat avaluar, analitzar i modificar les diverses expressions.
- També serveix per conèixer l'associativitat de cada operador en l'expressió.
- Per exemple, l'operador + és l'associatiu esquerre i / és l'associatiu dret.
- El dilema d'aquesta associativitat s'ha aclarit utilitzant l'expressió arbres.
- Aquests arbres d'expressions es formen utilitzant una gramàtica lliure de context.
- Hem associat una regla en gramàtiques sense context davant de cada producció gramatical.
- Aquestes regles també es coneixen com a regles semàntiques i, utilitzant aquestes regles semàntiques, podem construir fàcilment els arbres d'expressió.
- És una de les parts principals del disseny del compilador i pertany a la fase d'anàlisi semàntica.
- En aquesta anàlisi semàntica, utilitzarem les traduccions dirigides per la sintaxi i, en forma de sortida, produirem l'arbre d'anàlisi anotat.
- Un arbre d'anàlisi anotat no és més que l'anàlisi simple associat a l'atribut type i a cada regla de producció.
- L'objectiu principal d'utilitzar els arbres d'expressió és fer expressions complexes i es poden avaluar fàcilment mitjançant aquests arbres d'expressió.
- És immutable, i un cop hem creat un arbre d'expressions, no podem canviar-lo ni modificar-lo més.
- Per fer més modificacions, cal construir completament el nou arbre d'expressions.
- També s'utilitza per resoldre l'avaluació de l'expressió postfix, prefix i infix.
Els arbres d'expressió tenen un paper molt important a l'hora de representar nivell de llengua codi en forma de dades, que s'emmagatzemen principalment a l'estructura en forma d'arbre. També s'utilitza en la representació de memòria del lambda expressió. Utilitzant l'estructura de dades d'arbre, podem expressar l'expressió lambda de manera més transparent i explícita. Primer es crea per convertir el segment de codi en el segment de dades de manera que l'expressió es pugui avaluar fàcilment.
L'arbre d'expressió és un arbre binari en el qual cada node extern o de fulla correspon a l'operand i cada node intern o pare correspon als operadors, de manera que, per exemple, l'arbre d'expressió per a 7 + ((1+8)*3) seria:
Sigui S l'arbre d'expressions
Si S no és nul, aleshores
Si S.value és un operand, aleshores
Retorna el valor S
x = resoldre (S.esquerra)
y = resoldre (S.dreta)
Retorn càlcul (x, y, S.valor)
Aquí, a l'exemple anterior, l'arbre d'expressió utilitzava gramàtica lliure de context.
Tenim algunes produccions associades a algunes regles de producció en aquesta gramàtica, conegudes principalment com a regles semàntiques . Podem definir la producció de resultats a partir de les regles de producció corresponents utilitzant aquestes regles semàntiques. Aquí hem utilitzat el paràmetre de valor, que calcularà el resultat i el retornarà al símbol d'inici de la gramàtica. S.left calcularà el fill esquerre del node i, de la mateixa manera, el fill dret del node es pot calcular mitjançant el paràmetre S.right.
Ús de l'arbre d'expressió
- L'objectiu principal d'utilitzar els arbres d'expressió és fer expressions complexes i es poden avaluar fàcilment mitjançant aquests arbres d'expressió.
- També serveix per conèixer l'associativitat de cada operador en l'expressió.
- També s'utilitza per resoldre l'avaluació de l'expressió postfix, prefix i infix.
Implementació d'un arbre d'expressions
Per implementar l'arbre d'expressions i escriure el seu programa, ens demanarà que utilitzem una estructura de dades de pila.
Com que sabem que la pila es basa en el principi LIFO de l'últim en sortir, l'element de dades introduït recentment a la pila s'ha sortit sempre que s'ha requerit. Per a la seva implementació, s'utilitzen les dues operacions principals de la pila, push i pop. Mitjançant l'operació push, introduirem l'element de dades a la pila i, mitjançant l'operació pop, eliminarem l'element de dades de la pila.
Funcions principals de la pila en la implementació de l'arbre d'expressions:
En primer lloc, analitzarem l'expressió donada de manera esquerra a dreta, després comprovarem un per un el caràcter identificat,
- Si un caràcter escanejat és un operand, aplicarem l'operació push i l'introduirem a la pila.
- Si un caràcter escanejat és un operador, li aplicarem l'operació pop per eliminar els dos valors de la pila per convertir-los en fills i, després, retrocedirem el node pare actual a la pila.
Implementació de l'arbre d'expressió en llenguatge de programació 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> La sortida del programa anterior és:
X + Y * Z / W
Implementació de l'arbre d'expressió en llenguatge de programació 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> La sortida del programa anterior és:
X + Y * Z / W
Implementació de l'arbre d'expressió en llenguatge de programació 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>