Strom výrazov je strom používaný na reprezentáciu rôznych výrazov. Stromová dátová štruktúra sa používa na reprezentáciu výrazových príkazov. V tomto strome interný uzol vždy označuje operátory.
- Listové uzly vždy označujú operandy.
- Operácie sa vždy vykonávajú na týchto operandoch.
- Operátor prítomný v hĺbke stromu má vždy najvyššiu prioritu.
- Operátor, ktorý nie je príliš v hĺbke stromu, má vždy najnižšiu prioritu v porovnaní s operátormi ležiacimi v hĺbke.
- Operand bude vždy prítomný v hĺbke stromu; preto sa považuje za najvyššia priorita medzi všetkými operátormi.
- Stručne povedané, môžeme to zhrnúť tak, že hodnota prítomná v hĺbke stromu má najvyššiu prioritu v porovnaní s ostatnými operátormi prítomnými v hornej časti stromu.
- Hlavným použitím týchto výrazových stromov je to, na čo je zvyknutý hodnotiť, analyzovať a upraviť rôzne výrazy.
- Používa sa tiež na zistenie asociatívnosti každého operátora vo výraze.
- Napríklad operátor + je asociatívny vľavo a operátor / je asociatívny vpravo.
- Dilema tejto asociatívnosti bola vyriešená použitím výrazových stromov.
- Tieto výrazové stromy sú tvorené použitím bezkontextovej gramatiky.
- Pred každou produkciou gramatiky sme priradili pravidlo v bezkontextových gramatikách.
- Tieto pravidlá sú známe aj ako sémantické pravidlá a pomocou týchto sémantických pravidiel môžeme ľahko zostaviť výrazové stromy.
- Je to jedna z hlavných častí návrhu kompilátora a patrí do fázy sémantickej analýzy.
- V tejto sémantickej analýze použijeme syntaxovo riadené preklady a vo forme výstupu vytvoríme anotovaný syntaktický strom.
- Anotovaný strom analýzy nie je nič iné ako jednoduchá analýza spojená s atribútom type a každým produkčným pravidlom.
- Hlavným cieľom použitia výrazových stromov je vytvárať zložité výrazy a dajú sa ľahko vyhodnotiť pomocou týchto výrazových stromov.
- Je nemenný a keď už vytvoríme strom výrazov, nemôžeme ho meniť ani ďalej upravovať.
- Na vykonanie ďalších úprav je potrebné úplne zostaviť nový strom výrazov.
- Používa sa aj na riešenie vyhodnotenia výrazov postfix, prefix a infix.
Výrazové stromy zohrávajú veľmi dôležitú úlohu pri reprezentácii jazykovej úrovni kód vo forme údajov, ktoré sú uložené hlavne v stromovej štruktúre. Používa sa tiež v pamäťovej reprezentácii lambda výraz. Pomocou stromovej dátovej štruktúry môžeme výraz lambda vyjadriť transparentnejšie a explicitnejšie. Najprv sa vytvorí na konverziu segmentu kódu na segment údajov, aby sa výraz mohol ľahko vyhodnotiť.
Strom výrazov je binárny strom, v ktorom každý externý alebo listový uzol zodpovedá operandu a každý interný alebo rodičovský uzol zodpovedá operátorom, takže napríklad strom výrazov pre 7 + ((1+8)*3) by bol:
Nech S je strom výrazov
Ak S nie je nulové, potom
Ak je S.hodnota operandom, potom
Návrat S.hodnota
x = vyriešiť (S.vľavo)
y = vyriešiť (S.vpravo)
Vrátiť výpočet(x, y, S.hodnota)
Tu vo vyššie uvedenom príklade strom výrazov používal bezkontextovú gramatiku.
V tejto gramatike máme niekoľko inscenácií spojených s niektorými pravidlami výroby, najmä známymi ako sémantické pravidlá . Pomocou týchto sémantických pravidiel môžeme definovať tvorbu výsledkov z príslušných produkčných pravidiel. Tu sme použili parameter value, ktorý vypočíta výsledok a vráti ho na začiatočný symbol gramatiky. S.left vypočíta ľavý potomok uzla a podobne je možné vypočítať pravé dieťa uzla pomocou parametra S.right.
Použitie stromu výrazov
- Hlavným cieľom použitia výrazových stromov je vytvárať zložité výrazy a dajú sa ľahko vyhodnotiť pomocou týchto výrazových stromov.
- Používa sa tiež na zistenie asociatívnosti každého operátora vo výraze.
- Používa sa aj na riešenie vyhodnotenia výrazov postfix, prefix a infix.
Implementácia stromu výrazov
Na implementáciu stromu výrazov a napísanie jeho programu budeme musieť použiť dátovú štruktúru zásobníka.
Keďže vieme, že zásobník je založený na princípe LIFO posledný dnu, prvý von, dátový prvok vložený nedávno do zásobníka bol vysunutý, kedykoľvek to bolo potrebné. Na jeho implementáciu sa používajú hlavné dve operácie zásobníka, push a pop. Pomocou operácie push vtlačíme dátový prvok do zásobníka a pomocou operácie pop odstránime dátový prvok zo zásobníka.
Hlavné funkcie zásobníka v implementácii stromu výrazov:
Najprv urobíme skenovanie daného výrazu smerom zľava doprava, následne jeden po druhom skontrolujeme identifikovaný znak,
- Ak je naskenovaný znak operandom, použijeme operáciu push a vložíme ho do zásobníka.
- Ak je naskenovaný znak operátor, použijeme naň operáciu pop, aby sme odstránili dve hodnoty zo zásobníka, aby sa stali jeho potomkom, a potom do zásobníka zatlačíme aktuálny nadradený uzol.
Implementácia stromu výrazov v programovacom jazyku 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> Výstupom vyššie uvedeného programu je:
X + Y * Z / W
Implementácia stromu výrazov v programovacom jazyku 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> Výstupom vyššie uvedeného programu je:
X + Y * Z / W
Implementácia stromu výrazov v programovacom jazyku 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>