building an expression tree the constructor for the expressiontree classfrom code fragment provides basic functionality for combining existing trees to build larger expression trees howeverthe question still remains how to construct tree that represents an expression for given stringsuch as ((( + ) )/(( - )+ )to automate this processwe rely on bottom-up construction algorithmassuming that string can first be tokenized so that multidigit numbers are treated atomically (see exercise - )and that the expression is fully parenthesized the algorithm uses stack while scanning tokens of the input expression to find valuesoperatorsand right parentheses (left parentheses are ignored when we see an operator *we push that string on the stack when we see literal value vwe create single-node expression tree storing vand push on the stack when we see right parenthesiswe pop the top three items from the stack swhich represent subexpression ( we then construct tree using trees for and as subtrees of the root storing *and push the resulting tree back on the stack we repeat this until the expression has been processedat which time the top element on the stack is the expression tree for the total running time is (nan implementation of this algorithm is given in code fragment in the form of stand-alone function named build expression treewhich produces and returns an appropriate expressiontree instanceassuming the input has been tokenized def build expression tree(tokens) """returns an expressiontree based upon by tokenized expression "" =[we use python list as stack for in tokenst is an operator symbol if in +- * append(tpush the operator symbol consider to be literal elif not in ( append(expressiontree( )push trivial tree storing value compose new tree from three constituent parts elif = right popright subtree as per lifo op popoperator symbol left popleft subtree append(expressiontree(opleftright)repush tree we ignore left parenthesis return popcode fragment implementation of build expression tree that produces an expressiontree from sequence of tokens representing an arithmetic expression