Стабло израза је дрво које се користи за представљање различитих израза. Структура података стабла се користи за представљање израза. У овом стаблу, унутрашњи чвор увек означава операторе.
- Листови чворови увек означавају операнде.
- Операције се увек изводе над овим операндима.
- Оператор присутан у дубини стабла је увек на највишем приоритету.
- Оператор, који није много на дубини у стаблу, увек је на најнижем приоритету у поређењу са оператерима који леже на дубини.
- Операнд ће увек бити присутан на дубини дрвета; стога се сматра да највиши приоритет међу свим оператерима.
- Укратко, можемо то сумирати као вредност присутна на дубини дрвета на највишем приоритету у поређењу са другим операторима присутним на врху стабла.
- Главна употреба ових стабала израза је да је навикла проценити, анализирати и модификовати разним изразима.
- Такође се користи за откривање асоцијативности сваког оператора у изразу.
- На пример, оператор + је лево-асоцијативно, а / је десно-асоцијативно.
- Дилема ове асоцијативности је отклоњена коришћењем стабала израза.
- Ова стабла израза се формирају коришћењем граматике без контекста.
- Повезали смо правило у граматикама без контекста испред сваке граматичке продукције.
- Ова правила су такође позната као семантичка правила и коришћењем ових семантичких правила можемо лако да конструишемо стабла израза.
- То је један од главних делова дизајна компајлера и припада фази семантичке анализе.
- У овој семантичкој анализи користићемо преводе усмерене на синтаксу, а у облику излаза ћемо произвести анотирано стабло рашчлањивања.
- Стабло рашчлањивања са коментарима није ништа друго до једноставна анализа повезана са атрибутом типа и сваким производним правилом.
- Главни циљ коришћења стабала израза је прављење сложених израза и могу се лако проценити коришћењем ових стабала израза.
- Он је непроменљив и када једном креирамо стабло израза, не можемо га мењати или модификовати даље.
- Да бисте направили више модификација, потребно је да се у потпуности конструише ново стабло израза.
- Такође се користи за решавање процене израза постфикса, префикса и инфикса.
Стабла израза играју веома важну улогу у представљању на нивоу језика код у облику података, који се углавном чува у структури налик стаблу. Такође се користи у меморијској представи ламбда израз. Користећи структуру података стабла, можемо изразити ламбда израз транспарентније и експлицитније. Прво је креиран да конвертује сегмент кода у сегмент података тако да се израз може лако проценити.
Стабло израза је бинарно стабло у коме сваки спољни или лисни чвор одговара операнду, а сваки унутрашњи или родитељски чвор одговара операторима, тако да би на пример стабло израза за 7 + ((1+8)*3) било:
Нека је С дрво израза
Ако С није нула, онда
Ако је С.валуе операнд, онда
Врати С.вредност
к = реши (С.лево)
и = реши (С.десно)
Врати израчунај(к, и, С.вредност)
Овде у горњем примеру, стабло израза је користило граматику без контекста.
Имамо неке продукције повезане са неким производним правилима у овој граматици, углавном познатим као семантичка правила . Можемо дефинисати производњу резултата из одговарајућих правила производње користећи ова семантичка правила. Овде смо користили параметар вредности, који ће израчунати резултат и вратити га на почетни симбол граматике. С.лефт ће израчунати лево дете чвора, и слично, десно дете чвора може се израчунати помоћу параметра С.ригхт.
Употреба стабла израза
- Главни циљ коришћења стабала израза је прављење сложених израза и могу се лако проценити коришћењем ових стабала израза.
- Такође се користи за откривање асоцијативности сваког оператора у изразу.
- Такође се користи за решавање процене израза постфикса, префикса и инфикса.
Имплементација стабла израза
Да бисмо имплементирали стабло израза и написали његов програм, од нас ће се тражити да користимо структуру података стека.
Пошто знамо да је стек заснован на принципу ЛИФО „последњи у први је изашао“, елемент података који је недавно гурнут у стек је искочио кад год је то било потребно. За његову имплементацију користе се две главне операције стека, пусх и поп. Користећи пусх операцију, гурнућемо елемент података у стек, а коришћењем операције поп уклонићемо елемент података из стека.
Главне функције стека у имплементацији стабла израза:
Пре свега, извршићемо скенирање датог израза са лева на десно, затим један по један проверити идентификовани карактер,
- Ако је скенирани знак операнд, применићемо операцију гурања и гурнути је у стек.
- Ако је скенирани знак оператор, применићемо на њега операцију поп да уклонимо две вредности из стека како бисмо их учинили подређеним, а након тога ћемо потиснути тренутни родитељски чвор назад у стек.
Имплементација стабла израза у програмском језику Ц
// 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> Резултат горњег програма је:
X + Y * Z / W
Имплементација стабла израза у програмском језику Ц++
// 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> Резултат горњег програма је:
X + Y * Z / W
Имплементација стабла израза у програмском језику Јава
// 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>