python - 递归计算表达式python

Question

我正在制作一个表达式解析器。我从字符串开始:

s = 'abs(multiply(4,add(-4,2)))'

最终会到达

s = 8

目前，当我测试我的代码时，我到达打印语句并得到

'abc(multiply(4,-2))'

但是，如果我想递归地执行此操作并继续该函数，则会出现此错误:

Traceback (most recent call last):
  File "test.py", line 44, in <module>
    print eval_expr(s)
  File "test.py", line 41, in eval_expr
    return eval_expr(new_expr)  
  File "test.py", line 37, in eval_expr
    new_expr = str(rest + _2 + value + arg1[arg1.find(')') + 1:])
  UnboundLocalError: local variable 'value' referenced before assignment

我不确定为什么会收到此错误。有人能多出一双眼睛，请指出为什么吗？谢谢!

代码:

from operator import mul, sub, abs, add

s = 'abs(multiply(4,add(-4,2)))'

def eval_expr(expr):
    op,_1,arg1 = expr.rpartition('(')
    rest,_2,thisop = op.rpartition(',')
    args = arg1.rstrip(')').split(',')
    j = map(int, args)

    if thisop == 'add':
        value = str(add(j[0], j[1]))
    elif thisop == 'subtract':
        value = str(sub(j[0],j[1]))
    elif thisop == 'multiply':
        value = str(mul(j[0], j[1]))
    elif thisop == 'abs':
        value = str(abs(j[0]))

    new_expr = str(rest + _2 + value + arg1[arg1.find(')') + 1:])

    print "new expr: " + new_expr
    #if rest:
    #   return eval_expr(new_expr)  

print eval_expr(s)

更新

现在我的代码卡在了第 2 次迭代。第一次迭代结果为

op = 'abs(multiply(4,add'
_1 = '('
arg1 = '-4,2)))'

rest = 'abs(multiply(4'
_2 = ','
thisop = 'add'

args = ['4','-2']
j = [4,-2]    

第二次迭代是(使用新表达式 'abc(multiply(4,-2))'

op = 'abs(multiply'
_1 = '('
arg1 = '4,-2))'

#Now I dont get any values for rest and _2 but thisop, args, and j are:

thisop = 'abs(multiply'
args = ['4','-2']
j = [4,-2]

我认为这是由于运算符内部的运算符或具有 2 个整数内部运算符。

Answer 1

只是另一种方法:如果您的每个函数都有固定数量的参数，您可以取消所有括号和逗号，并使用堆栈来处理它。无需递归、搜索逗号和括号等:

def parse (s):
    #Just throwing away all parentheses and commata
    s = s.replace ('(', ' ').replace (')', ' ').replace (',', ' ')
    #Return reversed polish notation
    return s.split () [::-1]

def evaluate (ops):
    stack = []
    while ops:
        op = ops [0]
        ops = ops [1:]
        try:
            stack.append (int (op) )
            continue
        except: pass
        try:
            stack.append (float (op) )
            continue
        except: pass
        if op == 'add':
            arg1, arg2 = stack.pop (), stack.pop ()
            stack.append (arg1 + arg2)
            continue
        if op == 'multiply':
            arg1, arg2 = stack.pop (), stack.pop ()
            stack.append (arg1 * arg2)
            continue
        if op == 'abs':
            arg1 = stack.pop ()
            stack.append (abs (arg1) )
            continue
        raise Exception ('Unkown instruction "{}".'.format (op) )
    return stack [0]

ops = parse ('abs(multiply(4,add(-4,2)))')
print (evaluate (ops) )
ops = parse ('multiply add 1 2 add add 3 4 5')
print (evaluate (ops) )

即使您有 var-adic 函数，也可以将它们转换为 n-adic 函数。例如。 add(1,2,3,4) 可以使用二元 add 编写为 add add add 1 2 3 4。

---

我将扩展这个例子。在某些时候，所有 if 语句只会让您的代码难以辨认。但是您可以为运算符定义一个类，定义其参数数量及其结果:

class Operator:
    def __init__ (self, argc, f):
        self.argc = argc
        self.f = f

    def __call__ (self, *args):
        return self.f (*args)

现在您可以使您的evaluate 函数更简洁一些。这里有一个计算斐波那契数列的工作示例:

#! /usr/bin/python3

from random import randrange

class Operator:
    def __init__ (self, argc, f):
        self.argc = argc
        self.f = f

    def __call__ (self, *args):
        return self.f (*args)

def parse (s):
    s = s.replace ('(', ' ').replace (')', ' ').replace (',', ' ')
    return s.split () [::-1]

def evaluate (ops):
    stack = []
    while ops:
        op = ops [0]
        ops = ops [1:]
        try:
            stack.append (int (op) )
            continue
        except: pass
        try:
            stack.append (float (op) )
            continue
        except: pass
        try:
            operator = operators [op]
        except:
            raise Exception ('Unkown operator {}'.format (op) )
        args = [stack.pop () for _ in range (operator.argc) ]
        stack.append (operator (*args) )
    return stack [0]

operators = {
    'add': Operator (2, lambda a, b: a + b),
    'sub': Operator (2, lambda a, b: a - b),
    'mul': Operator (2, lambda a, b: a * b),
    'div': Operator (2, lambda a, b: a / b),
    'pow': Operator (2, lambda a, b: a ** b),
    'floor': Operator (1, lambda a: int (a) ),
    'abs': Operator (1, lambda a: abs (a) ),
    }

n = int (input ('Which fibonacci number do you want: ') )
fib = 'floor add div pow div add 1 pow 5 .5 2 {} pow 5 .5 .5'.format (n)
#or if you like parentheses: 'floor(add(div(pow(div(add(1,pow(5,.5)),2),{}),pow(5,.5)),.5))'
ops = parse (fib)
print ('F({}) = {}'.format (n, evaluate (ops) ) )