# Expression Tree in Data Structure

** An expression tree is a binary tree data structure that is used to represent expressions in a mathematical or logical form**. It is built from individual operands and operators, where each node of the tree represents either an operand or an operator.

In an expression tree, the leaves of the tree represent the individual operands, while the internal nodes represent the operators. The expression tree is built such that the operators are placed at the internal nodes, and the operands are placed at the leaves.

The expression tree can be used to evaluate the expression, and it can also be used to generate the equivalent prefix, infix, and postfix notations of the expression.

For example, consider the infix expression "(2+3)*(4-1)". The corresponding expression tree would be:

```
*
/ \
+ -
/ \ / \
2 3 4 1
```

In this expression tree, the internal nodes represent the operators, while the leaves represent the operands. The evaluation of the expression can be done by traversing the expression tree in a postorder traversal and performing the operations at the internal nodes.

## Uses of Expression Tree in Data Structure

The expression tree data structure has several uses in computer science and programming, including:

**Evaluating expressions****:**The expression tree can be used to evaluate expressions, including arithmetic, logical, and Boolean expressions. The evaluation can be done by traversing the tree in a postorder traversal and performing the appropriate operations at each internal node.

**Simplifying expressions****:**The expression tree can be used to simplify expressions by performing algebraic manipulations, such as factoring, expanding, and cancelling out terms. The simplification can be done by manipulating the nodes of the tree and creating a new expression tree.

**Generating code:**The expression tree can be used to generate code for a given expression. This is particularly useful in compilers, where the expression tree can be converted into machine code or assembly language.

**Parsing expressions:**The expression tree can be used to parse expressions and convert them into a form that is easier to work with. This is useful in applications such as query languages and regular expressions.

**Visualization****:**The expression tree can be used to visualize expressions, which can aid in understanding and debugging complex expressions. The tree can be displayed using graphical tools, such as tree diagrams and graph visualization software.

## Types of Expression Trees

There are several types of expression trees, depending on the type of expression being represented. Some of the common types of expression trees are:

**Arithmetic expression tree****:**This type of expression tree is used to represent arithmetic expressions, such as addition, subtraction, multiplication, and division.*The internal nodes of the tree represent the arithmetic operators, while the leaf nodes represent the operands*.

**Boolean expression tree:**This type of expression tree is used to represent Boolean expressions, such as AND, OR, NOT, and XOR.*The internal nodes of the tree represent the Boolean operators, while the leaf nodes represent the Boolean values (True or False).*

**Prefix expression tree****:**This type of expression tree is used to represent expressions in prefix notation, where the operator appears before the operands.*The internal nodes of the tree represent the operators, while the leaf nodes represent the operands.*

**Postfix expression tree**: This type of expression tree is used to represent expressions in postfix notation, where the operator appears after the operands.*The internal nodes of the tree represent the operators, while the leaf nodes represent the operands.*

**Infix expression tree****:**This type of expression tree is used to represent expressions in infix notation, where the operator appears between the operands.*The internal nodes of the tree represent the operators, while the leaf nodes represent the operands.*

**Function expression tree**: This type of expression tree is used to represent expressions that involve functions, such as trigonometric functions, logarithmic functions, and exponential functions. The internal nodes of the tree represent the function operators, while the leaf nodes represent the arguments.

## How to Create an Expression Tree in C

To create an expression tree in C, you can follow these steps:

1. Define a node structure for the expression tree, which should have pointers to its left and right subtrees, as well as a value field to store the operand or operator.

```
struct TreeNode {
char value;
struct TreeNode* left;
struct TreeNode* right;
};
```

2. Write a function to create a new node for the expression tree. The function should allocate memory for the new node, set its value to the given operand or operator, and initialize its left and right subtrees to NULL.

```
struct TreeNode* createNode(char value) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
```

3. Write a function to build the expression tree from a given postfix expression. The function should use a stack to keep track of the operands and operators, and build the expression tree by popping operands and operators from the stack and adding them as nodes to the tree.

