Izrazno drevo je drevo, ki se uporablja za predstavitev različnih izrazov. Drevesna podatkovna struktura se uporablja za predstavitev izraznih stavkov. V tem drevesu notranje vozlišče vedno označuje operaterje.
- Listna vozlišča vedno označujejo operande.
- Operacije se vedno izvajajo na teh operandih.
- Operater, ki je prisoten v globini drevesa, ima vedno najvišjo prednost.
- Operater, ki v drevesu ni veliko v globini, je vedno na najnižji prioriteti v primerjavi z operaterji, ki ležijo v globini.
- Operand bo vedno prisoten v globini drevesa; zato velja za najvišja prioriteta med vsemi operaterji.
- Na kratko, to lahko povzamemo kot vrednost, ki je prisotna v globini drevesa, ima najvišjo prioriteto v primerjavi z drugimi operaterji, ki so prisotni na vrhu drevesa.
- Glavna uporaba teh izraznih dreves je, da se jih uporablja oceniti, analizirati in spremeniti različne izraze.
- Uporablja se tudi za ugotavljanje asociativnosti vsakega operatorja v izrazu.
- Operator + je na primer levi asociativen in / je desni asociativni.
- Dilemo te asociativnosti smo razrešili z izrazom drevesa.
- Ta izrazna drevesa so oblikovana z uporabo kontekstno proste slovnice.
- Pred vsako slovnično produkcijo smo povezali pravilo v kontekstno prostih slovnicah.
- Ta pravila so znana tudi kot semantična pravila in z uporabo teh semantičnih pravil lahko zlahka sestavimo izrazna drevesa.
- Je eden glavnih delov načrtovanja prevajalnika in spada v fazo semantične analize.
- V tej semantični analizi bomo uporabili prevode, usmerjene v sintakso, in v obliki izhoda izdelali označeno drevo razčlenjevanja.
- Označeno drevo razčlenjevanja ni nič drugega kot preprosto razčlenjevanje, povezano z atributom tipa in vsakim produkcijskim pravilom.
- Glavni cilj uporabe izraznih dreves je izdelava zapletenih izrazov, ki jih je mogoče zlahka ovrednotiti z uporabo teh izraznih dreves.
- Je nespremenljiv in ko enkrat ustvarimo izrazno drevo, ga ne moremo več spremeniti ali spreminjati.
- Za več sprememb je treba v celoti zgraditi novo izrazno drevo.
- Uporablja se tudi za reševanje vrednotenja postfiksnega, predponskega in infiksnega izraza.
Izrazna drevesa igrajo zelo pomembno vlogo pri predstavljanju jezikovna raven kodo v obliki podatkov, ki so večinoma shranjeni v drevesni strukturi. Uporablja se tudi v spominski predstavitvi lambda izražanje. Z uporabo drevesne podatkovne strukture lahko lambda izraz izrazimo bolj pregledno in eksplicitno. Najprej je ustvarjen za pretvorbo kodnega segmenta v podatkovni segment, tako da je mogoče izraz enostavno ovrednotiti.
Izrazno drevo je binarno drevo, v katerem vsako zunanje ali listno vozlišče ustreza operandu in vsako notranje ali nadrejeno vozlišče ustreza operaterjem, tako da bi bilo na primer izrazno drevo za 7 + ((1+8)*3):
Naj bo S izrazno drevo
Če S ni nič, potem
Če je S.value operand, potem
Vrni S.vrednost
x = reši (S.levo)
y = reši (S.desno)
Povratni izračun (x, y, S.vrednost)
V zgornjem primeru je izrazno drevo uporabilo slovnico brez konteksta.
V tej slovnici imamo nekaj produkcij, povezanih z nekaterimi produkcijskimi pravili, večinoma znanimi kot pomenska pravila . Ustvarjanje rezultatov lahko definiramo iz ustreznih produkcijskih pravil z uporabo teh semantičnih pravil. Tukaj smo uporabili parameter vrednosti, ki bo izračunal rezultat in ga vrnil na začetni simbol slovnice. S.left bo izračunal levega podrejenega vozlišča in podobno je mogoče izračunati desnega podrejenega vozlišča s parametrom S.right.
Uporaba izraznega drevesa
- Glavni cilj uporabe izraznih dreves je izdelava zapletenih izrazov, ki jih je mogoče zlahka ovrednotiti z uporabo teh izraznih dreves.
- Uporablja se tudi za ugotavljanje asociativnosti vsakega operatorja v izrazu.
- Uporablja se tudi za reševanje vrednotenja postfiksnega, predponskega in infiksnega izraza.
Implementacija izraznega drevesa
Za implementacijo izraznega drevesa in pisanje njegovega programa bomo morali uporabiti podatkovno strukturo sklada.
Ker vemo, da sklad temelji na načelu LIFO zadnji prišel, prvi ven, je bil podatkovni element, ki je bil pred kratkim potisnjen v sklad, po potrebi izrinjen. Za njegovo izvedbo se uporabljata glavni dve operaciji sklada, push in pop. Z operacijo push bomo podatkovni element potisnili v sklad, z operacijo pop pa odstranili podatkovni element iz sklada.
Glavne funkcije sklada v implementaciji izraznega drevesa:
Najprej bomo opravili skeniranje podanega izraza v način od leve proti desni, nato pa enega za drugim preverili identificirani znak,
- Če je skenirani znak operand, bomo uporabili operacijo potiskanja in ga potisnili v sklad.
- Če je optično prebran znak operator, bomo vanj uporabili operacijo pop, da dve vrednosti odstranimo iz sklada, da postaneta njegov podrejeni znak, nato pa bomo trenutno nadrejeno vozlišče potisnili nazaj v sklad.
Implementacija izraznega drevesa v programskem jeziku 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> Rezultat zgornjega programa je:
X + Y * Z / W
Implementacija izraznega drevesa v programskem jeziku 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> Rezultat zgornjega programa je:
X + Y * Z / W
Implementacija izraznega drevesa v programskem jeziku 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>