Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

HI I have a function parse() that takes a list of operators and operands (ex ['+', '20', '10']) tokens, and an index i, and constructs a tree from them. When an operator ( a node with a .left and .right ) is found, the function goes down until it reaches a literal ( a number ) or a letter variable. The problem is I would like the index i that is changing within the recursion to stay modified when the recursion on the left side is done and the function moves on to the right side. For example, to get this tree from [-, //, y, 2, x]:

enter image description here

I have written this:

def parse(tokens, i):
    """parse: tuple(String) * int -> (Node, int)
    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 represent the expression."""

    if tokens[i].isdigit():
        return mkLiteralNode(tokens[i])

    elif tokens[i] == "+":
        return mkAddNode(parse( tokens, i + 1 ), parse( tokens, i + 2 )) # first argument is the node.left, second is the node.right
    elif tokens[i] == "-":
        return mkSubtractNode(parse( tokens, i + 1 ), parse( tokens, i + 2 ))
    elif tokens[i] == "*":
        return mkMultiplyNode(parse( tokens, i + 1 ), parse( tokens, i + 2 ))
    elif tokens[i] == "//":
        return mkDivideNode(parse( tokens, i + 1 ), parse( tokens, i + 2 ))

    else:
        return mkVariableNode(tokens[i])

When the SubtractNode is made, i is 0 and then increments normally, but when the left side is done i is again 0 and the parse(tokens, i + 2) points to the y instead of the x, making something like this:

enter image description here

How is it possible to make the above tree without using pop() in tokens?

share|improve this question
 
You said, infix expression. Then how can i be 0 when mkSubtractNode is called? What would be value in tokens? –  thefourtheye 15 hours ago
 
Are you sure you know what infix is? This looks like prefix notation. –  user2357112 15 hours ago

2 Answers

up vote 3 down vote accepted

It's much easier to write such things, when you think of your tokens list as of an object, that is itself responsible for storing its position. That's why in general, the tokens should come from a Lexer, which usually just has one method: next_token. We'll simulate this with an iterator:

def parse(tokens):
    """parse: tokens_iter or generator -> Node
    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 represent the expression."""

    next_tok = next(tokens)

    if next_tok.isdigit():
        return ('literal', next_tok)

    elif next_tok == "+":
        return ('add', parse( tokens ), parse( tokens )) # first argument is the node.left, second is the node.right
    elif next_tok == "-":
        return ('sub', parse( tokens ), parse( tokens ))
    elif next_tok == "*":
        return ('mul', parse( tokens ), parse( tokens ))
    elif next_tok == "//":
        return ('div', parse( tokens ), parse( tokens ))

    else:
        return ('variable', next_tok )

# And, example:
print(parse(iter(['-', '//', 'y', '2', 'x'])))

That will print:

('sub', ('div', ('variable', 'y'), ('literal', '2')), ('variable', 'x'))

You'll also need to handle the StopIteration exception, and turn it into a meaningful ParseError.

share|improve this answer
up vote 0 down vote

Have parse return the index of the next unused token as well as the parse tree, and use that to determine where to continue parsing. For example:

left, rightIndex = parse(tokens, i+1)
right, returnIndex = parse(tokens, nextIndex)
return mkWhateverNode(left, right), returnIndex
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.