Вдохновение — задача с собеседования Яндекса и статья «Парсинг формул в 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)))
ссылка на оригинал статьи http://habrahabr.ru/post/273253/
Добавить комментарий