Q:

# Expression Tree

Given an expression tree evaluate the expression tree.

Example:

```        *
/ \
+   -
/ \ / \
7  4 6  3

The evaluation will be:
(7+4)*(6-3)
=11* 3=33```

Expression tree:

Any infix expression can be converted to an expression tree whose leaf nodes are all operands & intermediate nodes are operators.

Algorithm to evaluate an expression tree

Expression tree can be evaluated using the following algorithm

```    IF root is operator
Result =  evaluation of left child treeoperator
(root->data) evaluation of right child tree
ELSE
Result = root->data //operand
```

This can be constructed using a recursive function evalTree (root of expression tree)

Pre-requisite functions:

isOperator(string s) = Boolean function to check whether root data is operator or not

```ex:
isOperator("*") returns true where as isOperator("12") returns false
-----------------------------------------------------------------

value(string s)= returns value of the operand represented in string from
ex:
value("12") returns 12
-----------------------------------------------------------------

Evaluate (int a, int b, string s):  returns the result of evaluation
where a, b are operands and s is the operator
IF(s=="*")
return a*b;
ELSE IF(s=="/")
return a/b;
ELSE IF(s=="+")
return a+b;
ELSE
return a-b;
```
```FUNCTION evalTree(root)
1.  Base case
IF (root==NULL)
Return 0;
2.  IF (isOperator(root->data))
Evaluate left subtree (say a),
evaluate right subtree(say b) and return a root->data b
Set a=evalTree (root->left);
Set b=evalTree (root->left);
Return evaluate(a, b, tree->data);
ELSE
Return value (root->data); //return operand value
END FUNCTION```

C++ implementation:

``````#include <bits/stdc++.h>
using namespace std;

// TreeNode node type
class TreeNode{
public:
string data;       //data
TreeNode *left;    //pointer to left child
TreeNode *right;   //pointer to right child
};

// creating new node
TreeNode* newnode(string s)
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = s;
node->left = NULL;
node->right = NULL;

return(node);
}

//evalutes a root->data b
int evaluate(int a, int b, string s){
if(s=="*")
return a*b;
else if(s=="/")
return a/b;
else if(s=="+")
return a+b;
else
return a-b;
}

//returns operand value
int value(string s){
int sum=0,p=1;
for(int i=s.length()-1;i>=0;i--){
sum+=p*(s[i]-'0');
p*=10;
}
return sum;
}

//function to check whether operator
bool isOperator(string s){
if(s=="*" || s=="/" || s=="-" || s=="+" )
return true;
return false;
}

//recursive functuon to evaluate
int evalTree(TreeNode* root)
{
if(!root)
return 0;

if(isOperator(root->data)){
int a=evalTree(root->left);
int b=evalTree(root->right);
return evaluate(a,b,root->data);
}
else{
return value(root->data);
}
}

int main(){
cout<<"tree is built as per example\n";

TreeNode *root=newnode("*");

root->left= newnode("+");
root->right= newnode("-");
root->right->right=newnode("3");
root->right->left=newnode("6");
root->left->left=newnode("7");
root->left->right=newnode("4");

cout<<"The evaluation of the expression tree results to: "<<evalTree(root)<<endl;

return 0;
}
``````

Output

```tree is built as per example
The evaluation of the expression tree results to: 33```