0

嘿。我有一个我想用 Python 解决的问题，我想不出一个聪明的实现。输入是一串字母。其中一些代表变量，另一些代表运算符，我想迭代变量的大量值（不同的配置）。

我认为一个等价的问题是你得到一个方程，其中有许多变量存储为字符串，当你用 x、y、z 等替换许多不同的值或满足布尔公式时，你想看到解决方案。

我想不出任何聪明的数据结构可以实现这一点 - 每次都“设置”公式，替换变量，比实际评估它花费更多时间。

我知道这有点抽象 - 但有人有任何想法或有类似的经验吗？

有人建议我想实现一个评估器。这是真的，但题外话。为了这个问题，假设 eval(string) 函数已经实现。什么是有效的数据结构，可以保存值并允许每次都干净有效地更改它们？肯定不是字符串！它必须是一个可修改的列表。如果它有几个变量 x 的实例，它应该能够快速访问它们并在评估之前更改它们的值等等。

4

4 回答 4

1

正如 Ira 所说，您需要像 Lex/Yacc 这样的表达式评估器来完成这项工作，您在这里有很多可用的：

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

我一直在使用pyparsing并且在这类事情上效果很好

于 2009-09-13T17:42:08.877 回答
0

你想要的显然是一个表达式评估器。

其他您使用通常称为“eval”的语言中的内置工具（我不知道 Python 是否提供此功能），或者您构建表达式解析器/评估器。

要获得有关如何构建这样一个表达式评估器的一些想法，您可以查看以下 SO 高尔夫练习： Code Golf：数学表达式评估器（尊重 PEMDAS）

为了做你想做的事，你必须将基本思想（它们几乎都一样）翻译成 Pythonese，并添加一个工具来解析变量名并查找它们的值。这应该是一个非常简单的扩展。

于 2009-09-13T17:18:24.497 回答
0

将该字符串解析为树（或等效可解释的数据结构），只需一次，然后重复使用函数为每个感兴趣的变量分配集“解释树”。（您甚至可以将 Python 字节码生成为“可解释的数据结构”，这样您就可以将eval其用作“解释树”——这会导致生成缓慢，但只需要一次，并且可以快速解释）。

正如您所说，这有点抽象，所以让我们举一个具体的，如果过于简单化的例子。例如，变量是字母 x、y、z、t，运算符是用于加法的 a 和用于减法的 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')

现在，您可以简单地将evalthis 的结果作为第一个参数调用，并将与 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。

于 2009-09-13T17:39:22.483 回答
0

我看到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

于 2009-09-13T17:56:41.407 回答