gistfile1.py

 mathOpPlusMinus = 'PLUS', 'MINUS' , 1
    
    mathOpTimesDivide = 'TIMES', 'DIVIDE' , 2
    
    childrenStack = []
    
    higherChildrenStack = []
    
    parentStack = []
    
    #if tokens are from different mathOp groups current token is going on higherChildrenStack
    def isInTheSameOpGroup (self,previousToken, nextToken):
        if previousToken in self.mathOpPlusMinus and nextToken not in self.mathOpTimesDivide:
            return False
        else:
            return True
    
    
    def composeAST(self):
        
       
        numberToken = ASTNode(self.listOfTokens[0])
        if self.listOfTokens[1].type in self.mathOpPlusMinus:
            self.childrenStack.append(numberToken)
        else:
            self.higherChildrenStack.append(self.listOfTokens[0])    

        self.parentStack.append(ASTNode(self.listOfTokens[1]))
        
        tokenPosition = 1
        
        for token in self.listOfTokens[2:len(self.listOfTokens)]:
        
            tokenPosition+=1
        
            if token.type == "NUMBER":
                #if tokens are in the same mathOpGroup, PLUS and MINUS group
                if self.isInTheSameOpGroup(self.listOfTokens[tokenPosition-1], self.listOfTokensp[tokenPosition+1] ) and self.listOfTokens[-1] not in self.mathOpTimesDivide:
                    if len(self.childrenStack) ==1 :
                        mathOpNode = ASTNode(self.parentStack.pop())
                        mathOpNode.addChild(ASTNode(token))
                        mathOpNode.addChild(self.childrenStack.pop())
                        self.childrenStack.append(mathOpNode)
                    else:
                        self.childrenStack.append(token)
                #if they are not in the same group add token on higherChildrenStack, but there can NOT be more then two children on hCS
                else:
                    if len(self.higherChildrenStack) ==1 :
                        mathOpNode = ASTNode(self.parentStack.pop())
                        mathOpNode.addChild(ASTNode(self.higherChildrenStack.pop()))
                        mathOpNode.addChild(ASTNode(token))
                        #check if the next token is higher or lower order token , if it belongs to higher order then return node to higherChildrenStack
                        if self.listOfTokens[tokenPosition+1] in self.mathOpTimesDivide:
                            self.higherChildrenStack.append(mathOpNode)
                        else:
                            #check the number of tokens/nodes  on childrenStack
                            if len(self.childrenStack) ==1 :
                                mathOpNode2 = ASTNode(self.parentStack.pop())
                                mathOpNode2.addChild(self.childrenStack.pop())
                                mathOpNode2.addChild(mathOpNode)
                            else:
                                self.childrenStack.append(mathOpNode)
            
                    #if there is 0 tokens/nodes on higerChildrenStack
                    else:
                        self.higherChildrenStack.append(token)
            else:
                self.parentStack.append(token)
         
        
        return None