Оценка математического выражения в строке

Pyparsing можно использовать для анализа математических выражений. В частности, fourFn.py показывает, как анализировать основные арифметические выражения. Ниже я перевернул fourFn в класс числового парсера для более легкого повторного использования.

from __future__ import division
from pyparsing import (Literal, CaselessLiteral, Word, Combine, Group, Optional,
                       ZeroOrMore, Forward, nums, alphas, oneOf)
import math
import operator

__author__ = 'Paul McGuire'
__version__ = '$Revision: 0.0 $'
__date__ = '$Date: 2009-03-20 $'
__source__ = '''http://pyparsing.wikispaces.com/file/view/fourFn.py
http://pyparsing.wikispaces.com/message/view/home/15549426
'''
__note__ = '''
All I've done is rewrap Paul McGuire's fourFn.py as a class, so I can use it
more easily in other places.
'''


class NumericStringParser(object):
    '''
    Most of this code comes from the fourFn.py pyparsing example

    '''

    def pushFirst(self, strg, loc, toks):
        self.exprStack.append(toks[0])

    def pushUMinus(self, strg, loc, toks):
        if toks and toks[0] == '-':
            self.exprStack.append('unary -')

    def __init__(self):
        """
        expop   :: '^'
        multop  :: '*' | '/'
        addop   :: '+' | '-'
        integer :: ['+' | '-'] '0'..'9'+
        atom    :: PI | E | real | fn '(' expr ')' | '(' expr ')'
        factor  :: atom [ expop factor ]*
        term    :: factor [ multop factor ]*
        expr    :: term [ addop term ]*
        """
        point = Literal(".")
        e = CaselessLiteral("E")
        fnumber = Combine(Word("+-" + nums, nums) +
                          Optional(point + Optional(Word(nums))) +
                          Optional(e + Word("+-" + nums, nums)))
        ident = Word(alphas, alphas + nums + "_$")
        plus = Literal("+")
        minus = Literal("-")
        mult = Literal("*")
        div = Literal("/")
        lpar = Literal("(").suppress()
        rpar = Literal(")").suppress()
        addop = plus | minus
        multop = mult | div
        expop = Literal("^")
        pi = CaselessLiteral("PI")
        expr = Forward()
        atom = ((Optional(oneOf("- +")) +
                 (ident + lpar + expr + rpar | pi | e | fnumber).setParseAction(self.pushFirst))
                | Optional(oneOf("- +")) + Group(lpar + expr + rpar)
                ).setParseAction(self.pushUMinus)
        # by defining exponentiation as "atom [ ^ factor ]..." instead of
        # "atom [ ^ atom ]...", we get right-to-left exponents, instead of left-to-right
        # that is, 2^3^2 = 2^(3^2), not (2^3)^2.
        factor = Forward()
        factor << atom + \
            ZeroOrMore((expop + factor).setParseAction(self.pushFirst))
        term = factor + \
            ZeroOrMore((multop + factor).setParseAction(self.pushFirst))
        expr << term + \
            ZeroOrMore((addop + term).setParseAction(self.pushFirst))
        # addop_term = ( addop + term ).setParseAction( self.pushFirst )
        # general_term = term + ZeroOrMore( addop_term ) | OneOrMore( addop_term)
        # expr <<  general_term
        self.bnf = expr
        # map operator symbols to corresponding arithmetic operations
        epsilon = 1e-12
        self.opn = {"+": operator.add,
                    "-": operator.sub,
                    "*": operator.mul,
                    "/": operator.truediv,
                    "^": operator.pow}
        self.fn = {"sin": math.sin,
                   "cos": math.cos,
                   "tan": math.tan,
                   "exp": math.exp,
                   "abs": abs,
                   "trunc": lambda a: int(a),
                   "round": round,
                   "sgn": lambda a: abs(a) > epsilon and cmp(a, 0) or 0}

    def evaluateStack(self, s):
        op = s.pop()
        if op == 'unary -':
            return -self.evaluateStack(s)
        if op in "+-*/^":
            op2 = self.evaluateStack(s)
            op1 = self.evaluateStack(s)
            return self.opn[op](op1, op2)
        elif op == "PI":
            return math.pi  # 3.1415926535
        elif op == "E":
            return math.e  # 2.718281828
        elif op in self.fn:
            return self.fn[op](self.evaluateStack(s))
        elif op[0].isalpha():
            return 0
        else:
            return float(op)

    def eval(self, num_string, parseAll=True):
        self.exprStack = []
        results = self.bnf.parseString(num_string, parseAll)
        val = self.evaluateStack(self.exprStack[:])
        return val

