×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

Expression Tree

In this article, we are going to see what an expression tree is and how to evaluate an expression tree? This problem has been featured in the interview round of Amazon. Submitted by Radib Kar, on February 07, 2019

Problem statement

Given an expression tree evaluate the expression tree.

Example

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

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

Solution

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


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.