Expression Tree | An expression tree node ; A utility function to check if ' c ' is an operator ; A utility function to do inorder traversal ; Returns root of constructed tree for given postfix expression ; Traverse through every character of input expression ; if operand , simply push into stack ; Operator ; Pop two top nodes ; make them children ; Add this subexpression to stack ; Only element will be the root of expression tree ; Driver program to test above
class Et : NEW_LINE INDENT def __init__ ( self , value ) : NEW_LINE INDENT self . value = value NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def isOperator ( c ) : NEW_LINE INDENT if ( c == ' + ' or c == ' - ' or c == ' * ' or c == ' / ' or c == ' ^ ' ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT def inorder ( t ) : NEW_LINE INDENT if t is not None : NEW_LINE INDENT inorder ( t . left ) NEW_LINE print t . value , NEW_LINE inorder ( t . right ) NEW_LINE DEDENT DEDENT def constructTree ( postfix ) : NEW_LINE INDENT stack = [ ] NEW_LINE for char in postfix : NEW_LINE INDENT if not isOperator ( char ) : NEW_LINE INDENT t = Et ( char ) NEW_LINE stack . append ( t ) NEW_LINE DEDENT else : NEW_LINE INDENT t = Et ( char ) NEW_LINE t1 = stack . pop ( ) NEW_LINE t2 = stack . pop ( ) NEW_LINE t . right = t1 NEW_LINE t . left = t2 NEW_LINE stack . append ( t ) NEW_LINE DEDENT DEDENT t = stack . pop ( ) NEW_LINE return t NEW_LINE DEDENT postfix = " ab + ef * g * - " NEW_LINE r = constructTree ( postfix ) NEW_LINE print " Infix ▁ expression ▁ is " NEW_LINE inorder ( r ) NEW_LINE