重构递归计算器到迭代的计算器

Question

我有一个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已经重构我的应用程序的其它部分递归迭代成。

虽然这在将字段定义链接到用户输入时可行，但我在包装头问题时遇到了更多麻烦，一旦它归结为只有参数，然后将结果传递到下一个堆栈级别，上。

Answer 1

我不确定这会帮助您将头部缠绕在解析堆栈的递归中。如果您只是想评估表达式，那么您可以使用解析操作来处理所有事情，并在解析时进行评估。请参阅我提供的源代码中的嵌入式注释：

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()