Q:

Given an expression tree evaluate the expression tree

mahmoud2506
Save to bookmark
|
2022-04-30
|
  230 
0

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
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-30
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Interview C++ coding problems/challenges | tree
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given a Binary Tree and a number K. Print all node... >>
<< Write a function to detect if two trees are isomor...