De expressieboom is een boom die wordt gebruikt om de verschillende expressies weer te geven. De boomdatastructuur wordt gebruikt om de expressieve uitspraken weer te geven. In deze boom geeft het interne knooppunt altijd de operators aan.
- De bladknooppunten duiden altijd de operanden aan.
- De bewerkingen worden altijd op deze operanden uitgevoerd.
- De operator die zich diep in de boom bevindt, heeft altijd de hoogste prioriteit.
- De operator, die zich niet veel op diepte in de boom bevindt, heeft altijd de laagste prioriteit vergeleken met de operatoren die op diepte liggen.
- De operand zal altijd aanwezig zijn op een diepte van de boom; daarom wordt het beschouwd als de hoogste prioriteit onder alle exploitanten.
- Kortom, we kunnen het samenvatten omdat de waarde die aanwezig is op een diepte van de boom de hoogste prioriteit heeft vergeleken met de andere operatoren bovenaan de boom.
- Het belangrijkste gebruik van deze expressiebomen is dat het gewend is evalueren, analyseren En bewerken de verschillende uitingen.
- Het wordt ook gebruikt om de associativiteit van elke operator in de uitdrukking te achterhalen.
- De + operator is bijvoorbeeld de links-associatief en / is de rechts-associatief.
- Het dilemma van deze associativiteit is opgelost door gebruik te maken van de uitdrukkingsbomen.
- Deze expressiebomen worden gevormd door gebruik te maken van een contextvrije grammatica.
- We hebben een regel in contextvrije grammatica's aan elke grammaticaproductie gekoppeld.
- Deze regels staan ook bekend als semantische regels, en door deze semantische regels te gebruiken, kunnen we gemakkelijk de expressiebomen construeren.
- Het is een van de belangrijkste onderdelen van het compilerontwerp en behoort tot de semantische analysefase.
- In deze semantische analyse zullen we de syntaxisgerichte vertalingen gebruiken, en in de vorm van uitvoer zullen we de geannoteerde ontleedboom produceren.
- Een geannoteerde ontleedboom is niets anders dan de eenvoudige ontleding die is gekoppeld aan het typeattribuut en elke productieregel.
- Het belangrijkste doel van het gebruik van de expressiebomen is het maken van complexe expressies, die gemakkelijk kunnen worden geëvalueerd met behulp van deze expressiebomen.
- Het is onveranderlijk en als we eenmaal een expressieboom hebben gemaakt, kunnen we deze niet meer wijzigen of verder aanpassen.
- Om meer wijzigingen aan te brengen, is het nodig om de nieuwe expressieboom volledig te construeren.
- Het wordt ook gebruikt om de evaluatie van de postfix-, prefix- en tussenvoegselexpressie op te lossen.
Expressiebomen spelen een zeer belangrijke rol bij het representeren van de taalniveau code in de vorm van de gegevens, die voornamelijk in de boomachtige structuur zijn opgeslagen. Het wordt ook gebruikt in de geheugenrepresentatie van de lambda uitdrukking. Met behulp van de boomdatastructuur kunnen we de lambda-expressie transparanter en explicieter uitdrukken. Het wordt eerst gemaakt om het codesegment naar het gegevenssegment te converteren, zodat de uitdrukking eenvoudig kan worden geëvalueerd.
De expressieboom is een binaire boom waarin elk extern of leaf-knooppunt overeenkomt met de operand en elk intern of ouderknooppunt overeenkomt met de operators, dus de expressieboom voor 7 + ((1+8)*3) zou er bijvoorbeeld als volgt uitzien:
Laat S de expressieboom zijn
Als S niet nul is, dan
Als S.value een operand is, dan
Retour S.waarde
x = oplossen(S.links)
y = oplossen(S.rechts)
Retour berekenen(x, y, S.waarde)
Hier in het bovenstaande voorbeeld gebruikte de expressieboom contextvrije grammatica.
We hebben enkele producties die verband houden met enkele productieregels in deze grammatica, voornamelijk bekend als semantische regels . We kunnen de resultaatproductie definiëren op basis van de overeenkomstige productieregels met behulp van deze semantische regels. Hier hebben we de waardeparameter gebruikt, die het resultaat berekent en terugstuurt naar het startsymbool van de grammatica. S.left berekent het linkerkind van het knooppunt, en op dezelfde manier kan het rechterkind van het knooppunt worden berekend met behulp van de parameter S.right.
Gebruik van expressieboom
- Het belangrijkste doel van het gebruik van de expressiebomen is het maken van complexe expressies, die gemakkelijk kunnen worden geëvalueerd met behulp van deze expressiebomen.
- Het wordt ook gebruikt om de associativiteit van elke operator in de uitdrukking te achterhalen.
- Het wordt ook gebruikt om de evaluatie van de postfix-, prefix- en tussenvoegselexpressie op te lossen.
Implementatie van een expressieboom
Om de expressieboom te implementeren en het programma ervan te schrijven, zullen we een stapelgegevensstructuur moeten gebruiken.
Omdat we weten dat de stapel gebaseerd is op het last-in-first-out LIFO-principe, wordt het gegevenselement dat onlangs in de stapel is geduwd, eruit gehaald wanneer dat nodig is. Voor de implementatie ervan worden de twee belangrijkste bewerkingen van de stapel, push en pop, gebruikt. Met behulp van de push-operatie zullen we het data-element in de stapel duwen, en met de pop-operatie zullen we het data-element uit de stapel verwijderen.
Belangrijkste functies van de stapel in de implementatie van de expressieboom:
Allereerst zullen we de gegeven uitdrukking van links naar rechts scannen, en vervolgens één voor één het geïdentificeerde teken controleren,
- Als een gescand teken een operand is, passen we de push-operatie toe en duwen we het in de stapel.
- Als een gescand teken een operator is, passen we de pop-bewerking erop toe om de twee waarden uit de stapel te verwijderen en er een kind van te maken, en daarna duwen we het huidige bovenliggende knooppunt terug in de stapel.
Implementatie van expressieboom in C-programmeertaal
// 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> De uitvoer van het bovenstaande programma is:
X + Y * Z / W
Implementatie van expressieboom in C++ programmeertaal
// 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> De uitvoer van het bovenstaande programma is:
X + Y * Z / W
Implementatie van expressieboom in Java-programmeertaal
// 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>