Разработчик Python
0,0
рейтинг
16 декабря 2015 в 11:45

Разработка → Парсинг формул в 50 строк на Python из песочницы

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

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

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

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

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

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

На выходе этапов 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)))

Антон Григорьев @griganton
карма
8,0
рейтинг 0,0
Разработчик Python
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

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

  • +1
    Вместо лямбд для операторов проще и удобнее использовать функции из модуля operator:

    К тому же они работают чуть быстрее, так как убирают лишний вызов функции.
    • 0
      Согласен! Ещё у меня была мысль вытащить операторы из класса floatfloat.__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
      

      Две миллисекунды не считается, это я мышкой шевелил!
      • 0
        У меня на машине более ощутимая разница:

        # 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
        
        • 0
          Скорость ваших 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
      • 0
        Скорее всего это не самое узкое место, да и ускоряют они совсем на чуть-чуть.

        Еще можно вместо словаря использовать именованный кортеж, он, вроде, тоже чуть-чуть быстрее.

        Из экстремальных оптимизаций — можно вынести все обращения к атрибутам из цикла, например:
        stack_pop = stack.pop

        но это уже не питоник решение
      • 0
        Только mus скорее всего микросекунды
    • 0
      Вы меня опередили. Ещё мне кажется, что парсить числа `re` было бы быстрее. Накидал пример, но он неправильно считает: gist.github.com/JIghtuse/f4a79de4d1dd4539c960

      Отладим…
      • 0
        Потерял приведение типа во float. Разницы во времени почти нет gist.github.com/JIghtuse/f4a79de4d1dd4539c960. Вообще, `eval` гораздо больше делает, чем числа считает. Его можно обогнать, но, вероятно, придётся дёргать Си. Скорее всего, он на нём реализован.
  • 0
    Стаадии сортировочной станции и вычисления можно объединить используя двустековый алгоритм Дейкстры (Dijkstra's two-stack algorithm).

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.