Парсинг формул в 50 строк на Python / forpes.ru

Главная
Парсинг формул в 50 строк на Python

Парсинг формул в 50 строк на Python +26

16.12.2015 08:45

griganton 9 14300 Источник

Вдохновение — задача с собеседования Яндекса и статья «Парсинг формул в 40 строк».

Моей целью было посмотреть, как будет выглядеть «pythonic» решение этой задачи. Хотелось, чтобы решение было простым, код читаемым и разделённым. В итоге ещё получился и пример применения цепочки генераторов (generators pipeline).

На классический алгоритм решения задачи указал Яндекс в своей статье — Алгоритм сортировочной станции.

Алгоритм преобразует выражения в инфиксной, привычной нам, нотации в обратную польскую.
Вычисление выражения в обратной польской нотации (ОПН) для нас привлекательно тем, что у него простой алгоритм.

Весь алгоритм вычисления выражения разбивается на три части:

парсинг исходной строки на числа и операторы
применение алгоритма сортировочной станции для получения выражения в ОПН
вычисление выражения в ОПН

На выходе этапов 1 и 2 мы получаем массивы из чисел и операторов. Велик соблазн реализовать функцию как цепочку генераторов. Мы сократим потребление памяти, используя «ленивую» обработку данных, где выражение вычисляется по мере поступления чисел и операторов.

Итак, приступим

Для начала, определяем операторы в виде словаря, для каждого символа определим приоритет и функцию вычисления.
Этот словарь нам пригодится также для того, чтобы определять, является ли символ оператором:

OPERATORS = {'+': (1, lambda x, y: x + y), '-': (1, lambda x, y: x - y),
             '*': (2, lambda x, y: x * y), '/': (2, lambda x, y: x / y)}

Определим нашу функцию eval_, на вход которой подаётся строка с вычисляемым выражением:

def eval_(formula_string):

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

1. Парсер исходной строки

Генератор, получает на вход строку, возвращает числа в формате float, операторы и скобки в формате символов.

    def parse(formula_string):
        number = ''
        for s in formula_string:
            if s in '1234567890.': # если символ - цифра, то собираем число
                number += s  
            elif number: # если символ не цифра, то выдаём собранное число и начинаем собирать заново
                yield float(number) 
                number = ''
            if s in OPERATORS or s in "()": # если символ - оператор или скобка, то выдаём как есть
                yield s 
        if number:  # если в конце строки есть число, выдаём его
            yield float(number)

2. Алгоритм сортировочной станции

Генератор, получает на вход итерируемый объект из чисел и операторов в инфиксной нотации, возвращает числа и операторов в обратной польской записи.

    def shunting_yard(parsed_formula):
        stack = []  # в качестве стэка используем список
        for token in parsed_formula:
            # если элемент - оператор, то отправляем дальше все операторы из стека, 
            # чей приоритет больше или равен пришедшему,
            # до открывающей скобки или опустошения стека.
            # здесь мы пользуемся тем, что все операторы право-ассоциативны
            if token in OPERATORS: 
                while stack and stack[-1] != "(" and OPERATORS[token][0] <= OPERATORS[stack[-1]][0]:
                    yield stack.pop()
                stack.append(token)
            elif token == ")":
                # если элемент - закрывающая скобка, выдаём все элементы из стека, до открывающей скобки,
                # а открывающую скобку выкидываем из стека.
                while stack:
                    x = stack.pop()
                    if x == "(":
                        break
                    yield x
            elif token == "(":
                # если элемент - открывающая скобка, просто положим её в стек
                stack.append(token)
            else:
                # если элемент - число, отправим его сразу на выход
                yield token
        while stack:
            yield stack.pop()

3. Вычислитель

Функция, получает на вход итерируемый объект чисел и операторов в обратной польской нотации, возвращает результат вычисления:

    def calc(polish):
        stack = []
        for token in polish:
            if token in OPERATORS:  # если приходящий элемент - оператор,
                y, x = stack.pop(), stack.pop()  # забираем 2 числа из стека
                stack.append(OPERATORS[token][1](x, y)) # вычисляем оператор, возвращаем в стек
            else:
                stack.append(token)
        return stack[0] # результат вычисления - единственный элемент в стеке

В конце концов, составляем цепочку генераторов для вычисления результата функции eval_:

    return calc(shunting_yard(parse(formula_string)))

Быстродействие

Самый главный вопрос: «Как быстро работает программа?» Сравним нашу функцию со встроенной функцией eval.

На простейших случаях наша функция даже быстрее!

%timeit eval("2+2")
100000 loops, best of 3: 12.8 µs per loop

%timeit eval_("2+2")
100000 loops, best of 3: 7.61 µs per loop

На выражениях посложнее — на 22% дольше:

%timeit eval("15/(7-(1+1))*3-(2+(1+1))")
10000 loops, best of 3: 29.7 µs per loop

%timeit eval_("15/(7-(1+1))*3-(2+(1+1))")
10000 loops, best of 3: 36.3 µs per loop

На выражениях ещё сложнее — разрыв увеличивается, но всё равно быстродействие нашей функции сравнимо со встроенной:

%timeit eval("15/(7-(1+1))*3-(2+(1+1))*15/(7-(1+1))*3-(2+(1+1))*(15/(7-(1+1))*3-(2+(1+1))+15/(7-(1+1))*3-(2+(1+1)))")
10000 loops, best of 3: 86.3 µs per loop

%timeit eval_("15/(7-(1+1))*3-(2+(1+1))*15/(7-(1+1))*3-(2+(1+1))*(15/(7-(1+1))*3-(2+(1+1))+15/(7-(1+1))*3-(2+(1+1)))")
10000 loops, best of 3: 147 µs per loop

