Evaluation of Expression Tree | Class to represent the nodes of syntax tree ; This function receives a node of the syntax tree and recursively evaluate it ; empty tree ; leaf node ; evaluate left tree ; evaluate right tree ; check which operation to apply ; Driver function to test above problem
class node : NEW_LINE INDENT def __init__ ( self , value ) : NEW_LINE INDENT self . left = None NEW_LINE self . data = value NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def evaluateExpressionTree ( root ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return 0 NEW_LINE DEDENT if root . left is None and root . right is None : NEW_LINE INDENT return int ( root . data ) NEW_LINE DEDENT left_sum = evaluateExpressionTree ( root . left ) NEW_LINE right_sum = evaluateExpressionTree ( root . right ) NEW_LINE if root . data == ' + ' : NEW_LINE INDENT return left_sum + right_sum NEW_LINE DEDENT elif root . data == ' - ' : NEW_LINE INDENT return left_sum - right_sum NEW_LINE DEDENT elif root . data == ' * ' : NEW_LINE INDENT return left_sum * right_sum NEW_LINE DEDENT else : NEW_LINE INDENT return left_sum / right_sum NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = node ( ' + ' ) NEW_LINE root . left = node ( ' * ' ) NEW_LINE root . left . left = node ( '5' ) NEW_LINE root . left . right = node ( '4' ) NEW_LINE root . right = node ( ' - ' ) NEW_LINE root . right . left = node ( '100' ) NEW_LINE root . right . right = node ( '20' ) NEW_LINE print evaluateExpressionTree ( root ) NEW_LINE root = None NEW_LINE root = node ( ' + ' ) NEW_LINE root . left = node ( ' * ' ) NEW_LINE root . left . left = node ( '5' ) NEW_LINE root . left . right = node ( '4' ) NEW_LINE root . right = node ( ' - ' ) NEW_LINE root . right . left = node ( '100' ) NEW_LINE root . right . right = node ( ' / ' ) NEW_LINE root . right . right . left = node ( '20' ) NEW_LINE root . right . right . right = node ( '2' ) NEW_LINE print evaluateExpressionTree ( root ) NEW_LINE DEDENT