Вопрос реализации Python

Question

Эй. У меня есть проблема, которую я пытаюсь решить в Python, и я не могу придумать умную реализацию. Ввод представляет собой строку букв. Некоторые из них представляют переменные, другие представляют операторы, и я хочу перебрать большое количество значений для переменных (различные конфигурации).

Я думаю, что эквивалентным вопросом было бы то, что вы получите уравнение со многими переменными, хранящимися в виде строки, и вы хотите увидеть решение, когда подставляете x, y, z и т. Д. Для множества различных значений или удовлетворяете булевой формуле.

Я не могу придумать какую-либо умную структуру данных, которая бы реализовала это - просто «установка» формулы каждый раз, подстановка переменных, занимает больше времени, чем фактическая оценка.

Я знаю, что это немного абстрактно - но у кого-нибудь есть идеи или есть опыт работы с чем-то похожим?

Кто-то предложил мне реализовать оценщика. Это правда, но не в этом дело. Предполагается, что функция eval (string) уже реализована. Что такое эффективная структура данных, которая будет хранить значения и позволять менять их каждый раз чисто и эффективно? Конечно, не строка! Это должен быть изменяемый список. И если у него есть несколько экземпляров переменной x, он должен иметь возможность быстро оценить их все и изменить их значение до оценки и т. Д. И т. Д.

Answer 1

Как сказал Ира, для выполнения этой работы вам нужен оценщик выражений, такой как Lex / Yacc, у вас есть множество доступных здесь:

http://wiki.python.org/moin/LanguageParsing

Я использовал pyparsing и отлично работает для такого рода вещей

Answer 2

Я вижу, что идея eval уже упоминалась, и это не поможет, если у вас есть операторы для замены, но в прошлом я использовал следующее:

def evaluate_expression(expr, context):
    try:
        return eval(expr, {'__builtins__': None}, context)
    except (TypeError, ZeroDivisionError, SyntaxError):
        # TypeError is when combining items in the wrong way (ie, None + 4)
        # ZeroDivisionError is when the denominator happens to be zero (5/0)
        # SyntaxError is when the expression is invalid
        return None

Вы можете сделать что-то вроде:

values = {
    'a': 1.0,
    'b': 5.0,
    'c': 1.0,
}
evaluate_expression('a + b - (1/c)', **values)

, что оценивается в 1,0 + 5,0 - 1 / 1,0 == 5,0

Опять же, это не позволит вам подставлять в операторы, то есть вы не можете позволить 'd' вычислять +, но это дает вам безопасный способ использования функции eval в Python (вы можете ' например, запустить "while True").

См. этот пример для получения дополнительной информации о безопасном использовании eval.

Answer 3

Разобрать эту строку в дереве (или эквивалентно интерпретируемой структуре данных), всего один раз, а затем повторно использовать функцию для «интерпретации дерева» для каждого интересующего набора назначений переменных. (Вы даже можете сгенерировать байт-код Python в качестве «интерпретируемой структуры данных», так что вы можете просто использовать eval в качестве «интерпретации дерева» - что делает для медленной генерации, но это требуется только один раз, и для быстрой интерпретации). *

Как вы говорите, это немного абстрактно, поэтому давайте приведем конкретный, хотя и упрощенный пример. Скажем, например, что переменные - это буквы x, y, z, t, а операторы - для сложения и s для вычитания - строки смежных букв неявно означают высокоприоритетное умножение, как в общем математическом соглашении; нет круглых скобок и строгое выполнение слева направо (т.е. нет приоритета оператора, кроме умножения). Каждый символ кроме этих 6 должен игнорироваться. Итак, вот очень специальный анализатор и генератор байт-кода Python:

class BadString(Exception): pass

def makeBytecode(thestring):
  theoperator = dict(a='+', s='-')
  python = []
  state = 'start'
  for i, letter in enumerate(thestring):
    if letter in 'xyzt':
      if state == 'start':
        python.append(letter)
        state = 'variable'
      elif state == 'variable':
        python.append('*')
        python.append(letter)
    elif letter in 'as':
      if state == 'start':
        raise BadString(
            'Unexpected operator %r at column %d' % (letter, i))
      python.append(theoperator[letter])
      state = 'start'

  if state != 'variable':
    raise BadString(
      'Unexpected operator %r at end of string' % letter)
  python = ''.join(python)
  # sanity check
  # print 'Python for %r is %r' % (thestring, python)
  return compile(python, thestring, 'eval')

Теперь вы можете просто вызвать eval с результатом этого в качестве первого аргумента и с помощью dict, связывающего значения с x, y, z и t в качестве второго аргумента. Например (импортировав вышеупомянутый модуль как par и раскомментировав проверку работоспособности):

>>> c=par.makeBytecode('xyax')
Python for 'xyax' is 'x*y+x'
>>> for x in range(4):
...   for y in range(5):
...     print 'x=%s, y=%s: result=%s' % (x,y,eval(c,dict(x=x,y=y)))
... 
x=0, y=0: result=0
x=0, y=1: result=0
x=0, y=2: result=0
x=0, y=3: result=0
x=0, y=4: result=0
x=1, y=0: result=1
x=1, y=1: result=2
x=1, y=2: result=3
x=1, y=3: result=4
x=1, y=4: result=5
x=2, y=0: result=2
x=2, y=1: result=4
x=2, y=2: result=6
x=2, y=3: result=8
x=2, y=4: result=10
x=3, y=0: result=3
x=3, y=1: result=6
x=3, y=2: result=9
x=3, y=3: result=12
x=3, y=4: result=15
>>> 

Более сложный, но все же простой !, анализ строки & построение быстро интерпретируемой структуры данных, см., Например, pyparsing .

Answer 4

То, что вы хотите, очевидно, является оценщиком выражений.

В других случаях вы используете встроенное средство на языке, обычно называемом «eval» (я не знаю, предлагает ли это Python), или вы создаете анализатор / оценку выражений.

Чтобы получить некоторые идеи о том, как построить такой оценщик выражений, Вы можете посмотреть на следующее упражнение для гольфа: Code Golf: средство оценки математических выражений (в соответствии с PEMDAS)

Чтобы сделать то, что вы хотите, вам нужно перевести основные идеи (все они почти одинаковые) на Pythonese и добавить средство для анализа имен переменных и поиска их значений. Это должно быть очень простым расширением.