Парсеры

Языки

Java
JavaScript
Clojure
Prolog

Java

Задание

Разработайте классы Const, Variable, Add, Subtract, Multiply, Divide для вычисления выражений с одной переменной в типе int. Классы должны позволять составлять выражения вида

  new Subtract(
    new Multiply(
        new Const(2),
        new Variable("x")
    ),
    new Const(3)
).evaluate(5)

При вычислении такого выражения вместо каждой переменной подставляется значение, переданное в качестве параметра методу evaluate (на данном этапе имена переменных игнорируются). Таким образом, результатом вычисления приведенного примера должно стать число 7.

Метод toString должен выдавать запись выражения в полноскобочной форме. Например

  new Subtract(
    new Multiply(
        new Const(2),
        new Variable("x")
    ),
    new Const(3)
).toString()

должен выдавать ((2 * x) - 3).

Реализуйте метод equals, проверяющий, что два выражения совпадают. Например,

  new Multiply(new Const(2), new Variable("x"))
    .equals(new Multiply(new Const(2), new Variable("x")))

должно выдавать true, а

  new Multiply(new Const(2), new Variable("x"))
    .equals(new Multiply(new Variable("x"), new Const(2)))

должно выдавать false. Для тестирования программы должен быть создан класс Main, который вычисляет значение выражения x2−2x+1, для x, заданного в командной строке.

При выполнении задания следует обратить внимание на:

Выделение общего интерфейса создаваемых классов.

Выделение абстрактного базового класса для бинарных операций.

Доработайте предыдущее домашнее задание, так что бы выражение строилось по записи вида x * (x - 2)*x + 1 В записи выражения могут встречаться:

умножение *,
деление /,
сложение +,
вычитание -,
унарный минус -,
целочисленные константы (в десятичной системе счисления, которые помещаются в 32-битный знаковый целочисленный тип), круглые скобки, переменные (x) и произвольное число пробельных символов в любом месте (но не внутри констант).

Приоритет операторов, начиная с наивысшего

унарный минус;
умножение и деление;
сложение и вычитание. Разбор выражений рекомендуется производить методом рекурсивного спуска. Алгоритм должен работать за линейное время.

Добавьте в программу вычисляющую выражения обработку ошибок, в том числе:

ошибки разбора выражений;
ошибки вычисления выражений. Для выражения 1000000xxxx*x/(x-1) вывод программы должен иметь следующий вид:

x       f
0       0
1       division by zero
2       32000000
3       121500000
4       341333333
5       overflow
6       overflow
7       overflow
8       overflow
9       overflow
10      overflow

Результат division by zero (overflow) означает, что в процессе вычисления произошло деление на ноль (переполнение).

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

Человеко-читаемые сообщения об ошибках должны выводится на консоль.

Программа не должна «вылетать» с исключениями (как стандартными, так и добавленными).

Добавьте в программу разбирающую и вычисляющую выражения трех переменных поддержку вычисления в различных типах.

Создайте класс expression.generic.GenericTabulator, реализующий интерфейс expression.generic.Tabulator:

public interface Tabulator {
    Object[][][] tabulate(String mode, String expression, int x1, int x2, int y1, int y2, int z1, int z2) throws Exception;
}

Аргументы

mode — режим работы

Режим Тип

i int (с детекцией переполнений)

d double

bi BigInteger
expression — вычисляемое выражение;
x1, x2; y1, y2; z1, z2 — диапазоны изменения переменны (включительно). Возвращаемое значение — таблица значений функции, где R[i][j][k] соответствует x = x1 + i, y = y1 + j, z = z1 + k. Если вычисление завершилось ошибкой, в соответствующей ячейке должен быть null.

Режим	Тип
i	int (с детекцией переполнений)
d	double
bi	BigInteger

Реализация не должна содержать непроверяемых преобразований типов.

Реализация не должна использовать аннотацию @SuppressWarnings.

При выполнении задания следует обратить внимание на простоту добавления новых типов и операциий.

Модификация

Uls
- Дополнительно реализовать поддержку режимов:
  - u – вычисления в int без проверки на переполнение;
  - l – вычисления в long без проверки на переполнение;
  - s – вычисления в short без проверки на переполнение.
- Исходный код тестов
AsmUls
- Реализовать режимы из модификации Uls.
- Дополнительно реализовать унарные операции:
  - abs – модуль числа, abs -5 равно 5;
  - square – возведение в квадрат, square 5 равно 25.
- Дополнительно реализовать бинарную операцию (максимальный приоритет):
  - mod – взятие по модулю, приоритет как у умножения (1 + 5 mod 3 равно 1 + (5 mod 3) равно 3).
- Исходный код тестов

JavaScript

Задание

Разработайте классы Const, Variable, Add, Subtract, Multiply, Divide, Negate для представления выражений с одной переменной. Пример описания выражения 2x-3:

let expr = new Subtract(
    new Multiply(
        new Const(2),
        new Variable("x")
    ),
    new Const(3)
);

println(expr.evaluate(5));

При вычислении такого выражения вместо каждой переменной подставляется её значение, переданное в качестве аргумента метода evaluate. Таким образом, результатом вычисления приведенного примера должно стать число 7.

Метод toString() должен выдавать запись выражения в обратной польской записи. Например, expr.toString() должен выдавать «2 x * 3 -».
Метод diff("x") должен возвращать выражение, представляющее производную исходного выражения по переменной x. Например, expr.diff("x") должен возвращать выражение, эквивалентное new Const(2) (выражения new Subtract(new Const(2), new Const(0)) и

new Subtract(
    new Add(
        new Multiply(new Const(0), new Variable("x")),
        new Multiply(new Const(2), new Const(1))
    )
    new Const(0)
)

так же будут считаться правильным ответом). Функция parse должна выдавать разобранное объектное выражение.

