Replace keys in values with key->values from same dictionary

Question

I have a dictionary whose values may contain keys that are already in the dictionary. What we are actually talking about are parameters. Sometimes a parameter is defined by a number plus another parameter, etc.

It looks something like this:

paramDict = {'ad': '2*dmcg/factor*(xw/factor)',
'dmcg': 2.05e-07,
'dxwn_3vna': 10.0,
'factor': 1,
'xw': '0+dxwn_3vna'}

If there is another parameter in the value it is of type string, otherwise it is an int or a float. After the replacing I want the value to be a float.

The code I wrote to solve this problem is this:

    for _ in range(10):
        for key, value in paramDict.items():
            if type(value) is str:
                matchList = re.findall('[a-z]\w*', value)
                matchList = [match for match in matchList if match != 'e']
                for match in matchList:
                    param = paramDict[match]
                    paramDict[key] = value.replace(match, str(param))
                try:
                    paramDict[key] = eval(paramDict[key])
                except:
                    pass

It works as far as I can tell, but it just doesn't feel right to just repeat the whole process a finite number of times and hope that all the strings have been replaced. Is there a safer way?

Answer 1

It took me some time (the question challenged me), but after playing with some (stupidly :) ) over-complicated approaches I came up with this pretty straightforward solution. It does not even require high-end libraries

I do not think it needs explanation, but if you have questions - I will gladly answer them

EDITED:

It occurred to me that the original version did not handle the case when some of the expressions cannot be evaluated. Well, that may be easily rectified.

def eval_dict(paramDict):
    evaluated_post_cnt = 0 # Total number of converted from previous loop
    result = {}
    while True:
        for var_name, value in paramDict.iteritems():
            if not var_name in result:
                try:
                    exec('{} = {}'.format(var_name, value))
                    result[var_name] = locals()[var_name]
                except NameError:
                    pass
        all_evaluated_num = len(result) 
        if all_evaluated_num == len(paramDict):
            # All values converted
            return result
        if evaluated_post_cnt == all_evaluated_num:
            # No new keys converted in a loop - dead end
            raise Exception('Cannot convert some keys')
        evaluated_post_cnt = all_evaluated_num

OK, here's the "magic":

exec - (not recommended by purists) attempts to execute strings as a Python command lines, so if the sting is, e.g

'xw =0+dxwn_3vna'

the execution will fail with NameError exception if dxwn_3vna has not been evaluated yet - or it will assign value 10.0 to variable with the name xw - as regular assignment statement. Assigned variable is added to local variable set - which may be accessed with function locals() - returns dictionary. So, if the code succeeds in evaluating values - they are replaced in your dictionary.

That simplifies the code, because I do not have to replace variable names within strings with values - if all variables in this string

2*dmcg/factor*(xw/factor)

are already defined, then this string may be executed

'ad = 2*dmcg/factor*(xw/factor)'

Is it clear now?

Answer 2

Well what you want there is evaluating expressions while keeping track of dependencies, so you should definitely not implement it via regular expressions and hoping that running it ten times is enough.

The best way in Python would probably be using the ast module to parse and figure out the referenced variables, then calculate dependencies and evaluate the parsed expressions via compile and eval while passing in the referenced variables in the local parameter.

That way you make sure that the expressions are actually valid, you can use Python expressions and you can (and should) also detect cycles in the specification.

Below is a sketch how to do that, not saying that is the best code, please edit or comment with improvements, I couldn't find a good example while searching.

import ast, _ast

params = {
    'ad': '2*dmcg/factor*(xw/factor)',
    'dmcg': 2.05e-07,
    'dxwn_3vna': 10.0,
    'factor': 1,
    'xw': '0+dxwn_3vna',
    'foo': 'bar',
    'bar': 'foo'
}

parsed = {}

for key, value in params.iteritems():
    parsed[key] = value

    if type(value) in (str, unicode):
        parsed[key] = ast.parse(value, mode="eval")

evaluated = {key: value for key, value in parsed.iteritems()}

So at this point the evaluated dictionary is mostly a copy of the params, except that expressions have been parsed.

def referenced(code):
    return [node.id for node in ast.walk(code) if "id" in node._fields]

referenced returns a list with the names of referenced variables in the expression.

evaluating = []

def resolve(key, value):
    if key in evaluating:
        raise Exception("Loop while evaluating {}".format(key))

    if type(value) is not _ast.Expression:
        evaluated[key] = value
        return value

    evaluating.append(key)

    locals = {name: resolve(name, evaluated[name]) for name in referenced(value)}

    result = eval(compile(value, "<unknown>", "eval"), globals(), locals)

    evaluated[key] = result

    evaluating.pop()

    return result

resolve evaluates the expression recursively but also keeps track of the stack (in evaluating), so it can detect cycles by looking up the current variable. It also assigns the results immediately, so in further invocations it will return early (the not _ast.Expression case).

for key, value in parsed.iteritems():
    try:
        resolve(key, value)
    except Exception as exception:
        print ("Error while evaluating {}: {}".format(key, exception))

print(evaluated)

Lastly, iterate over all entries and try to evaluate them.

Answer 3

A slightly more robust technique than volcano's, but still less-so than ferada's, is to capture the evaluation in a fake "scope" and avoid messing with strings:

paramDict[var_name] = eval(value, {}, paramDict)

This keeps locals clean.

However, you don't want to start with everything available to eval since you'll never get a NameError that way. Instead, build a dictionary as you go.

What might even be better is abusing eval's locals argument with a lazy cached evaluation strategy:

# from UserDict import UserDict on Python 2
from collections import UserDict

class StringScope(UserDict):
    def __getitem__(self, name):
        expr = self.data[name]

        if isinstance(expr, str):
            expr = self.data[name] = eval(expr, {}, self)

        return expr

scope = StringScope(paramDict)

That's it: scope will now lazily evaluate its values as they are requested. If you want eager evaluation, just do

scope = dict(StringScope(paramDict))

instead. This will automatically do walking of the dependency chain, too, so is technically more efficient algorithmically.