Skip to content

Latest commit

 

History

History
82 lines (63 loc) · 7.28 KB

README.md

File metadata and controls

82 lines (63 loc) · 7.28 KB

Преобразователь

Способы опробовать

Можно прямо сейчас по ссылке, а можно локально:

  1. Склонировать репозиторий: git clone https://github.com/cromtus/jb-preinternship-2020-callchain.git
  2. Скомпилировать в исполняемый jar: ./gradlew jar и запустить собранный jar: java -jar build/libs/callchain.jar.

или

  1. Вместо предыдущего запустить ./gradlew run.

или

  1. Вместо предыдущего запустить Идею и в src/main/kotlin/Main.kt нажать зелёный треугольник рядом с методом main :)

Комментарии

Цепочка вызовов, подаваемая на вход, транслируется во внутреннее представление (Model из пакета structures) при помощи функции из пакета parser. Во время парсинга может выброситься SyntaxError или TypeError. По идее, никаких других исключений парсер выбрасывать не может (если только все константные выражения помещаются в Int).

Внутреннее представление допускает несоответствие типов (например, можно подставить булево выражение в map), поскольку это допускает грамматика из условия задачи. Как уже было сказано, проверку типов делает парсер.

Для тестирования также создан пакет applicator, который умеет применять цепочку вызовов из Model к заданному массиву. Он тоже делает проверку типов, но выбрасывает RuntimeException. Если Model создана парсером, RuntimeException невозможен.

Узкие места. Константные выражения хранятся в типе Int, вычисления applicator выполняет в нём же. Также не реализовано упрощение выражений. Все числовые выражения в данной грамматике — многочлены, поэтому, можно было бы, например, упрощать сравнения линейных функций (2 * x + 4 < x + 4 заменять на x < 0) и квадратичных (x * x - 2 * x + 1 > -3 заменять на 1 = 1). А на основе уже имеющегося кода можно было бы сделать вычисление константных выражений ((2+2) заменять на 4). Ещё в онлайн-демонстрации проблемы с русскими буквами: вместо SyntaxError будет MalformedInputException. Локально же всё работает хорошо.

Условие задачи

Язык описания операций над целочисленными массивами задан следующей грамматикой:

<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>

Арифметические операции имеют стандартную семантику. Операция “&” это логическое “и”, операция “|” --- логическое “или“. Бинарные выражения с операторам “&”, “|” , “=”, “>”, “<” имеют булевый тип, а с операторами “+”, “-”, “*” --- арифметический. Операнды арифметических операций должны иметь целочисленный тип, а операнды логических --- булевый. Вызов функции map заменяет каждый элемент массива на результат вычисления переданного арифметического выражения, в котором вместо element подставляется значение текущего элемента. Вызов функции filter оставляет в массиве только элементы, для которых переданное выражение истинно.

Последовательность вызовов применяется к массиву по очереди, слева направо.

Необходимо написать преобразователь выражений описываемых правилом <call-chain> в выражения вида <filter-call> “%>%” <map-call>, эквивалентные исходному. Решение должно принимать на стандартный поток ввода одну строку --- выражение описываемое правилом <call-chain> и выводить строку с преобразованным выражением. В случае наличия синтаксической ошибки, решение должно вывести SYNTAX ERROR, а если тип выражения не совпадает c ожидаемым TYPE ERROR.

Дополнительно, к решению предъявляются следующие требования:

  • решение должно быть выполнено на языке Java или Kotlin;
  • решение должно быть оформлено в виде публичного git репозитория;
  • код должен быть хорошо структурирован;
  • решение должно включать в себя тесты;

Бонус:

  • решение производит упрощение выражений;

Примеры ниже содержат один из корректных вариантов преобразования, ваш вариант не обязан совпадать с предложенным. Примеры:

In:
filter{(element>10)}%>%filter{(element<20)}
Out:
filter{(element>10)&(element<20)}%>%map{element}

In:
map{(element+10)}%>%filter{(element>10)}%>%map{(element*element)}
Out:
filter{((element+10)>10)}%>%map{((element+10)*(element+10))}

In:
map{(element+10)}%>%filter{(element>10)}%>%map{(element*element)}
Out:
filter{(element>0)}%>%map{((element*element)+((element*20)+100))}

In:
filter{(element>0)}%>%filter{(element<0)}%>%map{(element*element)
Out:
filter{(1=0)}%>%map{element}