Evaluation of Expression Tree | C ++ program to evaluate an expression tree ; Class to represent the nodes of syntax tree ; Utility function to return the integer value of a given string ; Check if the integral value is negative or not If it is not negative , generate the number normally ; If it is negative , calculate the + ve number first ignoring the sign and invert the sign at the end ; This function receives a node of the syntax tree and recursively evaluates it ; empty tree ; leaf node i . e , an integer ; Evaluate left subtree ; Evaluate right subtree ; Check which operator to apply ; create a syntax tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; class node { public : string info ; node * left = NULL , * right = NULL ; node ( string x ) { info = x ; } } ; int toInt ( string s ) { int num = 0 ; if ( s [ 0 ] != ' - ' ) for ( int i = 0 ; i < s . length ( ) ; i ++ ) num = num * 10 + ( int ( s [ i ] ) - 48 ) ; else for ( int i = 1 ; i < s . length ( ) ; i ++ ) { num = num * 10 + ( int ( s [ i ] ) - 48 ) ; num = num * -1 ; } return num ; } int eval ( node * root ) { if ( ! root ) return 0 ; if ( ! root -> left && ! root -> right ) return toInt ( root -> info ) ; int l_val = eval ( root -> left ) ; int r_val = eval ( root -> right ) ; 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 ; } int main ( ) { 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 ; }