Решение тестового задания стажировок JetBrains 2020 реализовал студент 2 курса бакалавриата ОП "Программная инженерия" факультета компьютерных наук НИУ ВШЭ Тибилов Таймураз.
Язык описания операций над целочисленными массивами задан следующей грамматикой:
<digit> ::= “0” | “1" | “2” | “3" | “4” | “5" | “6” | “7" | “8” | “9"
<number> ::= <digit> | <digit> <number>
<operation> ::= “+” | “-” | “*” | “>” | “<” | “=” | “&” | “|”
<constant-expression> ::= “-” <number> | <number>
<binary-expression> ::= “(” <expression> <operation> <expression> “)”
<expression> ::= “element” | <constant-expression> | <binary-expression>
<map-call> ::= “map{” <expression> “}”
<filter-call> ::= “filter{” <expression> “}”
<call> ::= <map-call> | <filter-call>
<call-chain> ::= <call> | <call> “%>%” <call-chain>
Необходимо написать преобразователь выражений описываемых правилом <call-chain>
в выражения вида
<filter-call> “%>%” <map-call>
, эквивалентные исходному.
Полученное на вход выражение <call-chain>
разбивается на подвыражения <call>
через разделитель %>%
.
Далее для каждого <call>
строится абстрактное синтаксическое дерево. Во время построения дерева
также проверяется соответствие типа операндов типам операторов, а также типа возвращаемых
значений соответствующим выражениям <filter-call>
и <map-call>
. В случае возникновения ошибки
парсинга или несоответствия типов будет создано соответствующее исключение.
Важно отметить -- при парсинге токенов пропуск пробельных символов не производится (хотя функциональная часть для этого
реализована). Во время построения также запоминаются все узлы, представляющие собой
“element”
для реализации слияний деревьев и их объединения.
После получения всех деревьев происходит их "слияние" и получение одного <filter-call>
и одного <map-call>
по следующим правилам:
- Узлы типа
“element”
для каждого последующего выражения типа<filter-call>
и<map-call>
заменяются на корневой узел последнего предшествующего выражения типа<map-call>
- Выражения типа
<filter-call>
последовательно объединяются в новое выражение вида<filter-call>
с<expression>
, являющимся объединением<expression>
-ов переданных<filter-call>
через операцию"&"
(логическоеИ
).
Затем с помощью рекурсивных вызовов строется конечное выражение вида
<filter-call> “%>%” <map-call>
, являющееся результатом работы алгоритма.