recursively computing expression python

Question

I am making an expression parser. I start with the string:

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

and will eventually reach

s = 8

Currently, when I test my code, I reach the print statement and I get

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

However if I wanted to do this recursively and continue the function, I get this error:

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

I'm not sure why I am getting this error. Could someone be an extra pair of eyes and point out why please? Thank you!

code:

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)

update

Right now my code gets stuck at the 2nd iteration. The first iteration results in

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

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

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

The second iteration is (using the new expression '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]

I think this is due to the operators inside operators or having 2 integers insider operators.

Please see the last edit to my answer, which simplifies a bit the code. — Hyperboreus
– Hyperboreus, Commented Nov 29, 2013 at 16:58
@Hyperboreus your answer has helped tremendously! thank you so much!! — Liondancer
– Liondancer, Commented Nov 30, 2013 at 0:55

Hyperboreus · Accepted Answer · 2013-11-29 16:55:21Z

Just another approach: If each of your functions has a fixed number of arguments, you can do away with all the parentheses and commata and use a stack to process it. No need for recursion, searching for commata and parentheses, etc:

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

Even if you have var-adic functions, those can be transcribed into n-adic ones. E.g. add(1,2,3,4) can be written using dyadic add as add add add 1 2 3 4.

I will expand a bit this example. At some point all the if-statements will just make you code illegible. But you can define a class for operatores, defining its number of arguments and its result:

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

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

Now you can make your evaluate function a bit neater. Here a working example for calculating fibonacci numbers:

#! /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) ) )

Filip Malczak · Accepted Answer · 2013-11-29 15:20:06Z

3

I assume that you know about "eval" function, and you're writing it for fun, or to learn by-hand creation of parsers.

local variable 'value' referenced before assignment

means that you try using 'value' before it was declared. I know, you declared it in if...elseif..., but apparently none of those conditions worked, so no assignment to 'value' was performed. In the end, there is no 'value' in local namespace! You should check 'thisop' value, to find out what it contains, you probably missed some parenthesis stripping or smth like that.

Good luck.

answered Nov 29, 2013 at 15:20

Filip Malczak

3,2221 gold badge26 silver badges45 bronze badges

1 Comment

Tim Pierce Over a year ago

Please mark the answer as "accepted" so @FilipMalczak gets the reputation credit for it :-)

usethedeathstar · Accepted Answer · 2013-11-29 15:20:55Z

0

Your value is undefined, You say if elif elif elif , but you have no final else, (and in that case you will get that error since you do not say what value is in that case)

answered Nov 29, 2013 at 15:20

usethedeathstar

2,3191 gold badge21 silver badges31 bronze badges

Collectives™ on Stack Overflow

recursively computing expression python

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related