AtCoder Beginner Contest 033 C - 数式の書き換え

Question

こちらの問題に Python3 で以下のようなコードを書いて提出したところ、いくつかのテストケースで RE が返ってきました。テストケースがこうかいされていないため、自分で原因が思いつけないです。どなたか分かる方いましたら教えていただけますでしょうか。

C - 数式の書き換え

提出コード

ans = 0
for si in input().split("+"):
    if eval(si) != 0:
        ans += 1
print(ans)

プログラムの挙動について補足

• 入力文字列を + で区切ります
• 区切った各文字列に対し、その値を実際に計算し、 0 の場合は ans の値を 1 増やします

Answer 1

完全に内部の実装の問題になってしまうのですが、Pythonのevalは非常識なほど長い式（非常識なほどたくさん演算子が連なっていると……というべきか）を評価できるようには実装されていないようです。それに引っかかったのでしょう。

>>> eval("1*" * 10 + "1")
1
>>> eval("1*" * 100 + "1")
1
>>> eval("1*" * 1000 + "1")
1
>>> eval("1*" * 10000 + "1")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded during compilation

PythonレイヤでRecursionErrorが起きているみたいなので、sys.setrecursionlimit(10**5)するとなぜか例外が出なくなります。ちなみにデフォルトは1000です。

>>> import sys
>>> sys.setrecursionlimit(10**5)
>>> eval("1*" * 10000 + "1")
1

構文解析のときに再帰する要素があるのでしょう。

sys.setrecursionlimitで乗り切るのは、あんまりおすすめしません（すごく大きくしていけば動くかもしれないけど、先にバルスになるかもしれません。そしてそもそも競プロとしてどうよという感もあり）。

Comments

[bighope]

eval が悪さをしていたのですね！丁寧にありがとうございます。納得できました。

Answer 2

1行目には、問題文の条件を満たす数式S(Sの長さは1以上100,000以下)が与えられる。

9999…(100,000文字まで繰り返し)
を入力するとeval(si)でRecursionError: maximum recursion depth exceeded during compilationになりますね。

Comments

[bighope]

ありがとうございます！evalで長い数式の場合に耐えられなくなってしまうようですね。