Uttrykkstreet er et tre som brukes til å representere de ulike uttrykkene. Tredatastrukturen brukes til å representere uttrykksutsagnene. I dette treet angir den interne noden alltid operatørene.
- Bladnodene angir alltid operandene.
- Operasjonene utføres alltid på disse operandene.
- Operatøren som befinner seg i dybden av treet har alltid høyeste prioritet.
- Operatøren, som ikke er mye på dybden i treet, har alltid lavest prioritet sammenlignet med operatørene som ligger på dypet.
- Operaanden vil alltid være tilstede i en dybde av treet; derfor anses det som høyeste prioritet blant alle operatørene.
- Kort oppsummert kan vi oppsummere det som at verdien som er tilstede i en dybde av treet har høyeste prioritet sammenlignet med de andre operatørene som er tilstede på toppen av treet.
- Hovedbruken av disse uttrykkstrærene er at de er vant til vurdere, analysere og endre de ulike uttrykkene.
- Den brukes også til å finne ut assosiativiteten til hver operator i uttrykket.
- For eksempel er +-operatoren den venstre-assosiative og / er den høyre-assosiative.
- Dilemmaet til denne assosiativiteten har blitt ryddet opp ved å bruke uttrykket trær.
- Disse uttrykkstrærene er dannet ved å bruke en kontekstfri grammatikk.
- Vi har knyttet en regel i kontekstfrie grammatikker foran hver grammatikkproduksjon.
- Disse reglene er også kjent som semantiske regler, og ved å bruke disse semantiske reglene kan vi enkelt konstruere uttrykkstrene.
- Det er en av hoveddelene av kompilatordesign og tilhører den semantiske analysefasen.
- I denne semantiske analysen vil vi bruke de syntaksstyrte oversettelsene, og i form av utdata vil vi produsere det kommenterte parsetreet.
- Et kommentert parse-tre er ikke annet enn den enkle analysen knyttet til typeattributtet og hver produksjonsregel.
- Hovedmålet med å bruke uttrykkstrene er å lage komplekse uttrykk og kan enkelt evalueres ved hjelp av disse uttrykkstrærene.
- Det er uforanderlig, og når vi først har laget et uttrykkstre, kan vi ikke endre det eller modifisere det ytterligere.
- For å gjøre flere modifikasjoner, er det nødvendig å konstruere det nye uttrykkstreet helt.
- Det brukes også til å løse evalueringen av postfiks-, prefiks- og infiksuttrykk.
Uttrykkstrær spiller en svært viktig rolle i å representere språknivå kode i form av dataene, som hovedsakelig er lagret i den trelignende strukturen. Det brukes også i minnerepresentasjonen av lambda uttrykk. Ved å bruke tredatastrukturen kan vi uttrykke lambda-uttrykket mer transparent og eksplisitt. Det opprettes først for å konvertere kodesegmentet til datasegmentet slik at uttrykket enkelt kan evalueres.
Uttrykkstreet er et binært tre der hver ekstern- eller bladnode tilsvarer operanden og hver interne eller overordnede node tilsvarer operatorene, så for eksempel vil uttrykkstre for 7 + ((1+8)*3) være:
La S være uttrykkstreet
Hvis S ikke er null, da
Hvis S.value er en operand, da
Returner S.verdi
x = løse(S.venstre)
y = solve(S.right)
Retur beregn(x, y, S.verdi)
Her i eksemplet ovenfor brukte uttrykkstreet kontekstfri grammatikk.
Vi har noen produksjoner knyttet til noen produksjonsregler i denne grammatikken, hovedsakelig kjent som semantiske regler . Vi kan definere resultatproduserende fra de tilsvarende produksjonsreglene ved å bruke disse semantiske reglene. Her har vi brukt verdiparameteren, som vil beregne resultatet og returnere det til grammatikkens startsymbol. S.left vil beregne det venstre barnet til noden, og på samme måte kan det høyre barnet til noden beregnes ved å bruke S.right-parameteren.
Bruk av uttrykkstreet
- Hovedmålet med å bruke uttrykkstrene er å lage komplekse uttrykk og kan enkelt evalueres ved hjelp av disse uttrykkstrærene.
- Den brukes også til å finne ut assosiativiteten til hver operator i uttrykket.
- Det brukes også til å løse evalueringen av postfiks-, prefiks- og infiksuttrykk.
Implementering av et uttrykkstre
For å implementere uttrykkstreet og skrive programmet, må vi bruke en stabeldatastruktur.
Siden vi vet at stabelen er basert på LIFO-prinsippet sist inn først ut, har dataelementet som nylig ble skjøvet inn i stabelen blitt spratt ut når det var nødvendig. For implementeringen brukes de to hovedoperasjonene til stabelen, push og pop. Ved å bruke push-operasjonen vil vi skyve dataelementet inn i stabelen, og ved å bruke pop-operasjonen vil vi fjerne dataelementet fra stabelen.
Hovedfunksjoner til stabelen i uttrykkstreimplementeringen:
Først av alt skal vi skanne det gitte uttrykket til venstre til høyre måte, deretter en etter en sjekke det identifiserte tegnet,
- Hvis et skannet tegn er en operand, bruker vi push-operasjonen og skyver den inn i stabelen.
- Hvis et skannet tegn er en operator, vil vi bruke pop-operasjonen inn i det for å fjerne de to verdiene fra stabelen for å gjøre dem til dets underordnede, og deretter skyver vi tilbake den nåværende overordnede noden inn i stabelen.
Implementering av uttrykkstre i C programmeringsspråk
// 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> Utgangen av programmet ovenfor er:
X + Y * Z / W
Implementering av uttrykkstre i C++ programmeringsspråk
// 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> Utgangen av programmet ovenfor er:
X + Y * Z / W
Implementering av uttrykkstre i Java programmeringsspråk
// 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>