将递归计算器重构为迭代计算器
Refactor recursive calculator into an iterative one
我有一个 Django 应用程序，它是一个计算器。用户在一个屏幕上配置任意深度的计算（想想 Excel 公式），然后在另一个屏幕上输入（单元格）数据。
将字段链接到它们的值后，我得到了一个形式为
的公式
SUM(1,2,4)
可以任意深，例如
SUM(1,SUM(5,DIFFERENCE(6,DIVISION(8,10),7),4),2)
令我头疼的公式之一是用户在我们系统中输入的比较复杂的公式之一：
ROUND(MULTIPLICATION(DIVISION(ROUND(SUM(MULTIPLICATION(50.00000,50.00000),MULTIPLICATION(50.00000,50.00000,2),MULTIPLICATION(50.00000,50.00000)),-2),300),DIFFERENCE(DIFFERENCE(41,7),0.3)),0)
我正在使用 pyparsing 来解析公式并提取值和嵌套公式，并递归地执行计算。问题是由于解析每个嵌套计算，我 运行 进入了 pyparsing 的递归限制。
我的递归代码：
class Calculator:
def __init__(self, formula=None):
self.formula = formula
def do_calculation(self):
# parse the formula we receive, which returns arguments in groups of numbers and nested calculations
# e.g. SUM(MULTIPLICATION(12,11),1,5)
parsed_formula = FormulaParser(self.formula).get_parsed_formula()
#calculation name is the outermost level calculation
calc_name = parsed_formula['calculation_name']
#don't stomp on built in round
if 'ROUND' in "".join(calc_name):
calc_name = ["ROUND_CALCULATION"]
#don't stomp on if
if 'IF' == "".join(calc_name):
calc_name = ['IF_STATEMENT']
#grab the name of the calculation, will match a function name below
ex = getattr(self, string.lower("".join(calc_name)))
calc_arguments = []
#formulas need to be recursively executed
formulas = parsed_formula.args.formulas.asList() if len(parsed_formula.args.formulas) else []
#numbers are just added to the arguments
dnumbers = parsed_formula.args.dnumbers.asList() if len(parsed_formula.args.dnumbers) else []
for arg in parsed_formula.args.asList():
if arg in dnumbers:
calc_arguments.append(''.join(arg))
elif arg in formulas:
new_calc = Calculator(''.join(self.flatten(arg[:])))
calc_arguments.append(new_calc.do_calculation())
#execute the calculation with the number arguments
for idx, arg in enumerate(calc_arguments):
if isinstance(arg, dict) and arg['rounding']:
calc_arguments[idx] = arg['result']
result = ex(*calc_arguments)
#for rounding, output is special to tell the api to not format to default 5 decimal places
if 'ROUND' in "".join(calc_name):
return dict(result=result, rounding=True)
return result
# function called on nested calculations that may have other nested calculations to flatten to a single level list
@staticmethod
def flatten(expr):
for i, x in enumerate(expr):
while isinstance(expr[i], list):
expr[i:i + 1] = expr[i]
return expr
公式解析器：
class FormulaParser():
def __init__(self, formula=None):
self.formula = formula
# grammar
# end result
expr = Forward()
formula = Forward()
#calculation keywords
calc_keyword = lambda name: Keyword(name)
calculations = [calc_keyword(calc) for calc in CALCULATION_TYPES]
calc_name = Group(reduce(lambda y, z: y | z, [x for x in calculations])).setResultsName('calculation_name')
#symbols
oparen, cparen, comma, dot, minus = map(Literal, '(),.-')
dnumber = Combine(Optional(minus) + Word(nums) + Optional(dot + Word(nums)))
#possible formulas
expr = Group(formula).setResultsName('formulas', listAllMatches=True) | Group(dnumber).setResultsName(
'dnumbers', listAllMatches=True)
exprs = expr + ZeroOrMore(comma + expr)
#entire formula
formula << Combine(calc_name + Group(oparen + exprs + cparen).setResultsName('args'))
self.parsed_formula = formula
def get_parsed_formula(self):
if self.formula:
return self.parsed_formula.parseString(self.formula)
return None
我已经使用 this SO answer 中的堆栈方法将应用程序的其他递归部分重构为迭代。
虽然这在将字段定义链接到用户输入方面是可行的，但我在思考如何执行计算时遇到了更多麻烦，一旦它归结为只有参数，然后将结果传递到下一个堆栈级别，并且等等。
我不确定这是否能帮助您集中精力处理已解析堆栈的递归问题。如果您只想评估表达式，那么您可以使用解析操作来处理所有事情，并在解析时进行评估。请参阅我的模组中对您提供的源代码的嵌入式注释：
sample = """ROUND(MULTIPLICATION(DIVISION(ROUND(SUM(MULTIPLICATION(50.00000,50.00000),MULTIPLICATION(50.00000,50.00000,2),MULTIPLICATION(50.00000,50.00000)),-2),300),DIFFERENCE(DIFFERENCE(41,7),0.3)),0)"""
from pyparsing import *
CALCULATION_TYPES = "ROUND MULTIPLICATION DIVISION SUM DIFFERENCE".split()
functionMap = {
"ROUND" : lambda args: round(args[0]),
"MULTIPLICATION" : lambda args: args[0]*args[1],
"DIVISION" : lambda args: args[0]/args[1],
"SUM" : lambda args: args[0]+args[1],
"DIFFERENCE" : lambda args: args[0]-args[1],
}
class FormulaParser():
def __init__(self, formula=None):
self.formula = formula
# grammar
# end result
expr = Forward()
formula = Forward()
#calculation keywords
calc_keyword = lambda name: Keyword(name)
calculations = [calc_keyword(calc) for calc in CALCULATION_TYPES]
calc_name = Group(reduce(lambda y, z: y | z, [x for x in calculations])).setResultsName('calculation_name')
# a simpler way to create a MatchFirst of all your calculations
# also, save the results names for when you assemble small elements into larger ones
calc_name = MatchFirst(calculations)
#symbols
oparen, cparen, comma, dot, minus = map(Literal, '(),.-')
#dnumber = Combine(Optional(minus) + Word(nums) + Optional(dot + Word(nums)))
# IMPORTANT - convert numbers to floats at parse time with this parse action
dnumber = Regex(r'-?\d+(\.\d+)?').setParseAction(lambda toks: float(toks[0]))
#possible formulas
#expr = Group(formula).setResultsName('formulas', listAllMatches=True) |
# Group(dnumber).setResultsName('dnumbers', listAllMatches=True)
#exprs = expr + ZeroOrMore(comma + expr)
#entire formula
#formula << Combine(calc_name + Group(oparen + exprs + cparen).setResultsName('args'))
#self.parsed_formula = formula
# define what is allowed for a function arg
arg_expr = dnumber | formula
def eval_formula(tokens):
fn = functionMap[tokens.calculation_name]
return fn(tokens.args)
# define overall formula, and add results names here
formula <<= (calc_name("calculation_name") + oparen
+ Optional(delimitedList(arg_expr))('args')
+ cparen).setParseAction(eval_formula)
self.parsed_formula = formula
def get_parsed_formula(self):
if self.formula:
return self.parsed_formula.parseString(self.formula)
return None
fp = FormulaParser(sample)
print fp.get_parsed_formula()
我有一个 Django 应用程序，它是一个计算器。用户在一个屏幕上配置任意深度的计算（想想 Excel 公式），然后在另一个屏幕上输入（单元格）数据。
将字段链接到它们的值后，我得到了一个形式为
的公式SUM(1,2,4)
可以任意深，例如
SUM(1,SUM(5,DIFFERENCE(6,DIVISION(8,10),7),4),2)
令我头疼的公式之一是用户在我们系统中输入的比较复杂的公式之一：
ROUND(MULTIPLICATION(DIVISION(ROUND(SUM(MULTIPLICATION(50.00000,50.00000),MULTIPLICATION(50.00000,50.00000,2),MULTIPLICATION(50.00000,50.00000)),-2),300),DIFFERENCE(DIFFERENCE(41,7),0.3)),0)
我正在使用 pyparsing 来解析公式并提取值和嵌套公式，并递归地执行计算。问题是由于解析每个嵌套计算，我 运行 进入了 pyparsing 的递归限制。
我的递归代码：
class Calculator:
def __init__(self, formula=None):
self.formula = formula
def do_calculation(self):
# parse the formula we receive, which returns arguments in groups of numbers and nested calculations
# e.g. SUM(MULTIPLICATION(12,11),1,5)
parsed_formula = FormulaParser(self.formula).get_parsed_formula()
#calculation name is the outermost level calculation
calc_name = parsed_formula['calculation_name']
#don't stomp on built in round
if 'ROUND' in "".join(calc_name):
calc_name = ["ROUND_CALCULATION"]
#don't stomp on if
if 'IF' == "".join(calc_name):
calc_name = ['IF_STATEMENT']
#grab the name of the calculation, will match a function name below
ex = getattr(self, string.lower("".join(calc_name)))
calc_arguments = []
#formulas need to be recursively executed
formulas = parsed_formula.args.formulas.asList() if len(parsed_formula.args.formulas) else []
#numbers are just added to the arguments
dnumbers = parsed_formula.args.dnumbers.asList() if len(parsed_formula.args.dnumbers) else []
for arg in parsed_formula.args.asList():
if arg in dnumbers:
calc_arguments.append(''.join(arg))
elif arg in formulas:
new_calc = Calculator(''.join(self.flatten(arg[:])))
calc_arguments.append(new_calc.do_calculation())
#execute the calculation with the number arguments
for idx, arg in enumerate(calc_arguments):
if isinstance(arg, dict) and arg['rounding']:
calc_arguments[idx] = arg['result']
result = ex(*calc_arguments)
#for rounding, output is special to tell the api to not format to default 5 decimal places
if 'ROUND' in "".join(calc_name):
return dict(result=result, rounding=True)
return result
# function called on nested calculations that may have other nested calculations to flatten to a single level list
@staticmethod
def flatten(expr):
for i, x in enumerate(expr):
while isinstance(expr[i], list):
expr[i:i + 1] = expr[i]
return expr
公式解析器：
class FormulaParser():
def __init__(self, formula=None):
self.formula = formula
# grammar
# end result
expr = Forward()
formula = Forward()
#calculation keywords
calc_keyword = lambda name: Keyword(name)
calculations = [calc_keyword(calc) for calc in CALCULATION_TYPES]
calc_name = Group(reduce(lambda y, z: y | z, [x for x in calculations])).setResultsName('calculation_name')
#symbols
oparen, cparen, comma, dot, minus = map(Literal, '(),.-')
dnumber = Combine(Optional(minus) + Word(nums) + Optional(dot + Word(nums)))
#possible formulas
expr = Group(formula).setResultsName('formulas', listAllMatches=True) | Group(dnumber).setResultsName(
'dnumbers', listAllMatches=True)
exprs = expr + ZeroOrMore(comma + expr)
#entire formula
formula << Combine(calc_name + Group(oparen + exprs + cparen).setResultsName('args'))
self.parsed_formula = formula
def get_parsed_formula(self):
if self.formula:
return self.parsed_formula.parseString(self.formula)
return None
我已经使用 this SO answer 中的堆栈方法将应用程序的其他递归部分重构为迭代。
虽然这在将字段定义链接到用户输入方面是可行的，但我在思考如何执行计算时遇到了更多麻烦，一旦它归结为只有参数，然后将结果传递到下一个堆栈级别，并且等等。
我不确定这是否能帮助您集中精力处理已解析堆栈的递归问题。如果您只想评估表达式，那么您可以使用解析操作来处理所有事情，并在解析时进行评估。请参阅我的模组中对您提供的源代码的嵌入式注释：
sample = """ROUND(MULTIPLICATION(DIVISION(ROUND(SUM(MULTIPLICATION(50.00000,50.00000),MULTIPLICATION(50.00000,50.00000,2),MULTIPLICATION(50.00000,50.00000)),-2),300),DIFFERENCE(DIFFERENCE(41,7),0.3)),0)"""
from pyparsing import *
CALCULATION_TYPES = "ROUND MULTIPLICATION DIVISION SUM DIFFERENCE".split()
functionMap = {
"ROUND" : lambda args: round(args[0]),
"MULTIPLICATION" : lambda args: args[0]*args[1],
"DIVISION" : lambda args: args[0]/args[1],
"SUM" : lambda args: args[0]+args[1],
"DIFFERENCE" : lambda args: args[0]-args[1],
}
class FormulaParser():
def __init__(self, formula=None):
self.formula = formula
# grammar
# end result
expr = Forward()
formula = Forward()
#calculation keywords
calc_keyword = lambda name: Keyword(name)
calculations = [calc_keyword(calc) for calc in CALCULATION_TYPES]
calc_name = Group(reduce(lambda y, z: y | z, [x for x in calculations])).setResultsName('calculation_name')
# a simpler way to create a MatchFirst of all your calculations
# also, save the results names for when you assemble small elements into larger ones
calc_name = MatchFirst(calculations)
#symbols
oparen, cparen, comma, dot, minus = map(Literal, '(),.-')
#dnumber = Combine(Optional(minus) + Word(nums) + Optional(dot + Word(nums)))
# IMPORTANT - convert numbers to floats at parse time with this parse action
dnumber = Regex(r'-?\d+(\.\d+)?').setParseAction(lambda toks: float(toks[0]))
#possible formulas
#expr = Group(formula).setResultsName('formulas', listAllMatches=True) |
# Group(dnumber).setResultsName('dnumbers', listAllMatches=True)
#exprs = expr + ZeroOrMore(comma + expr)
#entire formula
#formula << Combine(calc_name + Group(oparen + exprs + cparen).setResultsName('args'))
#self.parsed_formula = formula
# define what is allowed for a function arg
arg_expr = dnumber | formula
def eval_formula(tokens):
fn = functionMap[tokens.calculation_name]
return fn(tokens.args)
# define overall formula, and add results names here
formula <<= (calc_name("calculation_name") + oparen
+ Optional(delimitedList(arg_expr))('args')
+ cparen).setParseAction(eval_formula)
self.parsed_formula = formula
def get_parsed_formula(self):
if self.formula:
return self.parsed_formula.parseString(self.formula)
return None
fp = FormulaParser(sample)
print fp.get_parsed_formula()