// C++ program to evaluate an expression tree  #include     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 program to evaluate expression tree import java.lang.*; class GFG{   Node root; // Class to represent the nodes of syntax tree public 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 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');  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 

# Python program to evaluate expression tree # Class to represent the nodes of syntax tree class 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 it def 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 problem if __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# program to evaluate expression tree using 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  

<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('  
'+evalTree(root)); // This code is contributed by gauravrajput1 </script>