Maximum Recursion exceeded

Question

I have an error, that stated:

    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
  File "derpAgain.py", line 14, in parse
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
  File "derpAgain.py", line 13, in parse
    if tokens[0] == "+":
RuntimeError: maximum recursion depth exceeded in comparison

I have no idea why I got that error. I double checked, see nothing wrong with it.

from derp_node import *

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'
    """
    #t = tokens.pop(0)
    if tokens[0] == "+":
        return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
    elif tokens[0] == "-":
        return mkSubstractNode(parse(tokens, i + 1), parse(tokens, i + 1))
    elif tokens[0] == "*":
        return mkMultiplyNode(parse(tokens, i + 1), parse(tokens, i + 1))
    elif tokens[0] == "//":
        return mkDivideNode(parse(tokens, i + 1), parse(tokens, i + 1))
    elif (tokens.pop(0).isdigit()):
        return mkLiteralNode(int(tokens.pop(0)))
    else:
        return mkVariableNode(tokens.pop(0))

def infix(node):
    """infix: Node -> String | TypeError
    Perform an inorder traversal of the node and return a string that
    represents the infix expression."""
    if isinstance(node, MultiplyNode):
        return "(" + infix(node.left) + " * " + infix(node.right) + ")"
    elif isinstance(node, DivideNode):
        return "(" + infix(node.left) + " // " + infix(node.right) + ")"
    elif isinstance(node, AddNode):
        return "(" + infix(node.left) + " + " + infix(node.right) + ")"
    elif isinstance(node, SubtractNode):
        return "(" + infix(node.left) + " - " + infix(node.right) + ")"
    elif isinstance(node, LiteralNode):
        return str(node.val)
    else:
        return node.name

def evaluate(node, symTbl):
    """evaluate: Node * dict(key=String, value=int) -> int | TypeError
    Given the expression at the node, return the integer result of evaluating
    the node.
    Precondition: all variable names must exist in symTbl"""
    if isinstance(node, MultiplyNode):
        return evaluate(node.left, symTbl) * evaluate(node.right, symTbl)
    elif isinstance(node, DivideNode):
        return evaluate(node.left, symTbl) // evaluate(node.right, symTbl)
    elif isinstance(node, AddNode):
        return evaluate(node.left, symTbl) + evaluate(node.right, symTbl)
    elif isinstance(node, SubtractNode):
        return evaluate(node.left, symTbl) - evaluate(node.right, symTbl)
    elif isinstance(node, VariableNode):
        for var in symTbl:
            if var == node.name:
                return symTbl[var]
    else:
        return node.val

def main():
    """main: None -> None
    The main program prompts for the symbol table file, and a prefix
    expression.  It produces the infix expression, and the integer result of
    evaluating the expression"""

    print("Hello Herp, welcome to Derp v1.0 :)")

    inFile = input("Herp, enter symbol table file: ")

    # STUDENT: CONSTRUCT AND DISPLAY THE SYMBOL TABLE HERE
    fileOpen = open(inFile)
    symTbl = {}

    for line in fileOpen:
        lineStrip = line.split()
        symTbl[lineStrip[0]] = int(lineStrip[1])

    for var in sorted(symTbl):
        print("Name: " + var + " => " + str(symTbl[var]))

    print("Herp, enter prefix expressions, e.g.: + 10 20 (RETURN to quit)...")

    # input loop prompts for prefix expressions and produces infix version
    # along with its evaluation
    while True:
        prefixExp = input("derp> ")
        if prefixExp == "":
            break

        prefix = prefixExp.split()
        root = parse(prefix)
        print("Derping the infix expression: " + infix(root))

        print("Derping the evaluation: " + str(evaluate(root, symTbl)))

    print("Goodbye Herp :(")

if __name__ == "__main__":
    main()

When I opened up the program. It will show this output:

Hello Herp, welcome to Derp v1.0 :)
Herp, enter symbol table file: vars.txt
Name: x => 10
Name: y => 20
Name: z => 30
Herp, enter prefix expressions, e.g.: + 10 20 (RETURN to quit)...
derp> - 10 20
Derping the infix expression: 10
Derping the evaluation: None
derp> + 10 * x y
Then the error has started...

Vars.txt:

x 10
y 20
z 30

Sidenote: if you guys are curious what it is in derp_node.py, I am not going to post it here, however, I posted it on pastebin so this page don't look huge. http://pastebin.com/MXuc8Shc Any help would be great! Thank you. Hope I provided enough information, so you guys have an idea, what I am doing.

parse does not seem to have termination condition. For example when tokens[0] is +. — akonsu
– akonsu, Commented Nov 18, 2013 at 19:04
I mean parse calls itself recursively and there is no check in it that would make it stop doing that. For example, when tokens[0]=='+'. — akonsu
– akonsu, Commented Nov 18, 2013 at 19:07

user2040158 · Accepted Answer · 2013-11-18 19:09:52Z

1

You keep passing the same reference to tokens.

tokens[0] will ALWAYS be '+' if you don't increment which character you're referring to, meaning that the recursive calls to parse() will continue forever.

Also, why do you have 4 if/elif branches that all check/call the exact same thing?

Also, the .pop() method actually changes the underlying list, so your if tokens.pop().isdigit() is actually removing the last element in tokens. This might be want you want to do in the first if as well.

answered Nov 18, 2013 at 19:09

user2040158

Sign up to request clarification or add additional context in comments.

1 Comment

user2985771 Over a year ago

Hello, my fault. I fixed it about the ifs and elifs

PaulMcG · Accepted Answer · 2013-11-18 19:08:52Z

0

You still have some calls to pop, and calling pop in your conditional is especially bad, since you mutate the list when you are not even sure if the condition applies or not:

elif (tokens.pop(0).isdigit()):
    return mkLiteralNode(int(tokens.pop(0)))

should be:

elif (tokens[0].isdigit()):
    return mkLiteralNode(int(tokens.pop(0)))

answered Nov 18, 2013 at 19:08

PaulMcG

64.1k16 gold badges98 silver badges135 bronze badges

Comments

jwodder · Accepted Answer · 2013-11-18 19:10:31Z

0

Let's take a look at what happens when you call parse(tokens, i) and tokens[0] == '+'. The body of parse will try to execute:

return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))

Executing this statement requires evaluating parse(tokens, i+1), and as tokens[0] is still '+' within the recursive call, you'll get another call to parse, and another, and this will never end. I think what you want to do is test tokens[i] == '+', not tokens[0], or maybe change parse(tokens, i+1) to parse(tokens[1:], i+1) (Why do you even have i when you're not using it?)

answered Nov 18, 2013 at 19:10

jwodder

58.1k12 gold badges116 silver badges134 bronze badges

1 Comment

user2985771 Over a year ago

I fixed it. I apologize. That works. When I changed everything from [0] to [i]. I got another error: ` File "derpAgain.py", line 27, in parse return mkLiteralNode(int(tokens.pop(0))) ValueError: invalid literal for int() with base 10: '+'`

user2703636 · Accepted Answer · 2013-11-18 19:13:24Z

0

If you get to a token '+' it starts an infinite loop:

if tokens[0] == "+":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif tokens[0] == "+":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif tokens[0] == "+":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif tokens[0] == "+":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif (tokens.pop(0).isdigit()):
    return mkLiteralNode(int(tokens.pop(0)))
else:
    return mkVariableNode(tokens.pop(0))

you only check the '+' token and only pop if token is not '+'. I hope that helps

I would use:

aux = tokens.pop(0)
if aux == "+":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif aux == "-":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif aux == "*":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif aux == "/":
    return mkAddNode(parse(tokens, i + 1), parse(tokens, i + 1))
elif (aux.isdigit()):
    return mkLiteralNode(int(aux))
else:
    return mkVariableNode(aux)

answered Nov 18, 2013 at 19:13

user2703636

2 Comments

user2985771 Over a year ago

I cannot use the tokens.pop(0). I have to use the recursive instead. I know the pop(0) works fine. Right now, I am having trouble with the recursive.

user2703636 Over a year ago

you can use then: aux = tokens[i] and leave the rest just the same

Collectives™ on Stack Overflow

Maximum Recursion exceeded

4 Answers 4

1 Comment

Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related