Expression Tree - Scaler Topics

Overview

This article mainly explains Expression trees. Expression trees are binary trees where the internal nodes denote operators ("+", "-", "/", "*","^") whereas the leaf nodes denote operands. These expression trees are used to implement or represent various kinds of expressions like infix, postfix, and prefix expressions.

What is the Expression Tree?

Expression trees are the binary trees that are used to express various expressions like infix, postfix, and prefix expressions. The internal nodes of this expression tree consist of operators like +, -, \*,/,^, etc. And the external nodes(leaf nodes) of the Expression tree contain the operands, on which operations are performed. The leaves of an Expression tree always contain the operands that can be of any data type like character, integer, double, etc.

The below-given image is an example of the Expression tree:

example-of-the-expression-tree

The below article clearly explains how the Expression tree is formed from the given expression.

Evaluating the Expression Represented by an Expression Tree

For evaluation of the expression which is represented by an Expression tree, we use recursion. We follow a preorder traversal, to find the value of the expression. Firstly the left subtree is processed and then the right subtree of the root node is processed in the recursion. Below are the steps to be followed to evaluate an expression from the expression tree:

Assume that ExpTree is the root of the Expression tree which is given. Following are the steps involved in

Let's understand more about how the expression is evaluated for the below image:

Consider this is the tree and the expression obtained is evaluated as:

example-of-the-expression-tree-2

This expression is formed for the Expression tree present in the first image.

How to Construct an Expression Tree?

After understanding the basic definition of Expression trees, let's understand the steps needed for the construction of the Expression tree using the given input expression. During the construction of the Expression tree, we use Stack (Stack is a data structure based on the Last In First Out Principle).
The given expression can be of any type like infix, postfix, etc. The most interesting fact about the Expression tree is that when we perform the postorder traversal on the Expression tree, we get the postfix expression, for the preorder traversal on the Expression tree we get the prefix expression, and similarly, inorder traversal gives the infix expression.
For the construction of the Expression tree from the given input expression we use stack data structure which handles elements in a Last In First Out manner. Stack helps in storing the root of the Expression tree until that point and adding nodes to the Expression tree once it goes into the next character of the given expression.

Algorithm:

Below is the algorithm to be followed for the construction of the Expression tree from the given expression using stack data structure:

We need to traverse through the given expression using a for loop on it, then follow the below steps for every character in the given expression:

If the character is an operand then we need to push that character into the stack.
If the character is an operator then pop two nodes from the stack and make them the children of the present operator, first popped node should be on the left side and the second popped node should be on the right side of the operator.
At last, we need to push this modified node into the stack again. The below image clearly explains the above step:

At any instant, the stack stores the root nodes of the subtrees of the final Expression tree. These nodes are combined as an operator arrives in the expression and the root node of a larger subtree is pushed into the stack. This continues till the expression is over.

At the end of traversal on the given expression, the stack contains only one node which is the root node of the Expression tree formed from the given expression. The root of the Expression tree is always an operator, and generally, the operator with the least precedence is present as the root of the Expression tree.

Example:

For a better understanding of the above algorithm, let's look at the below-given infix expression and convert it into the Expression tree.

Input:

The steps to be followed for the construction of the Expression tree are:

Start traversing the given expression using a for loop:

Firstly operand F is present, create a Tree node using F as data and push this node into the stack as shown in the below image. We are storing only the root of the tree formed until now in the stack. For a clear understanding, the below images below elaborately show the root of the subtree formed till now.
Now operand A is encountered. Create a node with value A and push it in the stack as shown in the below image.
For "^", firstly create the node with value "^", and we need to pop two nodes from the stack and make them the children of the newly formed node "^".
Push this newly formed node into the stack as shown in the below image:
Push the operand B into the stack by creating a node with B as data. Now nodes present in the stack are shown in the below image:
The next character which is present is "*", forming a node with "*". Pop two nodes from the stack and, make them the children nodes for the "*" node, which is shown in the below image. And push this newly formed node into the stack.
The next character which is encountered is C, create a Tree node with C as data and push it into the stack which is shown in the below image:
For the next character, form a node "/" and pop two nodes from the stack and make them children nodes for the newly formed node and push this node into the stack which is shown in the below image:
The next character is D, make a corresponding tree node and push it into the stack as shown in the below image:
The next character is "-", make a tree node and pop two elements from the stack and make them the child nodes for the newly formed node, and push this node into the stack which is shown in the below image:
The next character is an operand E, make the corresponding tree node with value E and push it into the stack which is shown in the below image:
The last character from the given expression is an operator "+", so make a tree node with "+" and pop two elements from the stack and make them the children nodes of the newly formed tree and push this node in the stack which is shown in the below image:
Finally the stack contains only one node which is the root node of the Expression tree representing the given expression. The Expression tree formed as shown in the below image:

Implementation

Below is the implementation for the construction of the Expression tree from the given expression:

C++ implementation: for the construction of the Expression tree using the above-discussed algorithm.

Output:

Java implementation: for the construction of the Expression tree using the above-discussed algorithm.

Output:

Explanation:

From the given expression the expression tree is constructed using the stack data structure. After the formation of the Expression tree, inorder traversal is performed and output is obtained by printing its inorder traversal.

Applications of the Expression Tree

Below mentioned are a few applications of the Expression Tree:

Expression tree is very helpful for evaluating the expressions, as it simplifies calculations by forming a tree.
Expression trees also help in enforcing the associativity of each operator in the given expression. For instance, the + operator is the left-associative, and / is the right-associative.
Expression trees are also very helpful for computing the infix expression, postfix expression, and prefix expression.

Conclusion

This article explains the concept of the Ean xpression tree and the process of construction of an expression tree.
The following observations from the formed EXpression tree are as follows:
- The operator which is present in the depth of the expression tree is considered to be having the highest priority. The greater the depth, the higher the priority.
- Operands are always the leaf nodes of Expression Trees.
- At any point, the stack stores the roots of subtrees of the final expression tree.
The main use of these expression trees is that it is used to evaluate, analyze and modify the various expressions efficiently.
Expression trees also help in enforcing the associativity of each operator in the given expression. Using expression trees we can enforce that the "+" operator is the left-associative and "/" is the right-associative.