Вы можете использовать его следующим образом

nsp = NumericStringParser()
result = nsp.eval('2^4')
print(result)
# 16.0

result = nsp.eval('exp(2^4)')
print(result)
# 8886110.520507872

eval это зло

eval("__import__('os').remove('important file')") # arbitrary commands
eval("9**9**9**9**9**9**9**9", {'__builtins__': None}) # CPU, memory

Примечание: даже если вы используете для __builtins__ значение None это все еще может быть возможно, используя самоанализ:

eval('(1).__class__.__bases__[0].__subclasses__()', {'__builtins__': None})

Оцените арифметическое выражение, используя ast

import ast
import operator as op

# supported operators
operators = {ast.Add: op.add, ast.Sub: op.sub, ast.Mult: op.mul,
             ast.Div: op.truediv, ast.Pow: op.pow, ast.BitXor: op.xor,
             ast.USub: op.neg}

def eval_expr(expr):
    """
    >>> eval_expr('2^6')
    4
    >>> eval_expr('2**6')
    64
    >>> eval_expr('1 + 2*3**(4^5) / (6 + -7)')
    -5.0
    """
    return eval_(ast.parse(expr, mode='eval').body)

def eval_(node):
    if isinstance(node, ast.Num): # <number>
        return node.n
    elif isinstance(node, ast.BinOp): # <left> <operator> <right>
        return operators[type(node.op)](eval_(node.left), eval_(node.right))
    elif isinstance(node, ast.UnaryOp): # <operator> <operand> e.g., -1
        return operators[type(node.op)](eval_(node.operand))
    else:
        raise TypeError(node)

Вы можете легко ограничить допустимый диапазон для каждой операции или любого промежуточного результата, например, чтобы ограничить входные аргументы для a**b:

def power(a, b):
    if any(abs(n) > 100 for n in [a, b]):
        raise ValueError((a,b))
    return op.pow(a, b)
operators[ast.Pow] = power

Или для ограничения величины промежуточных результатов:

import functools

def limit(max_=None):
    """Return decorator that limits allowed returned values."""
    def decorator(func):
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            ret = func(*args, **kwargs)
            try:
                mag = abs(ret)
            except TypeError:
                pass # not applicable
            else:
                if mag > max_:
                    raise ValueError(ret)
            return ret
        return wrapper
    return decorator

eval_ = limit(max_=10**100)(eval_)

Пример

>>> evil = "__import__('os').remove('important file')"
>>> eval_expr(evil) #doctest:+IGNORE_EXCEPTION_DETAIL
Traceback (most recent call last):
...
TypeError:
>>> eval_expr("9**9")
387420489
>>> eval_expr("9**9**9**9**9**9**9**9") #doctest:+IGNORE_EXCEPTION_DETAIL
Traceback (most recent call last):
...
ValueError:

Некоторые более безопасные альтернативы eval() и sympy.sympify().evalf() ^*

• asteval
• Numberxpr

^* SymPy sympify также небезопасно в соответствии со следующим предупреждением из документации.

  

Предупреждение: обратите внимание, что эта функция использует eval и, следовательно, не должна использоваться для неанизированного ввода .

Хорошо, проблема с eval в том, что он может слишком легко покинуть свою песочницу, даже если вы избавитесь от __builtins__. Все методы выхода из песочницы сводятся к использованию getattr или object.__getattribute__ (через оператор .) для получения ссылки на опасный объект через разрешенный объект (''.__class__.__bases__[0].__subclasses__ или аналогичный). getattr удаляется установкой для __builtins__ значения ---- +: = 7 =: + ----. None - сложный вопрос, поскольку его нельзя просто удалить, поскольку object.__getattribute__ является неизменным и потому что удаление его сломало бы все. Однако object доступен только через __getattribute__ оператор, так что очищения от вашего ввода достаточно, чтобы eval не смог покинуть свою песочницу.
При обработке формул единственное допустимое использование десятичного числа - это когда ему предшествует или следует код ., поэтому мы просто удаляем все другие экземпляры [0-9]

