Parse function, python (binary search tree)

Question

I am trying to implement a parse function. "From an infix stream of tokens, and the current index into the token stream, construct and return the tree, as a collection of Nodes, that represents the expression" This is what i have came up with so far:

def parse(tokens, i = 0):
   lst = []
   token = lst[i]
   left, i = parse(lst, i+1)
   right, i = parse(lst, i+1)

   if token.isdigit():
       return mkLiteralNode(token)
   elif token.isidentifier():
       return mkVariableNode(token)
   else:
       left, i = parse(lst, i+1)
       right, i = parse(lst, i+1)

   return True

So in general, token.isdigit means that this command has to return an integer, which is mkLiteralNode, and token.isidentifier should return variable, or mkVariableNode. I am getting an error when testing this function and the error is:

    token = lst[i]
TypeError: 'int' object is not subscriptable

How can i fix this?

Answer 1

Ok sorry for inconvenience, but i researched and found another approach to this problem:

def parse(tokens):

   tok = next(tokens)

   if tok.isdigit():
       return ('literal', tok)
   elif tok == "+":
       return ('add', parse(tokens), parse(tokens))
   elif tok == '-':
       return ('subtract', parse(tokens), parse(tokens))
   elif tok == "*":
       return ('multiply', parse(tokens), parse(tokens))
   elif tok == "//":
       return ('divide', parse(tokens), parse(tokens))
   else:
       return ('variable', tok)

Answer 2

The error is right in the previous line:

lst = 0

You are making lst an int and then trying to access it as a list which throws the error you are seeing. token = lst[i] probably should be:

token = tokens[i]