Ocena wyrażenia matematycznego w ciągu

stringExp = "2^4"
intVal = int(stringExp)      # Expected value: 16

To zwraca następujący błąd:

Traceback (most recent call last):  
File "<stdin>", line 1, in <module>
ValueError: invalid literal for int()
with base 10: '2^4'

Wiem, że evalmożna to obejść, ale czy nie ma lepszej i - co ważniejsze - bezpieczniejszej metody oceny wyrażenia matematycznego przechowywanego w ciągu?

Pyparsing może służyć do analizowania wyrażeń matematycznych. W szczególności fourFn.py pokazuje, jak analizować podstawowe wyrażenia arytmetyczne. Poniżej przepisałem fourFn na numeryczną klasę parsera, aby ułatwić ponowne użycie.

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

Możesz tego używać w ten sposób

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

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

eval jest zły

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

Uwaga: nawet jeśli używasz zestawu __builtins__do Noneniego nadal może być możliwe, aby wyrwać się za pomocą introspekcji:

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

Oblicz wyrażenie arytmetyczne za pomocą 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)

Możesz łatwo ograniczyć dozwolony zakres dla każdej operacji lub dowolnego wyniku pośredniego, np. Aby ograniczyć argumenty wejściowe dla 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

Lub w celu ograniczenia zakresu wyników pośrednich:

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

Przykład

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

Niektóre bezpieczniejsze alternatywy dla eval()i ^* :sympy.sympify().evalf()

• asteval
• numexpr

^* SymPy sympifyjest również niebezpieczny, zgodnie z następującym ostrzeżeniem zawartym w dokumentacji.

Ostrzeżenie: Zwróć uwagę, że ta funkcja używa eval, a zatem nie powinna być używana w przypadku niezanizowanych danych wejściowych.

Okay, więc problem z eval polega na tym, że zbyt łatwo może uciec ze swojej piaskownicy, nawet jeśli się go pozbędziesz __builtins__. Wszystkie metody ucieczki z piaskownicy sprowadzają się do użycia getattrlub object.__getattribute__(przez .operatora) w celu uzyskania odniesienia do jakiegoś niebezpiecznego obiektu za pośrednictwem dozwolonego obiektu ( ''.__class__.__bases__[0].__subclasses__lub podobnego). getattrjest eliminowana przez ustawienie __builtins__na None. object.__getattribute__jest trudna, ponieważ nie można jej tak po prostu usunąć, zarówno dlatego, że objectjest niezmienna, jak i dlatego, że jej usunięcie zepsułoby wszystko. Jednak __getattribute__jest dostępny tylko przez .operatora, więc wyczyszczenie tego z danych wejściowych jest wystarczające, aby upewnić się, że eval nie wydostanie się z piaskownicy.
W formułach przetwarzania liczb dziesiętnych można używać tylko wtedy, gdy są poprzedzone lub zakończone[0-9], więc po prostu usuwamy wszystkie inne wystąpienia ..

import re
inp = re.sub(r"\.(?![0-9])","", inp)
val = eval(inp, {'__builtins__':None})

Zauważ, że podczas gdy Python normalnie traktuje 1 + 1.jako 1 + 1.0, to usunie to końcowe .i pozostawi cię z 1 + 1. Mógłbyś dodać ), i EOFdo listy rzeczy, które można śledzić ., ale po co?

Możesz użyć modułu ast i napisać NodeVisitor, który sprawdza, czy typ każdego węzła jest częścią białej listy.

import ast, math

locals =  {key: value for (key,value) in vars(math).items() if key[0] != '_'}
locals.update({"abs": abs, "complex": complex, "min": min, "max": max, "pow": pow, "round": round})

class Visitor(ast.NodeVisitor):
    def visit(self, node):
       if not isinstance(node, self.whitelist):
           raise ValueError(node)
       return super().visit(node)

    whitelist = (ast.Module, ast.Expr, ast.Load, ast.Expression, ast.Add, ast.Sub, ast.UnaryOp, ast.Num, ast.BinOp,
            ast.Mult, ast.Div, ast.Pow, ast.BitOr, ast.BitAnd, ast.BitXor, ast.USub, ast.UAdd, ast.FloorDiv, ast.Mod,
            ast.LShift, ast.RShift, ast.Invert, ast.Call, ast.Name)

def evaluate(expr, locals = {}):
    if any(elem in expr for elem in '\n#') : raise ValueError(expr)
    try:
        node = ast.parse(expr.strip(), mode='eval')
        Visitor().visit(node)
        return eval(compile(node, "<string>", "eval"), {'__builtins__': None}, locals)
    except Exception: raise ValueError(expr)

