我想知道 Python3 中的解析器模块用于评估
表达式的算法或时间复杂度。
这是我的代码:
import random
import parser
equation_ = '(x**3 + 5*(x**2) - 3*x + 3) + (4*(x**5) - 2*(x**2) + 1)'
code = parser.expr(equation_).compile()
test_cases = [random.randrange(-100, 100) for _ in range(10)]
for x in test_cases:
print(eval(code))
现在,我想知道使用了哪种算法或者该方法的时间复杂度是多少:parser.expr()
和 eval()
。
我尝试阅读 documentation但无法弄清楚,source code 的情况也是如此。 :parser.c和parser.h
最佳答案
我无法说出Python的parser
库中的具体算法,但一般来说解析是O(n)。它使用正则表达式从文本中提取标记流,然后将其与语法模式进行匹配,这可以通过表查找来完成。处理语法中的嵌套结构可能涉及递归,但这都是通过对输入进行固定次数的扫描来完成的。我认为 Python 是一种上下文无关语法,因此它应该可以通过一次解析来解析。
一旦解析了表达式,对其求值就具有与在普通源代码中编写该表达式相同的复杂性 - eval()
只是对 Python 的该部分的调用口译员。如果代码中没有循环,则时间复杂度为 O(n)。
关于python - 在Python3中使用解析器模块计算表达式的时间复杂度(theta)是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58922998/