listing the _buildstring helper method class expressiontree recursively builds string representation of the expression tree def _buildstringselftreenode )if the node is leafit' an operand if treenode left is none and treenode right is none return strtreenode element else otherwiseit' an operator expstr '(expstr +self _buildstringtreenode left expstr +strtreenode element expstr +self _buildstringtreenode right expstr +')return expstr their results are needed by the operation furtherthe division cannot be evaluated until the subtraction of ( has been computed we have already discussed two versions of an algorithm that processes both subtrees of node before the node itself rememberthis was the technique employed by both the preorder and postorder traversals we can use one of these to evaluate an expression tree the difference is that the visit operation is only applied to the operator (interiornodes and visit becomes the evaluation of the operation applied to the value of both subtrees the recursive function for evaluating an expression tree and returning the result is provided in listing listing evaluate an expression tree class expressiontree def _evaltreeselfsubtreevardict )see if the node is leaf nodein which case return its value if subtree left is none and subtree right is none is the operand literal digitif subtree element >' and subtree element <' return int(subtree elementelse or is it variableassert subtree element in vardict"invalid variable return vardict[subtree elementotherwiseit' an operator that needs to be computed else evaluate the expression in the left and right subtrees lvalue _evaltreesubtree leftvardict rvalue _evaltreesubtree rightvardict evaluate the operator using helper method return computeoplvaluesubtree elementrvalue compute the arithmetic operation based on the supplied op string def _computeopleftopright )