Школа 21, Бассейн, интермишшен (четвертая неделя, понедельник)

tl;dr ¯\_(ツ)_/¯ day13 ¯\_(ツ)_/¯ 10/100, evalexpr – метод "рекурсивного" спуска без деревьев, работающий за `O(n)`, rush02 – о том, как читать stdin и не погореть.

Доброе утро.

С тринадцатым днём я смог полностью ощутить каково это – сдать задания без тестирования и даже без минимальной компиляции. Напомню, что как раз этот день прошел под девизом "запушить хоть что-то", так что десять баллов, как ни крути, больше, чем ноль.

Оказалось, что я забыл в рекурсивной функции передать все аргументы вниз. Одного хватит, ведь так? ¯\_(ツ)_/¯

Забавно было обнаружить эту же ошибку у других в ходе проверок. Вероятно так действуют на сознание указатели на функции – казалось бы, ну, вот, зачем тебе передавать указатель? Объяви функцию как нормальный человек и не парься. Но, к примеру, если твой код – "чистая" библиотека только бинарных деревьев, то, очевидно, она вынуждена принимать указатель на функцию для обхода дерева.

Я набросился на evalexpr и начал расписывать алгоритм преобразования выражения со скобками в бинарное дерево. Это заняло какое-то время, но зато получился красивый псевдокод. Единственной его проблемой было, что кое где нужно было перемещать ветки дерева и держать всегда связь на родительский элемент (то есть вверх), а реализовывать это очень не хотелось.

Однако оказалось, что часть с исследованием и поиском данных порой совершенно необходима в задании, и так я нашел великолепный алгоритм (https://www.strchr.com/expression_evaluator), что шел слева направо по строке и делил её прямо на месте на "сумманды" (по-русски, вероятно, "складываемые"; любые выражения стоящие между знаком плюса и минуса) и прыгал вниз для определения внутри суммандов "факторов" (по-русски, вероятно, "сомножаемых"; любых выражений стоящих между знаком умножения и деления) и, опять же, прыгал вниз для разделения факторов на "атомы", которые либо будут числом, либо сложным выражением. Так, например, можно было бы реализовать `sin()` или любую другую буквенную функцию, но я использовал это, естественно, только ради скобок.

Больше всего меня восхитило, что несмотря на раздутие стека вызовами функций, мы на самом деле линейно (`O(n)`) идём по строке всего один раз! Да, конечно, можно заявить, что для реализации инкремента (`++`) и декремента (`--`) придется попотеть и, в целом, постоянно нужно внимательно следить за порядком операций, но тем не менее это достижимо. И не надо парсить строку, не надо создавать ни дерева, ни стека, ни двух для операций и, вообще, линейную сложность сложно как-либо победить.

С групповым заданием казалось все очень просто – мы опять утвердили API, я взял на себя ввод, другой парень взял на себя основное мясо программы и третий – вывод. Отвлекусь и скажу, что первый не мог присутствовать в воскресенье, а второй, вообще, сначала предложил мне, чтобы мы все решили сами, а он просто прочел и понял, что происходит. Он просто очень хотел сделать калькулятор... Тем не менее, на следующий день он стал готов написать вывод.

В утвержденном мною же API мы оперировали массивом входных строк. Конечно, вы можете подумать, что такого сложного в чтении строки со ввода и я опять отвлекусь.

Я, вроде как, не рассказывал, что в большинстве заданий нам не разрешено ни одной функции из стандартных библиотек. Если мы выделяем память, нам, слава богу, разрешен `malloc`, если выделяем много, то и `free`. Если мы что-то должны вывести на экран, то нам доступен только системный вызов `write`, который, я замечу, принимает указатель на символ в памяти и длину вывода. То есть для вывода числа уже надо писать преобразовыватель. Я слышал, вы используете `cout`, `puts` или `printf`. Что ж, вы уволены, так как использование запрещённой функции в коде автоматически желает вашу оценку за день равной минус сорока двум.

Для ввода данных, естественно, есть системный вызов `read`, который вы обычно использовали для чтения файлов, но тут мы будем читать стандартный ввод. Теперь на секундочку `read` пишет данные в буфер, а векторов у нас нет, что значит мы вынуждены использовать буфер фиксированной длины. Далее ничего сложного – читаешь строку, находишь в ней символ перевода строки и читаешь следующую...

А что же если длина строки 666 символов, а буфер всего 13 байт шириной? Как ты запомнишь те данные, что уже были прочтены? И ладно бы уже прочтённые данные, как насчёт того куска, что идёт после символа перевода строки в прочтенном буфере? Умный и вдумчивый читатель заметит, что есть же `seek`, который позволяет переместить указатель ввода на нужное место, но он нам не разрешен (и я не знаю как он работает со стандартным вводом; наверняка, после прочтения память автоматически высвобождается).

Стало совершенно очевидна необходимость реализации односвязного списка данных ввода и дальнейшего его преобразования в массив строк. Это было даже ещё хуже, чем писать `tail`, но, ничего, у меня получилось. Правда код пришлось написать дважды, так как первая попытка делала просто полную поебень, содержала функцию на 75 строк, работала только один раз сразу после компиляции и, в целом, даже я перестал понимать, что я написал. Вторая попытка была чистой и гораздо легче читаемой, да и работала ровно как надо.

Не знаю сколько команд заморочились над этим и полагаю, что большинство просто установило себе огромный буфер для чтения в надежде, что данных передадут меньше, чем размер буфера...

Сегодня – проверки evalexpr. Первая у меня в 10:00 и я на нее опаздываю. Лучше закончу писать и буду шевелить ногами.