표현식 트리는 다양한 표현식을 표현하는 데 사용되는 트리입니다. 트리 데이터 구조는 표현문을 나타내는 데 사용됩니다. 이 트리에서 내부 노드는 항상 연산자를 나타냅니다.
- 리프 노드는 항상 피연산자를 나타냅니다.
- 연산은 항상 이러한 피연산자에 대해 수행됩니다.
- 트리 깊이에 있는 연산자가 항상 가장 높은 우선순위를 갖습니다.
- 트리의 깊이에 별로 있지 않은 연산자는 깊이에 있는 연산자에 비해 항상 가장 낮은 우선순위를 갖습니다.
- 피연산자는 항상 트리의 깊이에 나타납니다. 따라서 그것은 간주됩니다 최우선 순위 모든 운영자 중에서.
- 간단히 말해서, 트리의 최상위에 존재하는 다른 연산자들에 비해 트리의 깊이에 존재하는 값이 가장 높은 우선순위를 갖는다고 요약할 수 있습니다.
- 이러한 표현식 트리의 주요 용도는 다음과 같습니다. 평가하다, 분석하다 그리고 수정하다 다양한 표현들.
- 또한 표현식에서 각 연산자의 연관성을 찾는 데에도 사용됩니다.
- 예를 들어 + 연산자는 왼쪽 결합이고 /는 오른쪽 결합입니다.
- 이러한 연관성의 딜레마는 표현식 트리를 사용하여 해결되었습니다.
- 이러한 표현식 트리는 문맥 자유 문법을 사용하여 구성됩니다.
- 우리는 각 문법 생성 앞에 문맥 자유 문법의 규칙을 연관시켰습니다.
- 이러한 규칙은 의미 규칙이라고도 하며 이러한 의미 규칙을 사용하면 표현식 트리를 쉽게 구성할 수 있습니다.
- 컴파일러 설계의 주요 부분 중 하나이며 의미 분석 단계에 속합니다.
- 이 의미론적 분석에서는 구문 지향 번역을 사용하고 출력 형식으로 주석이 달린 구문 분석 트리를 생성합니다.
- 주석이 달린 구문 분석 트리는 유형 속성 및 각 생산 규칙과 관련된 간단한 구문 분석일 뿐입니다.
- 식 트리를 사용하는 주요 목적은 복잡한 식을 만드는 것이며 이러한 식 트리를 사용하여 쉽게 평가할 수 있습니다.
- 이는 변경할 수 없으며 일단 표현식 트리를 만든 후에는 이를 변경하거나 더 이상 수정할 수 없습니다.
- 더 많은 수정을 하려면 새로운 표현식 트리를 전체적으로 구성해야 합니다.
- 또한 접미사, 접두사 및 중위 표현 평가를 해결하는 데에도 사용됩니다.
표현식 트리는 표현하는 데 매우 중요한 역할을 합니다. 언어 수준 주로 트리 구조로 저장되는 데이터 형태의 코드입니다. 기억 표현에도 사용된다. 람다 표현. 트리 데이터 구조를 사용하면 람다 식을 보다 투명하고 명시적으로 표현할 수 있습니다. 표현식을 쉽게 평가할 수 있도록 코드 세그먼트를 데이터 세그먼트로 변환하기 위해 먼저 생성됩니다.
표현식 트리는 각 외부 또는 리프 노드가 피연산자에 해당하고 각 내부 또는 부모 노드가 연산자에 해당하는 이진 트리입니다. 예를 들어 7 + ((1+8)*3)에 대한 표현식 트리는 다음과 같습니다.
S를 표현식 트리라고 하자
S가 null이 아닌 경우
S.value가 피연산자인 경우
S.값 반환
x = 풀기(S.왼쪽)
y = 풀기(S.오른쪽)
계산(x, y, S.값) 반환
위의 예에서 표현식 트리는 문맥 자유 문법을 사용했습니다.
이 문법에는 주로 다음과 같이 알려진 일부 생성 규칙과 관련된 일부 생성이 있습니다. 의미론적 규칙 . 이러한 의미론적 규칙을 사용하여 해당 생산 규칙에서 결과 생성을 정의할 수 있습니다. 여기서는 결과를 계산하고 이를 문법의 시작 기호로 반환하는 값 매개변수를 사용했습니다. S.left는 노드의 왼쪽 자식을 계산하고 마찬가지로 S.right 매개변수를 사용하여 노드의 오른쪽 자식을 계산할 수 있습니다.
표현식 트리 사용
- 식 트리를 사용하는 주요 목적은 복잡한 식을 만드는 것이며 이러한 식 트리를 사용하여 쉽게 평가할 수 있습니다.
- 또한 표현식에서 각 연산자의 연관성을 찾는 데에도 사용됩니다.
- 또한 접미사, 접두사 및 중위 표현 평가를 해결하는 데에도 사용됩니다.
표현식 트리 구현
표현식 트리를 구현하고 프로그램을 작성하려면 스택 데이터 구조를 사용해야 합니다.
스택이 후입선출 LIFO 원칙을 기반으로 한다는 것을 알고 있으므로 최근에 스택에 푸시된 데이터 요소는 필요할 때마다 팝아웃됩니다. 구현을 위해 스택의 주요 두 가지 작업인 푸시(push)와 팝(pop)이 사용됩니다. 푸시 작업을 사용하면 데이터 요소를 스택에 푸시하고 팝 작업을 사용하면 스택에서 데이터 요소를 제거합니다.
표현식 트리 구현에서 스택의 주요 기능은 다음과 같습니다.
우선, 주어진 표현식을 왼쪽에서 오른쪽으로 스캔한 다음 식별된 문자를 하나씩 확인합니다.
- 스캔한 문자가 피연산자이면 푸시 작업을 적용하여 스택에 푸시합니다.
- 스캔한 문자가 연산자인 경우 팝 작업을 적용하여 스택에서 두 값을 제거하여 자식으로 만든 다음 현재 상위 노드를 스택에 다시 밀어 넣습니다.
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> 위 프로그램의 출력은 다음과 같습니다.
X + Y * Z / W
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> 위 프로그램의 출력은 다음과 같습니다.
X + Y * Z / W
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>