Обратная польская нотация, что ты такое? Или как вывести производную сложной функции
В прошлом году я участвовал в Чемпионате Урала и там была задачка, что то на подобии перевода обратной польской нотации, в обычную польскую нотацию. В этом году я опять столкнулся с ОПН, но уже в качестве лабораторной работы. Если вкратце задача лабораторной звучала как то, так:
Пользователь вводит с клавиатуры выражение, нужно вывести его решение
В случае наличия x, вывести производную этого выражения
Если по первой подзадаче в интернете куча инфы, то вот по нахождению производной через польскую нотацию, не так много или она подана для более опытных соискателей. Я хочу рассказать как я пришел к своему решению подзадачи, ну и поделиться простеньким кодом который думаю будет понятен всем, и который можно будет спокойно перенести на любой другой язык.
Для начала разберемся с тем что такое обратная польская нотация и для чего она нужна.
Обратная польская нотация — удобный вид записи математического выражения, в записи которого учитывается приоритет операций. На словах не очень понятно, но перейдем к примеру.
Выражение в обратной польской записи
В такой записи у нас сначала идут числа потом операции над которыми будет проводиться эта операция, в данном примере идет 8 7 *, это означает что нам нужно умножить два числа стоящих перед операцией и заменить эти компоненты на получившееся значение. Повторяем действия пока не останется единственное число, являющееся результатом выражения.
Особо внимательные, могли заметить что операции, подозрительно похожи на бинарное дерево. Поздравляю, вы правы так и есть. Обратная польская нотация — это топологическая сортировка дерева решений выражения.
Пример представления в виде дерева
Перед тем как, переводить выражения с клавиатуры, давайте научимся считать уже переведенное выражение. Но перед этим нужно уточнить что в своем решении я буду использовать Стек, подробнее про него можно прочитать тут, но я расскажу о нем в двух словах.
Представьте что у нас есть коробка в которую мы можем либо докладывать книжки вверх в стопку, либо взять верхнюю из стопки книжку. Брать из середины или самую нижнюю книжку нельзя. Мы всегда работаем только с верхушкой коробки. Такая коробка и называется стеком.
Для удобства я буду вместо стека использовать обычный list в Python, потому что у него есть схожие функции.
Пусть у нас есть массив [»3»,»8»,»7»,»*»,»+»,»1»,»-»], давайте будем идти по нему и проверять если текущий токен не является операцией, то закидываем его в результирующий стек. Если же текущий элемент операция вытаскиваем два значения из результирующего стека, считаем получившееся под выражение и кладем в стек ответ.
operations = ["+", "-", "/", "*", "^"]
polish_notation = ["3", "8", "7", "*", "+", "1", "-"]
answer_stack = []
for token in polish_notation:
if token in operations:
b = answer_stack.pop()
a = answer_stack.pop()
if token == "+":
answer_stack.append(a + b)
elif token == "-":
answer_stack.append(a - b)
elif token == "/":
answer_stack.append(a / b)
elif token == "*":
answer_stack.append(a * b)
else:
answer_stack.append(a ** b)
else:
answer_stack.append(int(token))
print(answer_stack[0])Для удобства модернизации я вынесу операции в отдельную функцию:
def get_value(a, b, token):
if token == "+":
return a + b
elif token == "-":
return a - b
elif token == "/":
return a / b
elif token == "*":
return a * b
else:
return a ** b
operations = ["+", "-", "/", "*", "^", "(", ")"]
polish_notation = ["3", "8", "7", "*", "+", "1", "-"]
answer_stack = []
for token in polish_notation:
if token in operations:
b = answer_stack.pop()
a = answer_stack.pop()
answer_stack.append(get_value(a, b, token))
else:
answer_stack.append(int(token))
print(answer_stack[0])Как не сложно заметить, я в своем решении использую «токены» — выражение разбитое на понятные для компьютера компоненты. Далее в статье, я разберу как разбивать введенное с клавиатуры выражение на такие токены. Да это немного замедлит асимптотическую сложность программы, но поверьте потери не значительны перед удобством данного способа.
Теперь давайте, разберем алгоритм перевода токенов строки, в обратную польскую запись.
Для начала нам нужно понять, каким образом можно учитывать приоритет математических операций. Еще с начальной школы все знают что умножение и деление идет раньше чем сложение и вычитание. Но компилятору как то пофиг на эти приоритеты для него : что »+», что »*» — это просто разные строки. Давайте укажем алгоритму с какими приоритетами ему нужно работать. Я для себя определил вот такие приоритеты:
priority = {
"sin": 3,
"cos": 3,
"ctg": 3,
"tg": 3,
"_": 2,
"^": 2,
"*": 1,
"/": 1,
"%": 1,
"+": 0,
"-": 0,
"(": -2,
")": -1,
}Дальше нам нужно понять, в какие места нам нужно вставить наши операции. Для этого воспользуемся таким алгоритмом:
1) Заводим массив для формирования польской нотации и стек ожидания вставки операции
2) Пройдемся циклом по массиву и будем проверять текущий токен является ли операцией:
а )Если текущий токен не является операцией то закидываем его в ответ
b) Иначе вытаскиваем из стека ожидания все операции чей приоритет выше текущего токена в ответ, и в конце закидываем текущий токен в стек ожидания
3) Вытаскиваем из стека ожидания все оставшиеся операции
Почему это работает, ну давайте разберем тест
В момент когда к нам придет операция »*» , если мы вытащим »+» из стека ожидания и запишем его в ответ. Мы получим примерно такой массив [»3»,»8»,»+»] , давайте применим алгоритм решения который мы писали чуть выше и получим 11 в ответе, что уже не верно. Думаю из этого понятно что операции приоритет которых выше должны идти в ответе рядом с теми компонентами, к которым они относятся и раньше операций приоритет которых ниже текущей. А данным алгоритмом мы можем обеспечить это условие.
Ну и немного кода реализующий данный алгоритм:
tokens = ["3", "+", "8", "*", "7", "-", "1"]
polish_notation = []
# стек ожидания операций
stack_of_operations = []
for token in tokens:
# проверяем что наш токен это операция
if token in operations:
# вытаскиваем все операции у которых преоритет выше текущей операции
while len(stack_of_operations) != 0 and \
priority[stack_of_operations[-1]] > priority[token]:
polish_notation.append(stack_of_operations.pop())
# и заносим нашу операцию в стек ожидания
stack_of_operations.append(token)
else:
polish_notation.append(token)
# вытаскием все оставшиеся в стеке ожидания операции
while len(stack_of_operations) != 0:
polish_notation.append(stack_of_operations.pop())
# тут мы уже перевели наш массив токенов
# polish_notation = ['3', '8', '7', '*', '1', '-', '+']Не трудно заметить что при таком подходе операция возведения в степень, будет записана раньше чем умножение или деление. Но мы забыли про скобки, в школе учили что сначала выполняется выражение в скобках, а уже после этого все операции не входящие в них.
Ну тут алгоритм не сильно усложняется, ведь по сути нам нужно провернуть все тоже самое только для выражения в скобках. А уже после этого продолжить выполнять алгоритм как раньше.
Так каков план действий?
Если мы встретили открывающую скобку , заносим ее в лист ожидания с приоритетом -2
Продолжаем выполнение алгоритма как обычно, из за того что мы выставили такой маленький приоритет все операции будут заноситься в стек и ответ так как будто бы мы начали все сначала, тоесть как будто бы мы отдельно обрабатываем чисто кусочек в скобках. Главное случайно не вытащить открывающую скобку.
Как только мы встретили закрывающую скобку, вытаскиваем из стека ожидания все операции до открывающей скобки. после этого просто удаляем из стека открывающую скобку, не занося ее в ответ.
Продолжаем выполнение алгоритма как раньше.
Разберем на примере получившуюся запись. Красным отмечен порядок выполнения вычислений.
Получается что нам больше не нужны скобки и приоритет операций соблюден.
Теперь добавим буквально пару изменений в наш код
tokens = ["4", "*", "(", "2", "+", "3", "*", "2", ")", "+", "4"]
polish_notation = []
stack_of_operations = []
for token in tokens:
if token in operations:
# проверяем что это не закрывающая скобка
if token != ")":
while len(stack_of_operations) != 0 and \
priority[stack_of_operations[-1]] > priority[token] and \
token != "(":
polish_notation.append(stack_of_operations.pop())
stack_of_operations.append(token)
else:
# вытаскиваем в ответ все операции до открывающей скобки
while len(stack_of_operations) != 0 \
and stack_of_operations[-1] != "(":
polish_notation.append(stack_of_operations.pop())
# вытаскиваем саму открывающую скобку
stack_of_operations.pop()
else:
polish_notation.append(token)
while len(stack_of_operations) != 0:
polish_notation.append(stack_of_operations.pop())
# тут мы уже перевели наш массив токенов
# polish_notation = ['4', '2', '3', '2', '*', '+', '*', '4', '+']Таким образом мы научились работать со скобочками и их приоритетами.
