timtibilov / jetbrainstestcase

Test Case for JetBrains Internship 2020

Решение тестового задания стажировок 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>, являющееся результатом работы алгоритма.