python - 递归解析而不是使用 pop

Question

我将如何递归地解析 token ，而不是使用 pop？

def parse(tokens, i = 0):
    """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.

    NOTE:  YOU ARE NOT ALLOWED TO MUTATE 'tokens' (e.g. pop())!!!  YOU
        MUST USE 'i' TO GET THE CURRENT TOKEN OUT OF 'tokens'
    """
    i = 0
    if tokens.pop(0) == '+':
        return mkAddNode(parse(tokens), parse(tokens))
    elif tokens.pop(0) == '-':
        return mkSubtractNode(parse(tokens), parse(tokens))
    ....

我正在努力将其转换为使用递归调用，而不是在函数中使用 tokens.pop() 。

Answer 1

递归调用parse时递增i:

def parse(tokens, i=0):
    """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.

    NOTE:  YOU ARE NOT ALLOWED TO MUTATE 'tokens' (e.g. pop())!!!  YOU
        MUST USE 'i' TO GET THE CURRENT TOKEN OUT OF 'tokens'
    """
    if tokens[i] == '+':
        return mkAddNode(parse(tokens, i+1), parse(tokens, i+1))
    elif tokens[i] == '-':
        return mkSubtractNode(parse(tokens, i+1), parse(tokens, i+1))