Да, вспоминая название статьи, тут всего 50 строк, не забывая про читаемость и PEP8!

Код функции целиком

OPERATORS = {'+': (1, lambda x, y: x + y), '-': (1, lambda x, y: x - y),
             '*': (2, lambda x, y: x * y), '/': (2, lambda x, y: x / y)}


def eval_(formula):
    def parse(formula_string):
        number = ''
        for s in formula_string:
            if s in '1234567890.':
                number += s
            elif number:
                yield float(number)
                number = ''
            if s in OPERATORS or s in "()":
                yield s
        if number:
            yield float(number)

    def shunting_yard(parsed_formula):
        stack = []
        for token in parsed_formula:
            if token in OPERATORS:
                while stack and stack[-1] != "(" and OPERATORS[token][0] <= OPERATORS[stack[-1]][0]:
                    yield stack.pop()
                stack.append(token)
            elif token == ")":
                while stack:
                    x = stack.pop()
                    if x == "(":
                        break
                    yield x
            elif token == "(":
                stack.append(token)
            else:
                yield token
        while stack:
            yield stack.pop()

    def calc(polish):
        stack = []
        for token in polish:
            if token in OPERATORS:
                y, x = stack.pop(), stack.pop()
                stack.append(OPERATORS[token][1](x, y))
            else:
                stack.append(token)
        return stack[0]

    return calc(shunting_yard(parse(formula)))

Комментарии (9)

overmes
16.12.2015 13:03
#8690887
+1
Вместо лямбд для операторов проще и удобнее использовать функции из модуля operator:

К тому же они работают чуть быстрее, так как убирают лишний вызов функции.
1. griganton
  16.12.2015 13:19
  #8690931
  Согласен! Ещё у меня была мысль вытащить операторы из класса float — float.__add__ и т.п., но некрасиво вытаскивать приватные методы из классов.
  
  С операторами из модуля operator код меняется на:
  
  import operator OPERATORS = {'+': (1, operator.add), '-': (1, operator.sub), '*': (2, operator.mul), '/': (2, operator.truediv)}
  
  Но в моих замерах я не заметил разницы в производительности.
  С операторами из operator:
  
  %timeit eval2("15/(7-(1+1))*3-(2+(1+1))*15/(7-(1+1))*3-(2+(1+1))*(15/(7-(1+1))*3-(2+(1+1))+15/(7-(1+1))*3-(2+(1+1)))") 10000 loops, best of 3: 141 µs per loop
  
  С lambda функциями:
  
  %timeit eval_("15/(7-(1+1))*3-(2+(1+1))*15/(7-(1+1))*3-(2+(1+1))*(15/(7-(1+1))*3-(2+(1+1))+15/(7-(1+1))*3-(2+(1+1)))") 10000 loops, best of 3: 143 µs per loop
  
  Две миллисекунды не считается, это я мышкой шевелил!
  1. JIghtuse
    16.12.2015 13:51
    #8690999
    У меня на машине более ощутимая разница:
    
    # lambda %timeit eval_("15/(7-(1+1))*3-(2+(1+1))*15/(7-(1+1))*3-(2+(1+1))*(15/(7-(1+1))*3-(2+(1+1))+15/(7-(1+1))*3-(2+(1+1)))") 1000 loops, best of 3: 310 µs per loop # builtin %timeit eval("15/(7-(1+1))*3-(2+(1+1))*15/(7-(1+1))*3-(2+(1+1))*(15/(7-(1+1))*3-(2+(1+1))+15/(7-(1+1))*3-(2+(1+1)))") 10000 loops, best of 3: 72.4 µs per loop # operator In [10]: %timeit eval_("15/(7-(1+1))*3-(2+(1+1))*15/(7-(1+1))*3-(2+(1+1))*(15/(7-(1+1))*3-(2+(1+1))+15/(7-(1+1))*3-(2+(1+1)))") 10000 loops, best of 3: 144 µs per loop
    
    griganton
    16.12.2015 13:56
    #8691023
    Скорость ваших operator сравнима с моей, а лямбда — в 2 раза медленнее. Чем это может быть обусловлено? Это может быть интересно.
    Моя система: Python 3.4.1 |Anaconda 2.1.0 (64-bit)| (default, Sep 24 2014, 18:32:42) [MSC v.1600 64 bit (AMD64)] on win32
  1. overmes
    16.12.2015 14:08
    #8691041
    Скорее всего это не самое узкое место, да и ускоряют они совсем на чуть-чуть.
    
    Еще можно вместо словаря использовать именованный кортеж, он, вроде, тоже чуть-чуть быстрее.
    
    Из экстремальных оптимизаций — можно вынести все обращения к атрибутам из цикла, например:
    stack_pop = stack.pop
    
    но это уже не питоник решение
  1. domix32
    21.12.2015 18:31
    #8697233
    Только mus скорее всего микросекунды
1. JIghtuse
  16.12.2015 13:28
  #8690953
  Вы меня опередили. Ещё мне кажется, что парсить числа `re` было бы быстрее. Накидал пример, но он неправильно считает: gist.github.com/JIghtuse/f4a79de4d1dd4539c960
  
  Отладим…
  1. JIghtuse
    16.12.2015 13:49
    #8690995
    Потерял приведение типа во float. Разницы во времени почти нет gist.github.com/JIghtuse/f4a79de4d1dd4539c960. Вообще, `eval` гораздо больше делает, чем числа считает. Его можно обогнать, но, вероятно, придётся дёргать Си. Скорее всего, он на нём реализован.

encyclopedist
16.12.2015 15:18
#8691205
Стаадии сортировочной станции и вычисления можно объединить используя двустековый алгоритм Дейкстры (Dijkstra's two-stack algorithm).