Expression Tree in Data Structure

Last Updated on May 5, 2023 by Prepbytes

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.

What is an Expression Tree in Data Structure?

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.

Properties of Expression Tree in Data Structure

Let’s go through some expression tree properties.

• The operands are always represented by the leaf nodes. These operands are always used in the operations.
• The operator at the root of the tree is always given top priority.
• When compared to the operators at the bottom of the tree, the operator at the bottom is always given the lowest priority.
• Because the operand is always present at a depth of the tree, it is given the highest priority of all operators.
• The expression tree can be traversed to evaluate prefix expressions, postfix expressions, and infix expressions.

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.

The given expression can be evaluated using the expression tree in data structure.

 a + (b * c) + d * (e + f)

Uses of an Expression Tree in Data Structure

The following is the primary application of these expression trees in data structure:

• It evaluates, analyses, and modifies diverse phrases. It can also be used to determine the associativity of each operator in an expression.
  As an example:
  The + operator is left-associative, while the / operator is right-associative. The expression trees helped to solve the conundrum of this associativity.

• A context-free grammar is used to create these expression trees.

• It is a key component in compiler design and is part of the semantic analysis step.

• The expression trees are mostly used to create complex expressions that can be quickly evaluated.

Construction of an Expression Tree in Data Structure

A stack is used to build an expression tree. For each character, we cycle through the input expressions and do the following.

• If a character is an operand, add it to the stack.
• If a character is an operator, pop both values from the stack and make both its children and push the current node again.

Finally, the stack’s lone element will be the root of an expression tree.

Let us understand this above process using a postfix expression. The implementation of the expression tree is described for the below expression.

a b + c *

• Step1 : The first two symbols are operands, for which we generate a one-node tree and push a reference to the stack.

  

• Step2 : Next, read a’+’ symbol to pop two pointers to the tree, form a new tree, and push a pointer to it onto the stack.

  

• Step3 : In the next stage ‘c’ is read, we build a single node tree and store a pointer to it on the stack

  

• Step4 : Finally, we read the last symbol’ ‘, pop two tree pointers, and build a new tree with a,’‘as root, and a pointer to the final tree remains on the stack.

  

Algorithm of an Expression Tree in Data Structure

Let ET be the expression tree

If  ET is not null then
      If ET.value is operand then  
                return  ET.value
      A = solve(ET.left)
      B = solve(ET.right)

      return calculate(A, B, ET.value) 

// calculate() function applies operator 'ET.value' on A and B, and returns the value

Code Implementation for Construction of an Expression Tree

Let us now discuss the code implementation of an expression tree for the expression :
A + B * C / D

#include <stdio.h>
#include <stdlib.h>

struct node {
    char data;
    struct node* left;
    struct node* right;
};
struct node* create_node(char data) {
    struct node* new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

struct node* construct_tree(char postfix[]) {
    struct node* stack[100];
    int top = -1;
    int i = 0;
    while (postfix[i] != '\0') {
        char ch = postfix[i];
        if (ch >= 'A' && ch <= 'Z') {
            struct node* new_node = create_node(ch);
            stack[++top] = new_node;
        } else {
            struct node* new_node = create_node(ch);
            new_node->right = stack[top--];
            new_node->left = stack[top--];
            stack[++top] = new_node;
        }
        i++;
    }
    return stack[top--];
}

void inorder(struct node* root) {
    if (root) {
        inorder(root->left);
        printf("%c ", root->data);
        inorder(root->right);
    }
}

int main() {
    char postfix[] = "ABC*+D/";
    struct node* root = construct_tree(postfix);
    printf("Inorder traversal of expression tree:\n");
    inorder(root);
    return 0;
}

#include <iostream>
#include <stack>

using namespace std;

struct node {
    char data;
    node* left;
    node* right;
};

node* create_node(char data) {
    node* new_node = new node();
    new_node->data = data;
    new_node->left = nullptr;
    new_node->right = nullptr;
    return new_node;
}

node* construct_tree(char postfix[]) {
    stack<node*> s;
    int i = 0;
    while (postfix[i] != '\0') {
        char ch = postfix[i];
        if (ch >= 'A' && ch <= 'Z') {
            node* new_node = create_node(ch);
            s.push(new_node);
        } else {
            node* new_node = create_node(ch);
            new_node->right = s.top();
            s.pop();
            new_node->left = s.top();
            s.pop();
            s.push(new_node);
        }
        i++;
    }
    return s.top();
}

void inorder(node* root) {
    if (root) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

int main() {
    char postfix[] = "ABC*+D/";
    node* root = construct_tree(postfix);
    cout << "Inorder traversal of expression tree:" << endl;
    inorder(root);
    return 0;
}

import java.util.*;

class Node {
    char data;
    Node left, right;
    Node(char data) {
        this.data = data;
        left = right = null;
    }
}

class ExpressionTree {
    static Node constructTree(char postfix[]) {
        Stack<Node> stack = new Stack<>();
        int i = 0;
        while (i < postfix.length) {
            char ch = postfix[i];
            if (Character.isLetter(ch)) {
                Node new_node = new Node(ch);
                stack.push(new_node);
            } else {
                Node new_node = new Node(ch);
                new_node.right = stack.pop();
                new_node.left = stack.pop();
                stack.push(new_node);
            }
            i++;
        }
        return stack.pop();
    }

    static void inorder(Node root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    public static void main(String[] args) {
        char postfix[] = "ABC*+D/";
        Node root = constructTree(postfix);
        System.out.println("Inorder traversal of expression tree:");
        inorder(root);
    }
}

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def construct_tree(postfix):
    stack = []
    for ch in postfix:
        if ch.isalpha():
            new_node = Node(ch)
            stack.append(new_node)
        else:
            new_node = Node(ch)
            new_node.right = stack.pop()
            new_node.left = stack.pop()
            stack.append(new_node)
    return stack.pop()

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=" ")
        inorder(root.right)

postfix = "ABC*+D/"
root = construct_tree(postfix)expression tree in data structures
print("Inorder traversal of expression tree:")
inorder(root)

Output :

Inorder traversal of expression tree:
A B C * + D /

Conclusion
We went over the expression tree in a data structure in detail in this article. What is an expression tree in data structures? how to build an expression tree in a data structure. Along with the code, we discussed the overall expression tree algorithm.

Frequently Asked Questions (FAQs)

Q1. What is the use of an expression tree?
Ans. Expression trees are also used in the dynamic language runtime (DLR) to provide interoperability between dynamic languages. NET and to enable compiler writers to emit expression trees instead of Microsoft intermediate language (MSIL).

Q2. What is an expression tree in the C function?
Ans. An expression tree is a special type of binary tree that is used to store algebraic expressions.

Q3. What are expression trees and decision trees?
Ans. A decision tree expression allows the definition of a binary tree of expressions.

Q4. What is an expression in data structure?
Ans. An expression is a collection of operators and operands that represents a specific value.

Q5. What are the disadvantages of expression trees?
Ans. The disadvantage of this approach is that too many nodes are used for expressions that contain one operator several times and simplification of expressions is difficult.