.

Обратите внимание, что в то время как python обычно обрабатывает import re inp = re.sub(r"\.(?![0-9])","", inp) val = eval(inp, {'__builtins__':None}) как 1 + 1., это удалит завершающий 1 + 1.0 и оставит вас с .. Вы можете добавить 1 + 1, ) и к списку вещей, которым разрешено следовать EOF, но зачем?

Причина eval и exec настолько опасны, что функция compile по умолчанию сгенерирует байт-код для любого допустимого выражения python, а eval или exec выполнит любой допустимый байт-код Python. Все ответы на сегодняшний день были сосредоточены на ограничении байт-кода, который может быть сгенерирован (путем очистки входных данных), или на создании вашего собственного предметно-ориентированного языка с использованием AST.

Вместо этого вы можете легко создать простую функцию eval, которая не способна делать что-либо плохое и может легко выполнять проверки во время выполнения в памяти или время использовано. Конечно, если это простая математика, то есть ярлык.

c = compile(stringExp, 'userinput', 'eval')
if c.co_code[0]==b'd' and c.co_code[3]==b'S':
    return c.co_consts[ord(c.co_code[1])+ord(c.co_code[2])*256]

Способ, которым это работает, прост: любое математическое выражение константы безопасно оценивается во время компиляции и сохраняется как константа. Кодовый объект, возвращаемый компиляцией, состоит из d, который является байт-кодом для LOAD_CONST, за которым следует номер загружаемой константы (обычно последней в списке), за которой следует S, который является байт-кодом для RETURN_VALUE. Если этот ярлык не работает, это означает, что пользовательский ввод не является константным выражением (содержит вызов переменной или функции или подобное).

Это также открывает двери для некоторых более сложных форматов ввода. Например:

stringExp = "1 + cos(2)"

Это требует фактической оценки байт-кода, что все еще довольно просто. Байт-код Python - это стек-ориентированный язык, поэтому все просто: TOS=stack.pop(); op(TOS); stack.put(TOS) или аналогичный. Ключ заключается в реализации только тех кодов операций, которые безопасны (загрузка /сохранение значений, математические операции, возвращают значения) и не небезопасны (поиск атрибутов). Если вы хотите, чтобы пользователь мог вызывать функции (причина не использовать ярлык выше), просто сделайте свою реализацию CALL_FUNCTION разрешать только функции из «безопасного» списка.

from dis import opmap
from Queue import LifoQueue
from math import sin,cos
import operator

globs = {'sin':sin, 'cos':cos}
safe = globs.values()

stack = LifoQueue()

class BINARY(object):
    def __init__(self, operator):
        self.op=operator
    def __call__(self, context):
        stack.put(self.op(stack.get(),stack.get()))

class UNARY(object):
    def __init__(self, operator):
        self.op=operator
    def __call__(self, context):
        stack.put(self.op(stack.get()))


def CALL_FUNCTION(context, arg):
    argc = arg[0]+arg[1]*256
    args = [stack.get() for i in range(argc)]
    func = stack.get()
    if func not in safe:
        raise TypeError("Function %r now allowed"%func)
    stack.put(func(*args))

def LOAD_CONST(context, arg):
    cons = arg[0]+arg[1]*256
    stack.put(context['code'].co_consts[cons])

def LOAD_NAME(context, arg):
    name_num = arg[0]+arg[1]*256
    name = context['code'].co_names[name_num]
    if name in context['locals']:
        stack.put(context['locals'][name])
    else:
        stack.put(context['globals'][name])

def RETURN_VALUE(context):
    return stack.get()

