DAA: Expression Trees
Expression Trees
Expression trees are those in which the leaf nodes have the values to be operated, and internal nodes contain the operator on which the leaf node will be performed.
Example: 3 + ((5 + 9) * 2) will have an expression tree as follows:
Take a tree T and if it is not null
If t.value is an operand, then.
Return t.value
A = solve(t.left) // Recur for left
B = solve(t.right) // Recur for right
--> Compute applies operator 't.value' on A and B, and return value
Return calculate(A, B, t.value)
Ways and data structure to create an expression tree is
The optimal data structure to be used here is stack. Iterate in the postfix expression and do the following steps:
- If we strike an operand in expression, push in the stack.
- If we take and pop two values from stack, push them in current mode by making them child.
C++ code:
#include <bits/stdc++.h>
using namespace std;
// node class for expression tree
class node {
public:
char data;
node *left, *right;
node(char data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
//expression tree class
class exp_tree {
string postfix_exp;
node* root;
public:
exp_tree(string postfix_exp)
{
this->postfix_exp = postfix_exp;
root = NULL;
create_tree(postfix_exp);
}
private:
bool is_operator(char c)
{
if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^') // if given char is operator
{
return true; // then return true
}
return false; // else return false
}
void create_tree(string exp)
{
int len = exp.length();
stack<node*> s;
root = new node(exp[len - 1]);
s.push(root);
for (int i = len - 2; i >= 0; i--) // travel on rest of the postfix expression
{
node* curr_node = s.top();
if (curr_node->right == NULL) // if right node of current node is NULL
{
node* temp = new node(exp[i]);
curr_node->right = temp;
if (is_operator(exp[i])) {
s.push(temp);
}
}
else {
node* temp = new node(exp[i]);
curr_node->left = temp;
// if no child node of current node is NULL
s.pop(); // pop current from stack
if (is_operator(exp[i])) {
s.push(temp);
}
}
}
}
void inorder_traversal(node* head) // inorder traversal of expression tree
{
// inorder traversal => left,root,right
if (head->left != NULL) {
inorder_traversal(head->left);
}
cout << head->data << " ";
if (head->right != NULL) {
inorder_traversal(head->right);
}
return;
}
public:
void infix_exp() // inorder traversal of expression tree will give infix expression
{
inorder_traversal(root);
cout << endl;
return;
}
};
int main()
{
string postfix_exp = "ab+ef*g*-";
exp_tree et(postfix_exp);
et.infix_exp();
return 0;
}
Output:
a + b - e * f * g
Python code:
#stack class class stack: def __init__(self): self.arr = [] def push(self, data): self.arr.append(data) def pop(self): try: return self.arr.pop(-1) except: pass def top(self): try: return self.arr[-1] except: pass def size(self): return len(self.arr) #node class for expression tree class node: def __init__(self, data): self.data = data self.left = None self.right = None #expression tree class class exp_tree: def __init__(self, postfix_exp): self.exp = postfix_exp self.root = None self.createTree(self.exp) def isOperator(self, char): optr = ['+', '-', '*', '/', '^'] if char in optr: # if given char is operator return True # then return true return False # else return false def createTree(self, exp): s = stack() # store those operator node whose any child node is NULL self.root = node(exp[-1]) #last character of postfix expression is always an operator s.push(self.root) #travel on rest of the postfix expression for i in "".join(reversed(exp[:-1])): curr_node = s.top() if not curr_node.right: # if right node of current node is NULL temp = node(i) curr_node.right = temp if self.isOperator(i): s.push(temp) else: # if left node of current node is NULL temp = node(i) curr_node.left = temp #if no child node of current node is NULL s.pop() # pop current from stack if self.isOperator(i): s.push(temp) def inorder(self, head): # inorder traversal of expression tree #inorder traversal = > left, root, right if head.left: self.inorder(head.left) print(head.data, end=" ") if head.right: self.inorder(head.right) def infixExp(self): # inorder traversal of expression tree give infix expression self.inorder(self.root) print() if __name__ == "__main__": postfixExp = "ab+ef*g*-" et = exp_tree(postfixExp) et.infixExp()
Output:
a + b - e * f * g