J

Мова програмування J, створена на початку 1990-х років Кеннетом Іверсоном та Роджером Хуї, є синтезом APL (також розробленої Іверсоном) та мов функціонального рівня FP і FL, створених Джоном Бекусом.

Вікіпедія. J (мова програмування)

Сімейство мов APL відоме своєю підтримкою розширених операцій над векторами та масивами, і J не є винятком. Наприклад, всі унарні та бінарні числові операції в цих мовах за замовчуванням застосовуються до векторів та масивів різних розмірностей. Операція додавання ('+') може додавати не лише скаляри, як в інших мовах, але й скаляри до векторів (скаляр додається до кожного елемента вектора), або вектори до векторів (вектори додаються поелементно).

Виразна сила J вражає (як і його загадковий синтаксис), але для цієї задачі нам потрібна лише невелика підмножина мови. Ми розглядаємо один вираз, де можемо використовувати одну векторну змінну $X$, одну скалярну змінну $N$ - довжину вектора $X$, і наступні операції:

• Ми можемо додавати (+), віднімати (-) або множити (*) два вектори, вектор і скаляр, або два скаляри.

• Ми можемо використовувати унарний мінус (-) і унарну операцію зведення в квадрат (*:) для скалярів і векторів (поелементно).

• Ми можемо згортати вектор з операцією додавання ('+/') - тобто обчислювати суму вектора (унарна операція).

Операції обчислюються справа наліво, природний пріоритет операцій в J ігнорується. Порядок обчислення може бути змінений за допомогою дужок. Більш точно синтаксис визначається в наступному BNF.

<вираз> ::= <терм> | <терм> (' + ' | ' - ' | ' * ') <вираз> | ('-' | '*:' | '+/') <вираз>

<терм> ::= '('<вираз>')' | 'X' | 'N' | <число>

<число> ::= ('0' | '1' | . . . | '9')+

Щоб правильно накласти ще одне обмеження на синтаксис виразу, давайте визначимо складність виразу:

• складність скалярів (чисел, $N$, і результату згортки) дорівнює нулю;

• складність $X$ дорівнює одиниці;

• складність додавання та віднімання дорівнює максимуму складностей їх операндів;

• складність множення дорівнює сумі складностей його операндів;

• складність унарного зведення в квадрат дорівнює подвоєній складності його операнда.

Наприклад, складність виразу "(3-+/*:*:X)-X**:X" дорівнює $3$, тоді як складність його підвиразу "*:*:X" дорівнює $4$.

Ваша програма отримує вираз, що повертає скаляр, і значення вектора $X$, і повинна обчислити результат виразу за модулем 10^9. Складність кожного підвиразу у даному виразі не перевищує $10$.