Strom výrazů je strom používaný k reprezentaci různých výrazů. K reprezentaci výrazových příkazů se používá stromová datová struktura. V tomto stromu vnitřní uzel vždy označuje operátory.
- Listové uzly vždy označují operandy.
- Operace se vždy provádějí na těchto operandech.
- Operátor přítomný v hloubce stromu má vždy nejvyšší prioritu.
- Operátor, který není příliš v hloubce stromu, má vždy nejnižší prioritu ve srovnání s operátory ležícími v hloubce.
- Operand bude vždy přítomen v hloubce stromu; proto se považuje za Nejvyšší prioritou mezi všemi operátory.
- Stručně řečeno, můžeme to shrnout tak, že hodnota přítomná v hloubce stromu má nejvyšší prioritu ve srovnání s ostatními operátory přítomnými v horní části stromu.
- Hlavní použití těchto výrazových stromů je takové, na jaké je zvyklé hodnotit, analyzovat a modifikovat různé výrazy.
- Používá se také ke zjištění asociativnosti každého operátoru ve výrazu.
- Například operátor + je asociativní vlevo a / je asociativní vpravo.
- Dilema této asociativnosti bylo odstraněno použitím výrazových stromů.
- Tyto výrazové stromy jsou tvořeny použitím bezkontextové gramatiky.
- Před každou produkci gramatiky jsme přiřadili pravidlo v bezkontextových gramatikách.
- Tato pravidla jsou také známá jako sémantická pravidla a pomocí těchto sémantických pravidel můžeme snadno konstruovat výrazové stromy.
- Je to jedna z hlavních částí návrhu kompilátoru a patří do fáze sémantické analýzy.
- V této sémantické analýze použijeme překlady řízené syntaxí a ve formě výstupu vytvoříme anotovaný syntaktický strom.
- Anotovaný strom analýzy není nic jiného než jednoduchá analýza spojená s atributem type a každým produkčním pravidlem.
- Hlavním cílem použití výrazových stromů je vytvářet složité výrazy a lze je pomocí těchto výrazových stromů snadno vyhodnotit.
- Je neměnný a jakmile vytvoříme strom výrazů, nemůžeme jej měnit ani dále upravovat.
- Chcete-li provést další úpravy, je nutné zcela sestavit nový strom výrazů.
- Používá se také k řešení vyhodnocení výrazu postfix, prefix a infix.
Výrazové stromy hrají velmi důležitou roli při reprezentaci jazykové úrovni kód ve formě dat, která jsou převážně uložena ve stromové struktuře. Používá se také v paměťové reprezentaci lambda výraz. Pomocí stromové datové struktury můžeme vyjádřit výraz lambda transparentněji a explicitněji. Nejprve je vytvořen pro převod segmentu kódu na segment dat, aby bylo možné výraz snadno vyhodnotit.
Strom výrazů je binární strom, ve kterém každý vnější nebo listový uzel odpovídá operandu a každý vnitřní nebo nadřazený uzel odpovídá operátorům, takže například strom výrazu pro 7 + ((1+8)*3) by byl:
Nechť S je strom výrazů
Pokud S není nulové, pak
Pokud je S.hodnota operandem, pak
Návrat S.hodnota
x = vyřešit (S.left)
y = vyřešit (S.vpravo)
Návrat vypočítat(x, y, S.hodnota)
Zde ve výše uvedeném příkladu strom výrazů používal bezkontextovou gramatiku.
V této gramatice máme některé inscenace spojené s některými produkčními pravidly, hlavně známými jako sémantická pravidla . Pomocí těchto sémantických pravidel můžeme definovat vytváření výsledků z odpovídajících produkčních pravidel. Zde jsme použili parametr value, který vypočítá výsledek a vrátí jej na počáteční symbol gramatiky. S.left vypočítá levého potomka uzlu a podobně lze vypočítat pravého potomka uzlu pomocí parametru S.right.
Použití stromu výrazů
- Hlavním cílem použití výrazových stromů je vytvářet složité výrazy a lze je pomocí těchto výrazových stromů snadno vyhodnotit.
- Používá se také ke zjištění asociativnosti každého operátoru ve výrazu.
- Používá se také k řešení vyhodnocení výrazu postfix, prefix a infix.
Implementace stromu výrazů
K implementaci stromu výrazů a napsání jeho programu budeme muset použít datovou strukturu zásobníku.
Protože víme, že zásobník je založen na principu LIFO poslední dovnitř, první ven, datový prvek vložený nedávno do zásobníku byl vysunut, kdykoli to bylo potřeba. Pro jeho implementaci se používají hlavní dvě operace zásobníku, push a pop. Pomocí operace push vložíme datový prvek do zásobníku a pomocí operace pop odstraníme datový prvek ze zásobníku.
Hlavní funkce zásobníku v implementaci stromu výrazů:
Nejprve provedeme skenování daného výrazu zleva doprava, poté jeden po druhém zkontrolujeme identifikovaný znak,
- Pokud je naskenovaný znak operandem, použijeme operaci push a vložíme jej do zásobníku.
- Pokud je naskenovaný znak operátor, použijeme na něj operaci pop, abychom odstranili dvě hodnoty ze zásobníku, aby se staly jeho potomkem, a poté zatlačíme zpět aktuální nadřazený uzel do zásobníku.
Implementace stromu výrazů v programovacím jazyce 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ýstupem výše uvedeného programu je:
X + Y * Z / W
Implementace stromu výrazů v programovacím jazyce 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ýstupem výše uvedeného programu je:
X + Y * Z / W
Implementace stromu výrazů v programovacím jazyce 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>