Ponieważ działa za pośrednictwem białej listy, a nie czarnej listy, jest bezpieczny. Jedyne funkcje i zmienne, do których ma dostęp, to te, do których jawnie dajesz dostęp. Dyktowałem funkcjami związanymi z matematyką, więc jeśli chcesz, możesz łatwo zapewnić dostęp do nich, ale musisz jawnie ich użyć.

Jeśli ciąg próbuje wywołać funkcje, które nie zostały dostarczone, lub wywołać jakiekolwiek metody, zostanie zgłoszony wyjątek i nie zostanie wykonany.

Ponieważ używa to wbudowanego analizatora i analizatora Pythona, dziedziczy również pierwszeństwo i reguły promocji Pythona.

>>> evaluate("7 + 9 * (2 << 2)")
79
>>> evaluate("6 // 2 + 0.0")
3.0

Powyższy kod został przetestowany tylko w Pythonie 3.

Jeśli chcesz, możesz dodać dekorator limitu czasu do tej funkcji.

Powodem evali execsą tak niebezpieczne jest to, że compilefunkcja domyślna wygeneruje kod bajtowy dla dowolnego prawidłowego wyrażenia Pythona, a domyślny evallub execwykona dowolny prawidłowy kod bajtowy Pythona. Wszystkie dotychczasowe odpowiedzi skupiały się na ograniczaniu kodu bajtowego, który może być generowany (poprzez odkażanie danych wejściowych) lub budowaniu własnego języka specyficznego dla domeny za pomocą AST.

Zamiast tego możesz łatwo utworzyć prostą evalfunkcję, która nie jest w stanie zrobić niczego nikczemnego i może łatwo sprawdzić w czasie wykonywania pamięć lub wykorzystany czas. Oczywiście, jeśli jest to prosta matematyka, istnieje skrót.

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]

Sposób, w jaki to działa, jest prosty, każde stałe wyrażenie matematyczne jest bezpiecznie oceniane podczas kompilacji i przechowywane jako stała. Obiekt kodu zwrócony przez kompilację składa się z dkodu bajtowego dla LOAD_CONST, po którym następuje numer stałej do załadowania (zwykle ostatnia na liście), po Sktórym następuje kod bajtowy dla RETURN_VALUE. Jeśli ten skrót nie działa, oznacza to, że dane wejściowe użytkownika nie są wyrażeniem stałym (zawierają zmienną, wywołanie funkcji lub podobne).

Otwiera to również drzwi do bardziej wyrafinowanych formatów wejściowych. Na przykład:

stringExp = "1 + cos(2)"

Wymaga to rzeczywistej oceny kodu bajtowego, co nadal jest dość proste. Kod bajtowy Pythona jest językiem zorientowanym na stos, więc wszystko jest proste TOS=stack.pop(); op(TOS); stack.put(TOS)lub podobne. Kluczem jest implementacja tylko tych opkodów, które są bezpieczne (ładowanie / przechowywanie wartości, operacje matematyczne, zwracanie wartości), a nie niebezpiecznych (wyszukiwanie atrybutów). Jeśli chcesz, aby użytkownik mógł wywoływać funkcje (cały powód, aby nie używać powyższego skrótu), w prosty sposób wprowadź w życie CALL_FUNCTIONtylko zezwalanie na funkcje na liście „bezpiecznych”.

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

Oczywiście rzeczywista wersja byłaby nieco dłuższa (jest 119 rozkazów, z których 24 są związane z matematyką). Dodanie STORE_FASTi kilka innych pozwoliłoby na wprowadzenie podobnych 'x=5;return x+xlub podobnych, trywialnie łatwo. Może być nawet używany do wykonywania funkcji utworzonych przez użytkownika, o ile funkcje utworzone przez użytkownika są wykonywane przez VMeval (nie należy ich wywoływać !!! w przeciwnym razie mogą zostać użyte jako wywołanie zwrotne). Obsługa pętli wymaga obsługi gotokodów bajtowych, co oznacza zmianę z foriteratora whilena bieżącą instrukcję i utrzymywanie wskaźnika do bieżącej instrukcji, ale nie jest to zbyt trudne. Aby uzyskać odporność na DOS, główna pętla powinna sprawdzać, ile czasu minęło od rozpoczęcia obliczeń, a niektórzy operatorzy powinni odmawiać wprowadzania danych powyżej rozsądnego limitu (BINARY_POWER jest najbardziej oczywiste).

Chociaż to podejście jest nieco dłuższe niż prosty parser gramatyczny dla prostych wyrażeń (patrz wyżej o zwykłym przechwytywaniu skompilowanej stałej), rozciąga się łatwo na bardziej skomplikowane dane wejściowe i nie wymaga zajmowania się gramatyką ( compileweź wszystko, co jest dowolnie skomplikowane i redukuje je do sekwencja prostych instrukcji).