Добавьте в предыдущее домашнее задание функцию parsePrefix(string), разбирающую выражения, задаваемые записью вида «(- (* 2 x) 3)». Если разбираемое выражение некорректно, метод parsePrefix должен бросать человеко-читаемое сообщение об ошибке. Добавьте в предыдущее домашнее задание метод prefix(), выдающий выражение в формате, ожидаемом функцией parsePrefix.

При выполнение задания следует обратить внимание на:

Применение инкапсуляции.

Выделение общего кода для операций.

Минимизацию необходимой памяти.

Обработку ошибок.

Модификация

Cube. Дополнительно реализовать поддержку:
- унарных функций:
  - Cube (cube) – возведение в куб, 3 cube равно 27;
  - Cbrt (cbrt) – извлечение кубического корня, -27 cbrt равно −3;
Postfix: SumsqLength. Дополнительно реализовать поддержку:
- выражений в постфиксной записи: (2 3 +) равно 5
- операций произвольного числа аргументов:
  - Sumsq (sumsq) – сумма квадратов, (1 2 3 sumsq) равно 14;
  - Length (lengthу) – длина вектора, (3 4 length) равно 5;
- Исходный код тестов

Clojure

Задание

Разработайте конструкторы Constant, Variable, Add, Subtract, Multiply и Divide для представления выражений с одной переменной. Пример описания выражения 2x-3:

(def expr
  (Subtract
    (Multiply
      (Constant 2)
      (Variable "x"))
    (Constant 3)))

Функция (evaluate expression vars) должна производить вычисление выражения expression для значений переменных, заданных отображением vars. Например, (evaluate expr {"x" 2}) должно быть равно 1.
Функция (toString expression) должна выдавать запись выражения в стандартной для Clojure форме.
Функция (parseObject "expression") должна разбирать выражения, записанные в стандартной для Clojure форме. Например, (parseObject "(- (* 2 x) 3)") должно быть эквивалентно expr.
Функция (diff expression "variable") должена возвращать выражение, представляющее производную исходного выражения по заданой пермененной. Например, (diff expression "x") должен возвращать выражение, эквивалентное (Constant 2), при этом выражения (Subtract (Constant 2) (Constant 0)) и

(Subtract
  (Add
    (Multiply (Constant 0) (Variable "x"))
    (Multiply (Constant 2) (Constant 1)))
  (Constant 0))

так же будут считаться правильным ответом. Констуркторы Add, Subtract, Multiply и Divide должны принимать произвольное число аргументов. Разборщик так же должен допускать произвольное число аргументов для +, -, *, /. При выполнение задания можно использовать любой способ преставления объектов.

Реализуйте функцию (parseObjectInfix "expression"), разбирающую выражения, записанные в инфиксной форме, и функцию toStringInfix, возвращающую строковое представление выражения в этой форме. Например,

(toStringInfix (parseObjectInfix "2 * x - 3"))

должно возвращать ((2 * x) - 3). Функции разбора должны базироваться на библиотеке комбинаторов, разработанной на лекции.

Модификация

SumAvg. Дополнительно реализовать поддержку:
- операций произвольного числа аргументов:
  - Sum (sum) – сумма, (sum 1 2 3) равно 6;
  - Avg (avg) – арифметическое среднее, (avg 1 2 3) равно 2;
Variables. Дополнительно реализовать поддержку:
- Переменных, состоящих из произвольного количества букв XYZ в любом регистре
  - Настоящее имя переменной определяется первой буквой ее имени
PowLog. Сделать модификацию Variables и дополнительно реализовать поддержку:
- Бинарных правоассоциативных операций максимального приоритета:
  - IPow (**) – возведения в степень: 4 ** 3 ** 2 равно 4 ** (3 ** 2) равно 262144
  - ILog (//) – взятия логарифма: 8 // 9 // 3 равно 8 // (9 // 3) равно 3

Prolog

Задание

Доработайте правило (evaluate Expression Varsiables Result), вычисляющее арифметические выражения. Пример вычисления выражения 2x-3 для x = 5:

eval(
    operation(op_subtract,
        operation(op_multiply,
            const(2),
            variable(x)
        ),
        const(3)
    ),
    [(x, 5)],
    7
)

Поддерживаемые операции:

сложение (op_add, +),
вычитание (op_subtract, -),
умножение (op_multiply, *),
деление (op_divide, /),
противоположное число (op_negate, negate). Реализуйте правило (infix_str Expression Atom), разбирающее/выводящее выражения, записанные в полноскобочной инфиксной форме. Например,

infix_str(
    operation(op_subtract,operation(op_multiply,const(2),variable(x)),const(3)),
    '((2 * x) - 3)'
)

Правила должны быть реализованы с применением DC-грамматик.

Модификация

VarSinhCosh (36-37). Сделать модификацию Variables и дополнительно реализовать поддержку:
- унарных операций:
  - op_sinh (sinh) – гиперболический синус, sinh(3) немного больше 10;
  - op_cosh (cosh) – гиперболический косинус, cosh(3) немного меньше 10.

Ilya-Sib/expression-parsers

Парсеры

Языки

Java

Задание

Модификация

JavaScript

Задание

Модификация

Clojure

Задание

Модификация

Prolog

Задание

Модификация