Попробуем написать синтаксический анализатор математических выражений, который переводит их в обратную польскую запись и вычисляет результат. Например, такое выражение:
6 * (3 + 2)
в обратной польской записи будет выглядеть так:
6 3 2 + *
Для чего нужна такая запись? Во-первых, её можно использовать на некоторых реальных калькуляторах. В ней отсутствуют скобки, и поэтому порядок введения операций в калькулятор последовательный (не требует запоминания промежуточных результатов и т.п.) Во-вторых, она очень просто обрабатывается алгоритмически и потому подходит для различных программных реализаций. Алгоритм действительно очень простой и работает на стеке:
- Получить очередную часть выражения
- Если это число, положить его в стек
- Если это операция, то достать из стека 2 числа, сделать с ними эту операцию, и результат положить назад в стек.
После обработки всего выражения результат будет лежать на вершине стека.
Читайте также: Что такое стек?
Результат: 30.
Итак, начнём с написания синтаксического анализатора для исходных выражений. Требуется на основании входной строки получить структуру, в которой будут сохранены уже отдельные операнды и операции для дальнейшего использования. Необходимо учитывать следующие условия:
- Умножение и деление имеют приоритет над сложением и вычитанием
- Скобки имеют приоритет над любыми операциями
Если вы приступаете к этой задаче с нуля, в голове может не быть ясности, и это нормально. Совет здесь только один – не пишите сразу готовый анализатор, просто начните хоть с чего-то, хотя бы с перебора символов в строке и с определения, чем они являются. После этого начнут появляться различные мысли.
Чтобы пока не усложнять код, будем считать, что все числа – целые и положительные. Значит, исходное выражение состоит только из цифр 0..9, скобок () и знаков +-*/.
Допустим, мы движемся по строке посимвольно и смотрим, чему равен текущий символ. Если это цифра, значит мы в данный момент читаем число. Но число может состоять из нескольких цифр. Значит, надо аккумулировать прочитанные цифры в одной переменной.
А если мы встретим скобку или знак операции? Это не цифра, поэтому мы будем знать, что число закончилось (или вообще не начиналось). Аккумулированный до этого результат (если он не пустой) станет финальным числом, мы сохраним его и будем готовы аккумулировать следующее.
А если это не цифра, то что? Открывающая или закрывающая скобка? Пока непонятно, что с ней делать, просто пропустим её. Это знак операции? Вычислять пока ничего не надо, поэтому здесь всё просто – сохраним знак как часть выражения, так же как мы сохранили число.
Набросаем простейший код на Питоне:
И для строки '128*(3+64)-1' мы получаем результат:
['128', '*', '3', '+', '64', '-', '1']
То есть это список, где уже "раскиданы" конкретные числа и конкретные операции.
Код пока ещё ОЧЕНЬ сырой. В частности, в нём нет никакой обработки ошибок. Я делаю так исключительно для того, чтобы не отвлекаться от главного.
Из полученного списка уже можно было бы сформировать обратную польскую запись, но не хватает информации о приоритете операций. Сначала должна выполниться операция "+", затем "*", затем "-". В обратной польской записи это должно выглядеть так:
128 3 64 + * 1 -
Короче говоря, нужно вместе со знаками операций сохранять и их приоритет. Сделать это довольно просто: мы и так знаем, что '*' и '/' более приоритетны, чем '+' и '-', но есть ещё скобки. Мы их пока пропускали, но теперь обработаем так: каждая открывающая скобка поднимает базовый приоритет, а каждая закрывающая снижает его.
Пусть операции '+' и '-' имеют приоритет 0, а операции '*' и '/' приоритет 1. Тогда реальный приоритет каждой операции будет складываться из её собственного приоритета и базового приоритета. Увеличение базового приоритета должно происходить на шаг больший, чем максимальный приоритет операции. То есть у наших операций максимальный приоритет это 1. Значит, базовый приоритет должен увеличиваться минимум на 2 с каждой открывающей скобкой. Тогда любые операции внутри скобок будут иметь заведомо больший приоритет, чем вне их.
И теперь мы получили такой результат:
['128', ('*', 1), '3', ('+', 2), '64', ('-', 0), '1']
То есть там, где сохранялся просто знак, теперь сохраняется мини-список со знаком и приоритетом. Приоритеты уже правильные. Если мы выберем операции в нужном порядке (от максимального приоритета к минимальному), то уже сможем составить обратную польскую запись.
Но как перебрать их в нужном порядке? Искать в списке операцию с максимальным приоритетом, обрабатывать её, потом опять искать... Можно, но это всё как-то печально.
Давайте сделаем чуть проще. Отследим максимальный приоритет непосредственно при разборе строки и сохраним его в переменной. И с него будем начинать разбор списка.
То есть мы пройдём по списку, выберем все операции, у которых приоритет равен максимальному, и обработаем их.
Затем уменьшим максимальный приоритет, ещё раз пройдём по списку результатов, и обработаем все операции с этим приоритетом. Потом опять уменьшим приоритет и т.д., пока не обработаем все операции.
Хорошо, а как именно мы будем обрабатывать операции? Напомню расклад:
Мы начинаем с операции '+' (приоритет 2). Слева и справа от неё стоят два числа: 3 и 64. Так как у этой операции максимальный приоритет, то числа "притягиваются" именно к ней. Для переноса в польскую нотацию мы запишем эти два числа и операцию:
3 64 +
Весь этот результат, то есть '3 64 +' целиком, мы поместим обратно в список вместо трёх элементов: (3, '+', 64), и удалим лишние элементы. Там, где были три элемента "3, +, 64", теперь один элемент, который содержит в себе всю эту операцию.
Было:
['128', ('*', 1), '3', ('+', 2), '64', ('-', 0), '1']
Стало:
['128', ('*', 1), '3 64 +', ('-', 0), '1']
Следующая операция – '*' (приоритет 1). Слева от неё число 128, а справа – та самая операция, которую мы обработали на предыдущем шаге. Делаем то же самое, то есть переписываем левую часть, правую часть и знак:
128 3 64 + *
И вставляем то, что получилось, на старое место, удаляя лишние элементы. Теперь список имеет вид:
['128 3 64 + *', ('-', 0), '1']
Осталось обработать операцию '-' (приоритет 0). Слева от неё – операция, полученная на предыдущем шаге, справа – число 1. Повторяем запись "лево-право-знак":
128 3 64 + * 1 -
И помещаем обратно в список, удаляя лишние элементы:
['128 3 64 + * 1 -']
Всё, в списке не осталось больше знаков операций и остался один элемент, который и является обратной польской записью.
Допишем код, добавив в него запоминание максимального приоритета и обход списка с генерацией польской записи (ссылка):
Замечание
- В целях экономии места был написан примитивный код, который сломается, если в исходном выражении что-то будет неправильно. Добавление различных условий и проверок сделает код замусоренным. Но мы не откажемся от проверок, а просто сделаем более элегантное решение с использованием ООП.
- Обработка списка с операциями это, если приглядеться, построение дерева в неявном виде. Мы могли бы строить дерево более наглядно, но опять же это заняло бы больше места. Освоившись с базовым решением, мы также сделаем вариант с явным деревом в ООП.
Читайте также: Введение в ООП, Решения задач
Следующая часть:
