В предыдущей части был написан транслятор математических выражений, который переводит их из обычной (инфиксной) в обратную польскую (постфиксную) запись. Это был примитивный код, нацеленный только на то, чтобы получить рабочий прототип и освоить саму идею.
Теперь мы его усовершенствуем, применив объектно-ориентированный подход. Объём кода при этом вырастет (объём этого материала также вырастет, поэтому запаситесь терпением). Программа станет более структурированной и расширяемой, а не просто лапшой из строчек кода.
Чтение символов из строки
Разбирая математическое выражение, мы читаем его по одному символу, и сравниваем этот символ с одним из возможных вариантов – это цифра? это скобка? это операция? Кроме того, символ-цифра или символ-операция имеет смысл только тогда, когда его ждут.
- после числа или закрывающей скобки может быть только знак или закрывающая скобка
- после знака может быть только число или открывающая скобка
Иначе говоря, алгоритм может находиться в разных состояниях. Самое первое состояние это "после знака", то есть в начале строки мы ждём число или скобку, но не ждём знак. Поэтому мы напишем для каждого случая свой обработчик, а состояние будет выбирать те обработчики, которые ему подходят. Это позволит инкапсулировать логику разбора в отдельные классы.
Заодно сделаем класс, хранящий полное текущее состояние синтаксического анализатора. На Питоне:
Он инкапсулирует разбираемую строку (src), текущую позицию чтения из строки (pos), текущий приоритет (priority), максимальный приоритет (max_priority) и список разобранных элементов (parsed). Первичное состояние (mode) мы обозначим как 's_open'.
Обработчики
Так как все они будут работать примерно одинаково, то будут наследоваться от одного общего класса (ссылка):
Метод parse() получает на вход параметр state, то есть состояние со всеми его пирогами. Далее, пока позиция чтения не достигла конца строки, вызывается метод check() для текущего символа строки. Если метод отработал успешно, то мы запоминаем, что был успех (то есть обработчик вообще сработал), и переходим на следующий символ, снова вызывая check(). Если неуспешно, то текущий накопленный результат (value) добавляется в список разобранных элементов состояния (state.parsed) и метод возвращает успех/неуспех (result).
Все обработчики будут наследоваться от этого класса и использовать общий метод parse(), но конкретный метод check() будет у каждого свой. Напишем обработчик открывающей скобки:
Аналогично, закрывающей скобки:
Эти обработчики не создают данных, а только увеличивают или уменьшают базовый приоритет операций.
Теперь обработчик числа:
Он накапливает значение до тех пор, пока видит цифры. Как только появится не цифра, обработчик вернёт неуспех, но его накопленное значение попадёт в state.parsed.
И наконец, обработчик знака операции:
Он хранит у себя словарь (ops), где каждому знаку операции поставлен в соответствие приоритет. Словарь позволяет и искать знаки, и определять их приоритет. Если знак найден, его приоритет складывается с базовым приоритетом, а в накопленное значение (value) помещается список из пары элементов: знак и приоритет (char, priority). Этот обработчик также обновляет максимальный приоритет, если необходимо.
Состояния
Добавим логику смены состояний. Если состояние равно 's_open' (начальное), то возможны два обработчика: OpenHandler (открывающая скобка) или NumHandler (число), и т.д. Запишем эти правила в виде словаря:
's_open', 's_close', 's_num' и 's_op' – это названия состояний. Для каждого состояния задан список обработчиков, которые в нём возможны. Обработчики записаны в виде строчных идентификаторов 'h_open', 'h_num' и т.д. То есть, зная состояние, мы можем получить из словаря список индентификаторов обработчиков, а зная идентификатор обработчика, мы можем создать его через условие:
Я ранее писал про шаблон проектирования "Фабрика" для таких случаев, поэтому мы его и применим. Условия будут инкапсулированы в базовый класс Handler, а он станет фабрикой для получения конкретных обработчиков. Часть класса с дописанной фабрикой:
Далее, если какой-то из обработчиков вернул True, это значит, что он сработал и нужно установить новое состояние, базируясь на том, что это был за обработчик. Для этого делаем словарь, где каждому идентификатору обработчика ставится в соответствие идентификатор состояния:
Мы получили замкнутую систему: состояния порождают обработчики, а обработчики задают дальнейшие состояния.
Осталось этим всем воспользоваться. Перенесём словари состояний и код разбора (из прошлой части) внутрь класса State, чтобы окончательно всё инкапсулировать (ссылка):
Программный код настолько очистился, что для разбора состояния достаточно вызвать state.parse(). С помощью этого метода мы получим просто разобранное на части выражение, которое можно перевести в разные форматы: и в обратную польскую запись, и в другие. Поэтому для обратной польской записи сделаем отдельный класс:
У него статический метод build(), это значит, что нам не нужно создавать экземпляр класса через конструктор RPNBuilder(), а можно просто вызывать RPNBuilder.build(), передавая туда разобранный список элементов и максимальный приоритет. Это всё, что ему необходимо для работы. Максимальный приоритет можно было бы найти и самостоятельно, но раз он уже посчитан в состоянии, то я поленился.
Полный код доступен по ссылке.
Обработка ошибок
Если в первой части не было никакой обработки ошибок, то здесь она уже присутствует в некоторой степени за счёт того, что набор обработчиков для каждого состояния ограничен. Если ни один обработчик из набора не сработал – значит в строке находится не то, что ожидается, и поэтому на этом месте разбор прекращается. Нужно только добавить сообщение об ошибке. Также, количество открывающих и закрывающих скобок должно совпадать. Это легко определить по базовому приоритету состояния – если в конце разбора он не нулевой, значит скобки не совпадают.
Мутации
Список parsed, который хранится в объекте state, является результатом разбора выражения и передаётся в метод RPNBuilder.build(). В этом методе список изменяется – из него удаляются элементы. Соответственно меняется он и в объекте state. В зависимости от языка это может быть не так. В общем случае нам бы не хотелось, чтобы список parsed менялся, когда мы передаём его куда-то. Предлагаю вам пока разобраться с этим вопросом самостоятельно. Это общая тема мутабельных и немутабельных переменных, к которой мы в будущем вернёмся.
Ссылки по теме: Инкапсуляция, Наследование, Статические методы, Полиморфизм
Навигатор по каналу