Myślę, że użyłbym eval(), ale najpierw sprawdziłbym, czy ciąg jest prawidłowym wyrażeniem matematycznym, w przeciwieństwie do czegoś złośliwego. Możesz użyć wyrażenia regularnego do walidacji.

eval() pobiera również dodatkowe argumenty, których możesz użyć do ograniczenia przestrzeni nazw, w której działa, dla większego bezpieczeństwa.

To bardzo późna odpowiedź, ale myślę, że będzie przydatna w przyszłości. Zamiast pisać swój własny parser matematyczny (chociaż powyższy przykład pyparsingu jest świetny), możesz użyć SymPy. Nie mam z tym dużego doświadczenia, ale zawiera o wiele potężniejszy silnik matematyczny, niż ktokolwiek mógłby napisać dla konkretnej aplikacji, a podstawowa ocena wyrażenia jest bardzo łatwa:

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

Naprawdę super! A from sympy import *zapewnia o wiele więcej obsługi funkcji, takich jak funkcje trygonometryczne, funkcje specjalne itp., Ale unikałem tego tutaj, aby pokazać, co przychodzi skąd.

[Wiem, że to stare pytanie, ale warto wskazać nowe przydatne rozwiązania, gdy się pojawią]

Od pythona 3.6 ta funkcja jest teraz wbudowana w język , tworząc „f-strings” .

Zobacz: PEP 498 - Interpolacja dosłownych ciągów znaków

Na przykład (zwróć uwagę na fprzedrostek):

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

Użyj evalw czystej przestrzeni nazw:

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

Czysta przestrzeń nazw powinna uniemożliwić wstrzyknięcie. Na przykład:

>>> 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__'

W przeciwnym razie otrzymasz:

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

Możesz dać dostęp do modułu matematycznego:

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

Oto moje rozwiązanie problemu bez użycia eval. Działa z Python2 i Python3. Nie działa z liczbami ujemnymi.

$ python -m pytest test.py

test.py

from solution import Solutions

class SolutionsTestCase(unittest.TestCase):
    def setUp(self):
        self.solutions = Solutions()

    def test_evaluate(self):
        expressions = [
            '2+3=5',
            '6+4/2*2=10',
            '3+2.45/8=3.30625',
            '3**3*3/3+3=30',
            '2^4=6'
        ]
        results = [x.split('=')[1] for x in expressions]
        for e in range(len(expressions)):
            if '.' in results[e]:
                results[e] = float(results[e])
            else:
                results[e] = int(results[e])
            self.assertEqual(
                results[e],
                self.solutions.evaluate(expressions[e])
            )

solution.py

class Solutions(object):
    def evaluate(self, exp):
        def format(res):
            if '.' in res:
                try:
                    res = float(res)
                except ValueError:
                    pass
            else:
                try:
                    res = int(res)
                except ValueError:
                    pass
            return res
        def splitter(item, op):
            mul = item.split(op)
            if len(mul) == 2:
                for x in ['^', '*', '/', '+', '-']:
                    if x in mul[0]:
                        mul = [mul[0].split(x)[1], mul[1]]
                    if x in mul[1]:
                        mul = [mul[0], mul[1].split(x)[0]]
            elif len(mul) > 2:
                pass
            else:
                pass
            for x in range(len(mul)):
                mul[x] = format(mul[x])
            return mul
        exp = exp.replace(' ', '')
        if '=' in exp:
            res = exp.split('=')[1]
            res = format(res)
            exp = exp.replace('=%s' % res, '')
        while '^' in exp:
            if '^' in exp:
                itm = splitter(exp, '^')
                res = itm[0] ^ itm[1]
                exp = exp.replace('%s^%s' % (str(itm[0]), str(itm[1])), str(res))
        while '**' in exp:
            if '**' in exp:
                itm = splitter(exp, '**')
                res = itm[0] ** itm[1]
                exp = exp.replace('%s**%s' % (str(itm[0]), str(itm[1])), str(res))
        while '/' in exp:
            if '/' in exp:
                itm = splitter(exp, '/')
                res = itm[0] / itm[1]
                exp = exp.replace('%s/%s' % (str(itm[0]), str(itm[1])), str(res))
        while '*' in exp:
            if '*' in exp:
                itm = splitter(exp, '*')
                res = itm[0] * itm[1]
                exp = exp.replace('%s*%s' % (str(itm[0]), str(itm[1])), str(res))
        while '+' in exp:
            if '+' in exp:
                itm = splitter(exp, '+')
                res = itm[0] + itm[1]
                exp = exp.replace('%s+%s' % (str(itm[0]), str(itm[1])), str(res))
        while '-' in exp:
            if '-' in exp:
                itm = splitter(exp, '-')
                res = itm[0] - itm[1]
                exp = exp.replace('%s-%s' % (str(itm[0]), str(itm[1])), str(res))

        return format(exp)