```
struct TreeNode* buildExpressionTree(char postfix[]) {
int length = strlen(postfix);
struct TreeNode* stack[length];
int top = -1;
for (int i = 0; i < length; i++) {
if (isdigit(postfix[i])) {
struct TreeNode* operand = createNode(postfix[i]);
stack[++top] = operand;
}
else {
struct TreeNode* operator = createNode(postfix[i]);
operator->right = stack[top--];
operator->left = stack[top--];
stack[++top] = operator;
}
}
return stack[top];
}
```

4. To test the expression tree, you can write a function to evaluate the expression tree by traversing it in a postorder traversal and performing the appropriate operations at each internal node.

```
int evaluateExpressionTree(struct TreeNode* root) {
if (!root)
return 0;
if (!root->left && !root->right)
return root->value - '0';
int leftOperand = evaluateExpressionTree(root->left);
int rightOperand = evaluateExpressionTree(root->right);
switch (root->value) {
case '+': return leftOperand + rightOperand;
case '-': return leftOperand - rightOperand;
case '*': return leftOperand * rightOperand;
case '/': return leftOperand / rightOperand;
}
return 0;
}
```

Overall, creating an expression tree in C involves defining the node structure, writing functions to create nodes and build the tree, and testing the tree by evaluating its expression.

## Evaluation of an Expression Tree

Evaluation of an expression tree involves traversing the tree and performing the appropriate operations at each internal node to compute the final result of the expression. The following steps can be followed to evaluate an expression tree:

- Traverse the expression tree in a postorder traversal.

- If the current node is a leaf node, return its value.

- If the current node is an internal node, recursively evaluate its left and right subtrees.

- Perform the appropriate operation at the current node, based on its value.

- Return the final result of the expression.

## Implementation of Expression Tree in C++

Here is an implementation of an expression tree in C++:

```
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;
// Define the node structure for the expression tree
struct TreeNode {
char value;
TreeNode* left;
TreeNode* right;
TreeNode(char val) : value(val), left(NULL), right(NULL) {}
};
// Create a new node for the expression tree
TreeNode* createNode(char value) {
return new TreeNode(value);
}
// Build the expression tree from a given postfix expression
TreeNode* buildExpressionTree(string postfix) {
stack<TreeNode*> st;
for (int i = 0; i < postfix.size(); i++) {
char c = postfix[i];
if (isdigit(c)) {
TreeNode* operand = createNode(c);
st.push(operand);
}
else {
TreeNode* op = createNode(c);
op->right = st.top(); st.pop();
op->left = st.top(); st.pop();
st.push(op);
}
}
return st.top();
}
// Evaluate the expression tree
int evaluateExpressionTree(TreeNode* root) {
if (!root)
return 0;
if (!root->left && !root->right)
return root->value - '0';
int leftOperand = evaluateExpressionTree(root->left);
int rightOperand = evaluateExpressionTree(root->right);
switch (root->value) {
case '+': return leftOperand + rightOperand;
case '-': return leftOperand - rightOperand;
case '*': return leftOperand * rightOperand;
case '/': return leftOperand / rightOperand;
}
return 0;
}
// Test the expression tree
int main() {
string postfix = "45+7*";
TreeNode* root = buildExpressionTree(postfix);
int result = evaluateExpressionTree(root);
cout << "Result: " << result;}
```

**Output**:

```
/tmp/XWvNMi4nJR.o
Result: 63
```

## Generation of Expression Tree

The process of generating an expression tree involves constructing a tree data structure from an expression in infix notation. The general steps to generate an expression tree are as follows:

- Convert the infix expression to postfix notation using the shunting yard algorithm or a similar method.

- Create an empty stack to hold the nodes of the expression tree.

- Traverse the postfix expression from left to right.

- For each operand, create a leaf node with the operand as its value and push it onto the stack.

- For each operator, pop the top two nodes from the stack and create a new internal node with the operator as its value and the two nodes as its left and right children. Push the new node onto the stack.

- Repeat steps 4 and 5 until the end of the postfix expression is reached.

- The final node left on the stack is the root of the expression tree.