opfuncs = {
    opmap['BINARY_ADD']: BINARY(operator.add),
    opmap['UNARY_INVERT']: UNARY(operator.invert),
    opmap['CALL_FUNCTION']: CALL_FUNCTION,
    opmap['LOAD_CONST']: LOAD_CONST,
    opmap['LOAD_NAME']: LOAD_NAME
    opmap['RETURN_VALUE']: RETURN_VALUE,
}

def VMeval(c):
    context = dict(locals={}, globals=globs, code=c)
    bci = iter(c.co_code)
    for bytecode in bci:
        func = opfuncs[ord(bytecode)]
        if func.func_code.co_argcount==1:
            ret = func(context)
        else:
            args = ord(bci.next()), ord(bci.next())
            ret = func(context, args)
        if ret:
            return ret

def evaluate(expr):
    return VMeval(compile(expr, 'userinput', 'eval'))

Очевидно, что реальная версия этого будет немного длиннее (есть 119 кодов операций, 24 из которых связаны с математикой). Добавление STORE_FAST и нескольких других позволит вводить данные как 'x=5;return x+x или подобное, тривиально легко. Он может даже использоваться для выполнения пользовательских функций, если пользовательские функции сами выполняются через VMeval (не делайте их вызываемыми !!! или они могут где-то использоваться как обратный вызов). Для обработки циклов требуется поддержка байт-кодов goto, что означает переход с for итератор для while и ведение указателя на текущую инструкцию, но это не так сложно. Для обеспечения устойчивости к DOS основной цикл должен проверять, сколько времени прошло с начала вычислений, а определенные операторы должны отказать в вводе данных через некоторый разумный предел (BINARY_POWER является наиболее очевидным).

Хотя этот подход несколько длиннее, чем простой синтаксический анализатор грамматики для простых выражений (см. выше о простом получении скомпилированной константы), он легко распространяется на более сложные входные данные и не требует работы с грамматикой (compile принять что угодно сложное и свести к последовательности простых инструкций).

Это очень запоздалый ответ, но я считаю его полезным для дальнейшего использования. Вместо того, чтобы писать свой собственный математический парсер (хотя приведенный выше пример pyparsing великолепен), вы можете использовать SymPy. У меня нет большого опыта работы с ним, но он содержит гораздо более мощный математический движок, чем кто-либо может написать для конкретного приложения, и базовая оценка выражений очень проста:

>>> import sympy
>>> x, y, z = sympy.symbols('x y z')
>>> sympy.sympify("x**3 + sin(y)").evalf(subs={x:1, y:-3})
0.858879991940133

Очень круто! from sympy import * обеспечивает гораздо большую поддержку функций, таких как функции триггеров, специальные функции и т. Д., Но я избегал этого здесь показать, что происходит откуда.

[я знаю, что это старый вопрос, но стоит вспомнить новые полезные решения, когда они появляются]

Начиная с python3.6, эта возможность теперь встроена в язык , придумана "f-strings" .

См. PEP 498 - интерполяция буквенных строк

Например (обратите внимание на префикс f ):

f'{2**4}'
=> '16'

Если вы не хотите использовать eval, единственное решение - реализовать соответствующий синтаксический анализатор грамматики. Посмотрите на pyparsing .

Если вы уже используете wolframalpha, у них есть API Python, который позволяет вам оценивать выражения. Может быть немного медленно, но, по крайней мере, очень точно.

https://pypi.python.org/pypi/wolframalpha

Используйте eval в чистом пространстве имен:

>>> ns = {'__builtins__': None}
>>> eval('2 ** 4', ns)
16

Чистое пространство имен должно предотвращать инъекцию. Например:

>>> eval('__builtins__.__import__("os").system("echo got through")', ns)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1, in <module>
AttributeError: 'NoneType' object has no attribute '__import__'

В противном случае вы получите:

>>> eval('__builtins__.__import__("os").system("echo got through")')
got through
0

Возможно, вы захотите предоставить доступ к математическому модулю:

>>> import math
>>> ns = vars(math).copy()
>>> ns['__builtins__'] = None
>>> eval('cos(pi/3)', ns)
0.50000000000000011

В Python уже есть функция для безопасной оценки строк, содержащих буквенные выражения:

http://docs.python.org/2/library/ast.html # ast.literal_eval