![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683285869193-Expression%20tree%20in%20data%20structure.jpg\")
<\/p>\n<\/p>\n
A data structure called an expression tree is used to describe expressions that take the shape of trees. After creating an expression’s expression tree, we may execute inorder traversal to produce an infix expression. Postfix expressions can also be produced by traversing the expression tree in postorder. In this blog, we’ll talk about expression trees in data structures and how stacks may be used to create an expression tree from a given expression.<\/p>\n
A mathematical expression can be expressed as a binary tree using expression trees. Expression trees are binary trees with each leaf node serving as an operand and each internal (non-leaf) node serving as an operator.<\/p>\n
Let’s go through some expression tree properties.<\/p>\n
In summary, the value present at the depth of the tree has the highest priority when compared to the other operators located at the top of the tree. The expression tree is immutable, and once built, we cannot change or modify it further, so to make any changes, we must completely construct the new expression tree. <\/p>\n
The given expression can be evaluated using the expression tree in data structure.<\/p>\n
a + (b * c) + d * (e + f)<\/code><\/pre>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683285869312-1-01%20%2885%29.png\")
<\/p>\n
Uses of an Expression Tree in Data Structure<\/h3>\n
The following is the primary application of these expression trees in data structure:<\/p>\n
\n- \n
It evaluates, analyses, and modifies diverse phrases. It can also be used to determine the associativity of each operator in an expression.
\nAs an example:<\/strong>
\nThe + operator is left-associative, while the \/ operator is right-associative. The expression trees helped to solve the conundrum of this associativity. <\/p>\n<\/li>\n- \n
A context-free grammar is used to create these expression trees.<\/p>\n<\/li>\n
- \n
It is a key component in compiler design and is part of the semantic analysis step.<\/p>\n<\/li>\n
- \n
The expression trees are mostly used to create complex expressions that can be quickly evaluated.<\/p>\n<\/li>\n<\/ul>\n
Construction of an Expression Tree in Data Structure<\/h3>\n
A stack is used to build an expression tree. For each character, we cycle through the input expressions and do the following. <\/p>\n
\n- If a character is an operand, add it to the stack.<\/li>\n
- If a character is an operator, pop both values from the stack and make both its children and push the current node again.<\/li>\n<\/ul>\n
Finally, the stack’s lone element will be the root of an expression tree.<\/p>\n
Let us understand this above process using a postfix expression. The implementation of the expression tree is described for the below expression.<\/p>\n
a b + c *<\/code><\/pre>\n\n- \n
Step1 :<\/strong> The first two symbols are operands, for which we generate a one-node tree and push a reference to the stack.<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683285869342-1-02%20%2843%29.png\")
<\/p>\n<\/li>\n
- \n
Step2 :<\/strong> Next, read a’+’ symbol to pop two pointers to the tree, form a new tree, and push a pointer to it onto the stack.<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683285869345-1-03%20%2829%29.png\")
<\/p>\n<\/li>\n
- \n
Step3 :<\/strong> In the next stage ‘c’ is read, we build a single node tree and store a pointer to it on the stack<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683285869346-1-04%20%2822%29.png\")
<\/p>\n<\/li>\n
- \n
Step4 :<\/strong> Finally, we read the last symbol’ ‘, pop two tree pointers, and build a new tree with a,’<\/em>‘as root, and a pointer to the final tree remains on the stack.<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683285869346-1-05%20%2816%29.png\")
<\/p>\n<\/li>\n<\/ul>\n
Algorithm of an Expression Tree in Data Structure<\/h3>\n
Let ET be the expression tree<\/p>\n
If ET is not null then\n If ET.value is operand then \n return ET.value\n A = solve(ET.left)\n B = solve(ET.right)\n\n return calculate(A, B, ET.value) \n\n\/\/ calculate() function applies operator 'ET.value' on A and B, and returns the value<\/code><\/pre>\nCode Implementation for Construction of an Expression Tree<\/h3>\n
Let us now discuss the code implementation of an expression tree for the expression :
\nA + B * C \/ D<\/p>\n\t\t\t\t\t\t