Uttrycksträdet är ett träd som används för att representera de olika uttrycken. Träddatastrukturen används för att representera uttryckssatserna. I detta träd betecknar den interna noden alltid operatörerna.
- Bladnoderna betecknar alltid operanderna.
- Operationerna utförs alltid på dessa operander.
- Operatören som befinner sig i trädets djup har alltid högsta prioritet.
- Operatören, som inte är mycket på djupet i trädet, har alltid lägst prioritet jämfört med operatörerna som ligger på djupet.
- Operanden kommer alltid att finnas på ett djup av trädet; därför anses det vara högsta prioritet bland alla operatörer.
- Kortfattat kan vi sammanfatta det som att värdet som finns på ett djup av trädet har högsta prioritet jämfört med de andra operatörerna som finns i toppen av trädet.
- Den huvudsakliga användningen av dessa uttrycksträd är att de är vana vid utvärdera, analysera och ändra de olika uttrycken.
- Det används också för att ta reda på associativiteten för varje operator i uttrycket.
- Till exempel är + operatorn vänsterassociativ och / är högerassociativ.
- Dilemmat med denna associativitet har rensats genom att använda uttrycket träd.
- Dessa uttrycksträd bildas genom att använda en kontextfri grammatik.
- Vi har kopplat en regel i sammanhangsfria grammatiker framför varje grammatikproduktion.
- Dessa regler är också kända som semantiska regler, och genom att använda dessa semantiska regler kan vi enkelt konstruera uttrycksträden.
- Det är en av huvuddelarna av kompilatordesign och tillhör den semantiska analysfasen.
- I denna semantiska analys kommer vi att använda de syntaxstyrda översättningarna, och i form av utdata kommer vi att producera det kommenterade analysträdet.
- Ett kommenterat analysträd är inget annat än den enkla analysen som är associerad med typattributet och varje produktionsregel.
- Huvudsyftet med att använda uttrycksträden är att göra komplexa uttryck och kan enkelt utvärderas med hjälp av dessa uttrycksträd.
- Det är oföränderligt, och när vi väl har skapat ett uttrycksträd kan vi inte ändra det eller modifiera det ytterligare.
- För att göra fler modifieringar krävs det att det nya uttrycksträdet konstrueras helt.
- Det används också för att lösa utvärderingen av postfix-, prefix- och infixuttryck.
Uttrycksträd spelar en mycket viktig roll för att representera språknivå kod i form av data, som huvudsakligen lagras i den trädliknande strukturen. Det används också i minnesrepresentationen av lambda uttryck. Med hjälp av träddatastrukturen kan vi uttrycka lambda-uttrycket mer transparent och explicit. Det skapas först för att konvertera kodsegmentet till datasegmentet så att uttrycket enkelt kan utvärderas.
Uttrycksträdet är ett binärt träd där varje extern nod eller lövnod motsvarar operanden och varje intern eller överordnad nod motsvarar operatorerna så till exempel skulle uttrycksträd för 7 + ((1+8)*3) vara:
Låt S vara uttrycksträdet
Om S inte är null, då
Om S.value är en operand, då
Returnera S.värde
x = lösa(S.vänster)
y = lösa (S.höger)
Return calculate(x, y, S.value)
Här i exemplet ovan använde uttrycksträdet sammanhangsfri grammatik.
Vi har några produktioner förknippade med några produktionsregler i denna grammatik, främst känd som semantiska regler . Vi kan definiera resultatet som produceras från motsvarande produktionsregler med hjälp av dessa semantiska regler. Här har vi använt värdeparametern, som kommer att beräkna resultatet och returnera det till grammatikens startsymbol. S.left kommer att beräkna nodens vänstra underordnade, och på liknande sätt kan det högra underordnade av noden beräknas med S.right-parametern.
Användning av uttrycksträd
- Huvudsyftet med att använda uttrycksträden är att göra komplexa uttryck och kan enkelt utvärderas med hjälp av dessa uttrycksträd.
- Det används också för att ta reda på associativiteten för varje operator i uttrycket.
- Det används också för att lösa utvärderingen av postfix-, prefix- och infixuttryck.
Implementering av ett uttrycksträd
För att implementera uttrycksträdet och skriva dess program kommer vi att behöva använda en stackdatastruktur.
Eftersom vi vet att stacken är baserad på LIFO-principen sist in först ut, har dataelementet som nyligen tryckts in i stacken ploppats ut närhelst det har behövts. För dess implementering används stackens två huvudsakliga operationer, push och pop. Med push-operationen kommer vi att trycka in dataelementet i stacken, och genom att använda pop-operationen tar vi bort dataelementet från stacken.
Huvudfunktioner för stacken i expressionsträdets implementering:
Först och främst ska vi skanna det givna uttrycket till vänster till höger sätt, sedan en efter en kontrollera det identifierade tecknet,
- Om ett skannat tecken är en operand kommer vi att tillämpa push-operationen och skjuta in den i stacken.
- Om ett skannat tecken är en operator, kommer vi att tillämpa pop-operationen i den för att ta bort de två värdena från stacken för att göra dem till dess underordnade, och efter det kommer vi att trycka tillbaka den nuvarande överordnade noden i stacken.
Implementering av uttrycksträd i programmeringsspråk 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> Resultatet av programmet ovan är:
X + Y * Z / W
Implementering av uttrycksträd i programmeringsspråk 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> Resultatet av programmet ovan är:
X + Y * Z / W
Implementering av uttrycksträd i programmeringsspråk 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>