Solve very large expression in python

Question

I'm working a problem in Project Euler that asks to find the value of a continuous fraction representing e (the mathematical constant) up to 100 terms.

I came up with a long expression which I'm almost positive is correct but Python can't evaluate it. I keep getting a MemoryError.

To put it in perspective, it's a fraction with 50 fraction bars in it.

Here's the expression:

2+(1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+1/(1+1/(1+1/(8+1/(1+1/(1+1/(10+1/(1+1/(1+1/(12+1/(1+1/(1+1/(14+1/(1+1/(1+1/(16+1/(1+1/(1+1/(18+1/(1+1/(1+1/(20+1/(1+1/(1+1/(22+1/(1+1/(1+1/(24+1/(1+1/(1+1/(26+1/(1+1/(1+1/(28+1/(1+1/(1+1/(30+1/(1+1/(1+1/(32+1/(1+1/(1+1/(34+1/(1+1/(1+1/(36+1/(1+1/(1+1/(38+1/(1+1/(1+1/(40+1/(1+1/(1+1/(42+1/(1+1/(1+1/(44+1/(1+1/(1+1/(46+1/(1+1/(1+1/(48+1/(1+1/(1+1/(50+1/(1+1/(1+1/(52+1/(1+1/(1+1/(54+1/(1+1/(1+1/(56+1/(1+1/(1+1/(58+1/(1+1/(1+1/(60+1/(1+1/(1+1/(62+1/(1+1/(1+1/(64+1/(1+1/(1+1/(66+1/(1+1))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

The answer should be very close to e (2.71828)

Congratulations on creating a stack overflow! You'll just need to calculate the fraction piecemeal, from the inside out, in 2 or more steps. On the plus side, all your parens are matched, so it should evaluate just fine. — MattDMo, Feb 17 '15 at 05:16
yeah i built that expression by appending to a string and using eval. Had to use str.count() to make sure parens matched :) thanks for the help — coustyx, Feb 17 '15 at 05:18
https://trinket.io (python in browser) [can evaluate it](https://trinket.io/python/b3a623dcf6). — jfs, Feb 17 '15 at 05:40
If you were solving this problem to learn Python, it's worth mentioning that using eval is considered poor form anyway. You could have added your values to a list and then used a loop to do the evaluation directly in your code (a bit like Jedi's answer but without `eval` or any of the string manipulation). — Arthur Tacca, Jun 28 '17 at 06:31
That's true @ArthurTacca. Yeah, `eval` is definitely not ideal, but it is sometimes good to know what you can do with it, and how you can add some precautions (like character-whitelisting using regular expressions) — Jedi, Jul 05 '17 at 19:51

Jedi · Answer 1 · 2017-06-28T13:10:13.610

Here's a quick way to evaluate the string inside out:

def evaluate_nested_fraction(expr):

  # Allow only "safe" characters in your `eval` [digits and +-*/()]
  expr= re.sub('[^\d\+\-\*\/\)\(]+','', expr)

  # Convert into a list of expressions starting with the innermost 1+1
  # Do this by removing ')' assuming balance, splitting by '(' and reversing order
  expr = expr.replace(')','').split('(')[::-1]

  # Now evaluate and append
  value = ''
  for i in xrange(0, len(expr)):
    value = str(float(eval(expr[i] + value)))
  return value


# Let's run this on your fraction
x = '2+(1/(1+1/(2+1/(1+1/(1+1/(4+1/(1+1/(1+1/(6+1/(1+1/(1+1/(8+1/(1+1/(1+1/(10+1/(1+1/(1+1/(12+1/(1+1/(1+1/(14+1/(1+1/(1+1/(16+1/(1+1/(1+1/(18+1/(1+1/(1+1/(20+1/(1+1/(1+1/(22+1/(1+1/(1+1/(24+1/(1+1/(1+1/(26+1/(1+1/(1+1/(28+1/(1+1/(1+1/(30+1/(1+1/(1+1/(32+1/(1+1/(1+1/(34+1/(1+1/(1+1/(36+1/(1+1/(1+1/(38+1/(1+1/(1+1/(40+1/(1+1/(1+1/(42+1/(1+1/(1+1/(44+1/(1+1/(1+1/(46+1/(1+1/(1+1/(48+1/(1+1/(1+1/(50+1/(1+1/(1+1/(52+1/(1+1/(1+1/(54+1/(1+1/(1+1/(56+1/(1+1/(1+1/(58+1/(1+1/(1+1/(60+1/(1+1/(1+1/(62+1/(1+1/(1+1/(64+1/(1+1/(1+1/(66+1/(1+1))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))'

print evaluate_nested_fraction(x)

Returns 2.71828182846 on CPython. You can run it here.

Any usage of eval comes with the usual warnings.

Solve very large expression in python

1 Answers1