Given a simple expression tree, consisting of basic binary operators i.e., + , – ,* and / and some integers, evaluate the expression tree.
Examples:
Input: Root node of the below tree
Output:100
Input: Root node of the below tree
Output: 110
Approach: The approach to solve this problem is based on following observation:
As all the operators in the tree are binary, hence each node will have either 0 or 2 children. As it can be inferred from the examples above, all the integer values would appear at the leaf nodes, while the interior nodes represent the operators.
Therefore we can do inorder traversal of the binary tree and evaluate the expression as we move ahead.
To evaluate the syntax tree, a recursive approach can be followed.
Algorithm:
- Let t be the syntax tree
- If t is not null then
- If t.info is operand then
- Return t.info
- Else
- A = solve(t.left)
- B = solve(t.right)
- return A operator B, where operator is the info contained in t
Below is the implementation of the above approach:
C++
// C++ program to evaluate an expression tree #include <bits/stdc++.h> using namespace std; // Class to represent the nodes of syntax tree class node { public: string info; node *left = NULL, *right = NULL; node(string x) { info = x; } }; // Utility function to return the integer value // of a given string int toInt(string s) { int num = 0; // Check if the integral value is // negative or not // If it is not negative, generate the number // normally if(s[0]!='-') for (int i=0; i<s.length(); i++) num = num*10 + (int(s[i])-48); // If it is negative, calculate the +ve number // first ignoring the sign and invert the // sign at the end else { for (int i=1; i<s.length(); i++) num = num*10 + (int(s[i])-48); num = num*-1; } return num; } // This function receives a node of the syntax tree // and recursively evaluates it int eval(node* root) { // empty tree if (!root) return 0; // leaf node i.e, an integer if (!root->left && !root->right) return toInt(root->info); // Evaluate left subtree int l_val = eval(root->left); // Evaluate right subtree int r_val = eval(root->right); // Check which operator to apply if (root->info=="+") return l_val+r_val; if (root->info=="-") return l_val-r_val; if (root->info=="*") return l_val*r_val; return l_val/r_val; } //driver function to check the above program int main() { // create a syntax tree node *root = new node("+"); root->left = new node("*"); root->left->left = new node("5"); root->left->right = new node("-4"); root->right = new node("-"); root->right->left = new node("100"); root->right->right = new node("20"); cout << eval(root) << endl; delete(root); root = new node("+"); root->left = new node("*"); root->left->left = new node("5"); root->left->right = new node("4"); root->right = new node("-"); root->right->left = new node("100"); root->right->right = new node("/"); root->right->right->left = new node("20"); root->right->right->right = new node("2"); cout << eval(root); return 0; } |
Java
// Java program to evaluate expression treeimport java.lang.*;class GFG{ Node root;// Class to represent the nodes of syntax treepublic static class Node { String data; Node left, right; Node(String d) { data = d; left = null; right = null; }}private static int toInt(String s){ int num = 0; // Check if the integral value is // negative or not // If it is not negative, generate // the number normally if (s.charAt(0) != '-') for(int i = 0; i < s.length(); i++) num = num * 10 + ((int)s.charAt(i) - 48); // If it is negative, calculate the +ve number // first ignoring the sign and invert the // sign at the end else { for(int i = 1; i < s.length(); i++) num = num * 10 + ((int)(s.charAt(i)) - 48); num = num * -1; } return num;}// This function receives a node of the syntax// tree and recursively evaluate itpublic static int evalTree(Node root){ // Empty tree if (root == null) return 0; // Leaf node i.e, an integer if (root.left == null && root.right == null) return toInt(root.data); // Evaluate left subtree int leftEval = evalTree(root.left); // Evaluate right subtree int rightEval = evalTree(root.right); // Check which operator to apply if (root.data.equals("+")) return leftEval + rightEval; if (root.data.equals("-")) return leftEval - rightEval; if (root.data.equals("*")) return leftEval * rightEval; return leftEval / rightEval;}// Driver codepublic static void main(String[] args){ // Creating a sample tree Node root = new Node("+"); root.left = new Node("*"); root.left.left = new Node("5"); root.left.right = new Node("-4"); root.right = new Node("-"); root.right.left = new Node("100"); root.right.right = new Node("20"); System.out.println(evalTree(root)); root = null; // Creating a sample tree root = new Node("+"); root.left = new Node("*"); root.left.left = new Node("5"); root.left.right = new Node("4"); root.right = new Node("-"); root.right.left = new Node("100"); root.right.right = new Node("/"); root.right.right.left = new Node("20"); root.right.right.right = new Node("2"); System.out.println(evalTree(root));}}// This code is contributed by Ankit Gupta |
Python3
# Python program to evaluate expression tree# Class to represent the nodes of syntax treeclass node: def __init__(self, value): self.left = None self.data = value self.right = None# This function receives a node of the syntax tree# and recursively evaluate itdef evaluateExpressionTree(root): # empty tree if root is None: return 0 # leaf node if root.left is None and root.right is None: return int(root.data) # evaluate left tree left_sum = evaluateExpressionTree(root.left) # evaluate right tree right_sum = evaluateExpressionTree(root.right) # check which operation to apply if root.data == '+': return left_sum + right_sum elif root.data == '-': return left_sum - right_sum elif root.data == '*': return left_sum * right_sum else: return left_sum // right_sum# Driver function to test above problemif __name__ == '__main__': # creating a sample tree root = node('+') root.left = node('*') root.left.left = node('5') root.left.right = node('-4') root.right = node('-') root.right.left = node('100') root.right.right = node('20') print (evaluateExpressionTree(root)) root = None # creating a sample tree root = node('+') root.left = node('*') root.left.left = node('5') root.left.right = node('4') root.right = node('-') root.right.left = node('100') root.right.right = node('/') root.right.right.left = node('20') root.right.right.right = node('2') print (evaluateExpressionTree(root))# This code is contributed by Harshit Sidhwa |
C#
// C# program to evaluate expression treeusing System;public class GFG { // Class to represent the nodes of syntax tree public class Node { public String data; public Node left, right; public Node(String d) { data = d; left = null; right = null; } } private static int toInt(String s) { int num = 0; // Check if the integral value is // negative or not // If it is not negative, generate // the number normally if (s[0] != '-') for (int i = 0; i < s.Length; i++) num = num * 10 + ((int) s[i] - 48); // If it is negative, calculate the +ve number // first ignoring the sign and invert the // sign at the end else { for (int i = 1; i < s.Length; i++) num = num * 10 + ((int) (s[i]) - 48); num = num * -1; } return num; } // This function receives a node of the syntax // tree and recursively evaluate it public static int evalTree(Node root) { // Empty tree if (root == null) return 0; // Leaf node i.e, an integer if (root.left == null && root.right == null) return toInt(root.data); // Evaluate left subtree int leftEval = evalTree(root.left); // Evaluate right subtree int rightEval = evalTree(root.right); // Check which operator to apply if (root.data.Equals("+")) return leftEval + rightEval; if (root.data.Equals("-")) return leftEval - rightEval; if (root.data.Equals("*")) return leftEval * rightEval; return leftEval / rightEval; } // Driver code public static void Main(String[] args) { // Creating a sample tree Node root = new Node("+"); root.left = new Node("*"); root.left.left = new Node("5"); root.left.right = new Node("-4"); root.right = new Node("-"); root.right.left = new Node("100"); root.right.right = new Node("20"); Console.WriteLine(evalTree(root)); root = null; // Creating a sample tree root = new Node("+"); root.left = new Node("*"); root.left.left = new Node("5"); root.left.right = new Node("4"); root.right = new Node("-"); root.right.left = new Node("100"); root.right.right = new Node("/"); root.right.right.left = new Node("20"); root.right.right.right = new Node("2"); Console.WriteLine(evalTree(root)); }}// This code is contributed by umadevi9616 |
Javascript
<script>// javascript program to evaluate expression tree var root; // Class to represent the nodes of syntax tree class Node { constructor(val) { this.data = val; this.left = null; this.right = null; } } function toInt( s) { var num = 0; // Check if the integral value is // negative or not // If it is not negative, generate // the number normally if (s.charAt(0) != '-') for (i = 0; i < s.length; i++) num = num * 10 + ( s.charCodeAt(i) - 48); // If it is negative, calculate the +ve number // first ignoring the sign and invert the // sign at the end else { for (i = 1; i < s.length; i++) num = num * 10 + (s.charCodeAt(i) - 48); num = num * -1; } return num; } // This function receives a node of the syntax // tree and recursively evaluate it function evalTree(root) { // Empty tree if (root == null) return 0; // Leaf node i.e, an integer if (root.left == null && root.right == null) return toInt(root.data); // Evaluate left subtree var leftEval = evalTree(root.left); // Evaluate right subtree var rightEval = evalTree(root.right); // Check which operator to apply if (root.data === ("+")) return leftEval + rightEval; if (root.data === ("-")) return leftEval - rightEval; if (root.data === ("*")) return leftEval * rightEval; return leftEval / rightEval; } // Driver code // Creating a sample tree var root = new Node("+"); root.left = new Node("*"); root.left.left = new Node("5"); root.left.right = new Node("-4"); root.right = new Node("-"); root.right.left = new Node("100"); root.right.right = new Node("20"); document.write(evalTree(root)); root = null; // Creating a sample tree root = new Node("+"); root.left = new Node("*"); root.left.left = new Node("5"); root.left.right = new Node("4"); root.right = new Node("-"); root.right.left = new Node("100"); root.right.right = new Node("/"); root.right.right.left = new Node("20"); root.right.right.right = new Node("2"); document.write("<br/>"+evalTree(root));// This code is contributed by gauravrajput1</script> |
Output
60 110
Time Complexity: O(n), as each node is visited once.
Auxiliary Space: O(n)
This article is contributed by Ashutosh Kumar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
