RPN（postfix）表达式的优化计算方法

Question

在处理一个小的project时，我偶然发现了一个问题：我无法在Python中找到解析数学表达式的有效方法。在

简要介绍一下上下文：程序依赖于在RPN中迭代大量（约1000万）代数表达式，并对每个表达式进行求值，以确定其是否符合期望的结果。不出所料，该方法最慢的部分是对每个表达式求值，因此我非常希望简化它。在

以下问题是我迄今为止的研究结果摘要，并邀请您对现有方法提出改进建议。

我测试了以下方法：

• 我自己的方法，这是RPN解析的经典堆栈实现
• 一个稍微更一般化的方法，发现here
• 使用列表切片来获取堆栈项而不是弹出的方法发现here

我还测试了evil eval，以便为Python的内置解析器获取一个参考点，同时也只是“在线”执行计算。在

通过尝试解析以下每个表达式100万次并记录每个函数所用的时间来完成测试：

• 2 2 +
• 2 2 2 + +
• 2 2 2 2 + + +

Eval被用来计算等价的中缀表达式，相同的中缀表达式被直接传递给python进行测试的最后一步。完整的代码在帖子的底部。在

调查结果如下： Table, times in seconds 虽然有一些细微的区别，但是这些方法大体上是相似的，因为它们都是堆栈的列表实现，所以我想延迟来自于列表的变化。在

相比之下，邪恶的评估要差得多。内联计算显然是闪电般的快速。在

我知道除了计算之外，解析还执行大量的识别操作，但我希望有一种方法（明显地）比我在这里看到的方法更有效。也许有些Python的魔力我不知道。。。 我欢迎来自Python专家的任何和所有的指针，否则这篇文章可以作为RPN解析器的一个总结，供以后的几代人参考。。。在

import itertools as it
import random
import time
import operator
operators = ["+", "-", "/", "*"]
count = 0


def RPN_Classic_Stack(expression): #Mine
    explist = expression.split(" ")
    explist.pop(-1)
    stack = []

    for char in explist:
        if not char in operators:
            stack.append(int(char))
        else:
            if char == "+":
                num1 = stack.pop()
                num2 = stack.pop()

                result = num1 + num2
                stack.append(result)

            if char == "-":
                num1 = stack.pop()
                num2 = stack.pop()
                result = -num1 + num2

                stack.append(result)

            if char == "*":
                num1 = stack.pop()
                num2 = stack.pop()

                result = num1 * num2
                stack.append(result)

            if char == "/":
                divisor = stack.pop()
                divident = stack.pop()

                try:
                    result = divident / divisor
                except:
                    return [-1]
                stack.append(result)

    return stack.pop()


def safe_divide(darg1, darg2):
    try:
        return darg1/darg2
    except ZeroDivisionError:
        return -1

def RPN_Generalised_Operators(expression): #https://stackoverflow.com/a/37770871/5482177
    function_twoargs = {
        '*': operator.mul,
        '/': safe_divide,
        '+': operator.add,
        '-': operator.sub,
        }
    expression = expression.split(" ")
    stack = []
    for val in expression:
        result = None
        if val in function_twoargs:
            arg2 = stack.pop()
            arg1 = stack.pop()
            result = function_twoargs[val](arg1, arg2)
        else:
            result = float(val)
        stack.append(result)
    return stack.pop()

def RPN_List_Slicing(expression): #https://stackoverflow.com/a/3866502/5482177
    operators = {
    '+':  operator.add, '-':  operator.sub,
    '*':  operator.mul, '/':  operator.truediv, '%':  operator.mod,
    '**': operator.pow, '//': operator.floordiv,
    }
    stack = []
    for val in expression.split():
        if val in operators:
            f = operators[val]
            stack[-2:] = [f(*stack[-2:])]
        else:
            stack.append(int(val))
    return stack.pop()

def not_RPN_Evil_Eval(expression):
    return eval(expression)

expressions = ["2 2 +", "2 2 2 + +", "2 2 2 2 + + +"]
results = {}
parsers = [RPN_Classic_Stack, RPN_Generalised_Operators, RPN_List_Slicing]
for expression in expressions:
    for parser in parsers:
        start = time.time()
        for i in range(0,1000000):
            parser(expression)
        end = time.time()
        results[parser.__name__] = results.get(parser.__name__, {})
        results[parser.__name__][expression] = end-start
        print(results)

non_RPN_expressions = ["2 + 2", "2 + 2 + 2", "2 + 2 + 2 + 2"]
for expression in non_RPN_expressions:
    start = time.time()
    for i in range(0,1000000):
        not_RPN_Evil_Eval(expression)
    end = time.time()
    print(expression, end-start)


############ Inline calculations ###################
start = time.time()
for i in range(0,1000000):
    2 + 2
end = time.time()
print(expression, end-start)

start = time.time()
for i in range(0,1000000):
    2 + 2 + 2
end = time.time()
print(expression, end-start)

start = time.time()
for i in range(0,1000000):
    2 + 2 + 2 + 2
end = time.time()
print(expression, end-start)
##############################