Реализуйте на языке Си библиотеку calc, позволяющую вычислять значения арифметических выражений с четырьмя операциями, скобками и вызовами функций.
Все промежуточныые и конечные вычисления идут в типе double, гарантируется корректность всех промежуточных вычислений.
Пользователь библиотеки может добавлять в выражения функции из Си произвольной арности.
Вы можете ограничить арность сверху константой CALC_MAX_ARITY, но функции с трёмя аргументами поддержать обязательно.
Если на вход получено некорректное арифметическое выражение, библиотека должна сообщить о позиции в строке,
где возникла первая ошибка.
Далее реализуйте на языке Си консольное приложение ./calc-cli, обрабатывающее строчки некоторого файла по отдельности и выводящее результат обработки в другой файл.
Если строчка является корректным арифметическим выражением, результат обработки — результат вычисления с точностью до трёх знаков после запятой.
Если же произошла ошибка, требуется вывести её код и указание на символ, в котором произошла ошибка.
Разбор арифметического выражения должен работать за линейное время.
Можно считать, что установлена локаль C/POSIX или близкая к ним.
В частности, десятичная запятая — это точка, а число парсится или не парсится однозначно.
Гарантируется, что все числа на входе помещаются в тип double.
Гарантируется, что на вход библиотеке подаются только символы с кодами от 1 от 127.
В частности, вы можете использовать стандартные функции isdigit, isalpha, isspace.
Между соседними элементами выражения, а также в начале и в конце выражения может идти произвольное количество пробельных символов (isspace).
Пробельные символы не могут встречаться внутри чисел или имён функций.
Вот приблизительная LL-грамматика арифметического выражения:
- Выражение
<expr-1>— это последовательность из хотя бы одного<expr-2>, разделённая+и-(операции левоассоциативны). - Выражение
<expr-2>— это последовательность из хотя бы одного<atom>, разделённая*и/(операции левоассоциативны). <atom>— это одно из:(, за которой следует выражение<expr-1>, за которым следует).- Число
<number> - Вызов функции, состоящий из имени функции
<function-name>,(, аргументов функции<expr-1>, разделённых,, и завершающей). Аргументов может быть ноль или больше.
- Число
<number>начинается либо с цифры, либо с+, либо с-, либо с.. Для разбора числа используйте функции из стандартной библиотеки. <function-name>— это последовательность из хотя бы одного латинского символа (isalpha).
- Вы уже писали парсер арифметических выражений на алгоритмах: контест
200918_hse, задача 3D.- В этом задании наверняка будет проще написать метод рекурсивного спуска (recursive descent), потому что ему не требуется выделять динамический массив
под стэк операций.
Пример упрощённого парсера есть в файле
demo-parser.c.
- В этом задании наверняка будет проще написать метод рекурсивного спуска (recursive descent), потому что ему не требуется выделять динамический массив
под стэк операций.
Пример упрощённого парсера есть в файле
- Для использования функций из
<math.h>под Linux в языке Си иногда требуется явно прилинковать библиотекуm(сокращённо от math):-lm. ВCMakeLists.txtэто уже сделано. - Компилятор может требовать инициализации всех членов структуры при помощи
{}, даже если этот член — анонимныйunion. Это нормально, вы можете проинициализировать первый членunion(в том числе анонимного) при помощи тех же{}. Однако проинициализировать не-первый членunionтак нельзя:struct Foo { int a; union { int b; float c; }; } f = {1, {2}}; // a=1, b=2, c неактивен и активировать при помощи {} нельзя.
- Visual Studio считает, что anonymous union — нестандартное расширение языка и иногда выдаёт предупреждение
warning C4201: nonstandard extension used: nameless struct/union. Однако anonymous union (не struct!) поддерживается всеми стандартами C++ и стандартом C99, поэтому это предупреждение следует заглушить, если оно не по делу:#ifdef _MSC_VER // Код внутри #ifdef компилируется только на Visual Studio #pragma warning(push) // Сохранить текущие настройки предупреждений #pragma warning(disable : 4201) // Отключить C4201 #endif // Код, вызывающий предупреждение C4201 #ifdef _MSC_VER #pragma warning(pop) // Восстановить настройки предупреждений #endif
- Макросной магии в этом задании практически не требуется, максимум для задания констант.
- В частности, не надо пытаться эмулировать перегрузки по количеству аргументов в Си при помощи макросов. Это осуществимо, но не требуется.
Действуют стандартные требования; туда добавилось требование корректно компилироваться и работать в двух режимах: Debug и Release.
Также добавлено пояснение, что для языка Си не запускается clang-tidy, который поддерживает только C++.
Помимо этого, clang-tidy не запускается на файле calc.h (он должен быть совместим с Си) и отключены следующие проверки:
cppcoreguidelines-pro-type-union-access
- Вы должны проверять абсолютно все коды возврата всех функций, которые могут завершиться с ошибкой, кроме функций вывода на экран или в файл.
- При обработке ошибок запрещается копипастить код для освобождения ресурсов (даже если это простой
fclose). В C++ это делают деструкторы, в Си используйтеgoto.
Заголовочный файл calc.h должен корректно работать и в программах на Си, и в программах на C++.
Он предоставляет следующие сущности:
CALC_MAX_ARITY— целочисленная константа, максимальная поддерживаемая арность функций.calc_function— тип, из которого можно создать массив с определениями функций.- Должно быть можно проинициализировать значение этого типа при помощи следующего designated initializer:
{.name = "sqrt", .arity = 1, .func1 = sqrt} - Аналогично с
func1для функций другой арности естьfunc0,func2и так далее.
- Должно быть можно проинициализировать значение этого типа при помощи следующего designated initializer:
CALC_FUNCTIONS_SENTINEL— специальное значение типаcalc_function, обозначающее конец массива функций.- Семейство констант
CALC_ERROR_*(смотри описание ниже). calc_result— тип переменной, в которую библиотека может сохранить значение.- Внутри этого типа должно быть доступно минимум два поля:
valueс посчитанным значениемerror_positionс позицией, в которой произошла ошибка разбора выражения (смотри ниже).
- Тип должен занимать как можно меньше байт.
- Внутри этого типа должно быть доступно минимум два поля:
calc_evaluate(expr, res, functions)— функция с трёмя параметрами:expr— ASCIIZ-строка (строка в стиле Си, null-terminated string), содержащая арифметическое выражение.res— опциональный указатель на переменную типаcalc_result, в которую будет сохранён результат разбора выражения.functions— опциональный указатель на массив функций, доступных при вычислении выражения.- Функция должна возвращать код ошибки из семейства
CALC_ERROR_*.
- При подключении
calc.hв C++ функциюcalc_evaluateдолжно быть можно вызвать только с первыми двумя параметрами, параметрfunctionsдолжен установиться вnullptr.- При этом должна сохраниться возможность вызывать
calc_evaluateс трёмя параметрами. - И в языке Си, и в языке C++ должны проверяться типы параметров.
В частности, нельзя объявить в Си как
void calc_evaluate(). - В языки Си функция
calc_evaluateвсегда вызывается с тремя параметрами.
- При этом должна сохраниться возможность вызывать
- Если функции
calc_evaluateпередан нулевой параметрfunctions(либо явно, либо при вызове из C++ в двумя параметрами), то должны быть доступны следующие функции по умолчанию:sqrt,sin,cos,pow(из<math.h>).- Если передан ненулевой параметр, то эти функции недоступны.
- Гарантируется, что набор функций в ненулевом
functionsкорректен:- Завершается значением
CALC_FUNCTIONS_SENTINEL. - Все имена — корректные ASCIIZ-строки, различны, состоят только из латинских символов.
- В частности, перегрузок по количеству аргументов тоже нет.
- Функция ожидает ровно столько параметров типа
double, сколько указано вarity, и возвращаетdouble.
- Завершается значением
Если при разборе строки произошла ошибка, calc_evaluate обязана о ней сообщить, вернув
соответствующий код и указав на первый символ с ошибкой (возможно, \0 в конце строки, который не считается пробельным).
Возможны следующие ошибки:
| Код | Константа | Описание | Символ с ошибкой |
|---|---|---|---|
| 0 | CALC_ERROR_OK |
Ошибок нет | N/A |
| 1 | CALC_ERROR_BAD_NUMBER |
<number> корректно началось с цифры, +, - или ., но не является числом с точки зрения стандартной библиотеки |
Первый непробельный символ числа |
| 2 | CALC_ERROR_UNKNOWN_FUNCTION |
Функция с именем <function-name> не существует |
Первый символ после имени функции |
| 3 | CALC_ERROR_EXPECTED_OPEN_PAREN |
Ожидалась круглая скобка при вызове функции | Первый неожиданный непробельный символ |
| 4 | CALC_ERROR_EXPECTED_COMMA |
Ожидалась запятая при вызове функции | Первый неожиданный непробельный символ |
| 5 | CALC_ERROR_EXPECTED_CLOSE_PAREN |
Ожидалась закрывающая при вызове функции или разборе <atom> |
Первый неожиданный непробельный символ |
| 6 | CALC_ERROR_UNEXPECTED_CHAR |
Неожиданный символ при разборе <atom> |
Первый неожиданный непробельный символ |
| 7 | CALC_ERROR_EXTRA_INPUT |
Выражение разобрано, но после него остались непробельные символы | Первый неожиданный непробельный символ |
Это покрывает все возможные ошибки разбора выражения. Если вам кажется, что что-то не покрыто — напишите преподавателю.
Приложение запускается следующей командой:
./calc-cli ‹in-file› ‹out-file›
Дальше для каждой строчки in-file (включая неполную последнюю, при её наличии) в выходной файл выводится одно из:
- Значение вычисленного выражения — если выражение корректно.
- Используется набор функций по умолчанию.
- Выводить требуется в виде
xxx.yyyровно с трёмя знаками после запятой.- Гарантируется, что результатом не будут специальные значения из IEEE-754.
- Считаем, что округление в стандартной библиотеке везде одинаковое и нас устроит.
- Сообщение об ошибке из трёх строк — если выражение некорректно:
Error 5:, где5— код ошибки.- Два пробела и
<expr>— поданное на вход выражение. - Два пробела и
...^— последовательность из нескольких точек и одного символа^в конце, указывающая на символ выражения, где произошла ошибка.
Стандартный поток вывода и стандартный поток ошибок остаются пустыми.
Заранее известных ограничений на размер файла или максимальную глубину выражения нет. Вы можете считать, что глубины стэка вам хватит.
При возникновении следующих ошибок приложение обязано завершиться с кодом возврата 1 и выдать в стандартный поток ошибок соответствующее сообщение (формат важен).
| Ошибка | Пример сообщения | Комментарий |
|---|---|---|
| Аргументов не ровно два | Usage: ./calc-cli <input> <output> |
Вместо ./calc-cli выводите argv[0] |
| Не удалось открыть входной файл | Unable to open 'a.in' for reading |
|
| Не удалось открыть выходной файл | Unable to open 'a.out' for writing |
|
| Не удалось (пере)выделить буфер | Unable to allocate buffer |
|
| Ошибка при чтении из файла | Error while reading from the input |
Если возникла ошибка при вычислении выражения, это не является поводом завершить работу или вернуть 1.
Содержимое выходного файла остаётся не определено.
Это покрывает все возможные ошибки консольного приложения. Если вам кажется, что что-то не покрыто — напишите преподавателю.
Как и раньше, вы должны самостоятельно синхронизировать ветку
master в своём репозитории, создать новую ветку для задания и новый Pull Request.
- Задание оценивается в 10 баллов: 6 за корректность, 4 за стиль.
- Если не проходит хотя бы одна автопроверка или неверно назван PR, вы получаете ноль.
- Вы не можете получить за стиль больше баллов, чем за корректность.
Задание выдано 10 апреля 2021 (суббота) и будет обновлено не позднее 12 апреля 2021 (понедельник). Ниже в каждом случае указано московское время.
- Дедлайн сдачи: 22 апреля 2021 (четверг), 22:59.
- Если первая попытка сдачи достаточно разумна (на усмотрение принимающего),
то вы можете сделать ещё попытку исправлений.
- Дедлайн исправлений обговаривается индивидуально с проверяющим, в общем случае хотя бы пять суток.
- Предложение актуально даже если вы получили автоматический ноль за первую попытку.