программистская задачка

[avva]

Коллега недавно предложил следующее задание, которое мне понравилось в качестве разминки:

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

На входе: строка типа "(2+2)*12" или 56-4*2 или -10^2 итд. Разрешаются скобки и операторы: унарные + и -, бинарные +,-,*,/,^ (возведение в степень). У бинарных операторов обычные уровни приоритета и левая ассоциация внутри уровня, т.е. 10-5-2 равно 3, а не 7. Разрешаются ненужные скобки "(3)". Если в вашем языке нет целочисленной степени, не надо ее имплементировать, можно обойти трюками (напр. в C/C++ перейти к плавающей точке, возвести в степень и округлить). Можно предположить, что все числа и результаты укладываются в размер целочисленного типа вашего языка, если есть такое ограничение. Запрещено использовать массивы, стеки, списки, динамически отведенную память непостоянного размера и другие способы иметь локально неограниченную память в контексте конкретного запуска конкретной функции. Ну и конечно пользоваться чем-то вроде eval() своего языка нельзя, нужно "честно" решить.

Я не утверждаю, что это какое-то особо глубокое или сложное задание, просто хороший способ тряхнуть стариной и элегантно организовать логику. Если вы хотите поучаствовать, присылайте код ссылками на https://pastebin.com/ или свой гитхаб или еще как угодно. Я добавлю ссылку на свое решение (на питоне) завтра вечером к этой записи.

P.S. Поясняю насчет рекурсии. Правила специально сформулированы так ("в контексте конкретного запуска конкретной функции"), что рекурсию МОЖНО использовать. Если вы можете обойтись без рекурсии (я специально не говорю, легко это или тяжело, можно или нельзя), то тоже хорошо, но и рекурсия разрешается.

Update: Спасибо за присланные решения, они все красивые и хорошие :) Мое решение: https://pastebin.com/J6mpMRb2 (исправлены два бага, спасибо комментаторам!).

Comments

[livelight]

А в той памяти, где хранится исходное выражение, шалить можно? :)

[avva.livejournal.com]

Это извращение мне в голову не приходило, но нет, нельзя :)

[livelight]

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

[(Anonymous)]

Т.е. стек, как структуру данных, использовать нельзя, но стек для вызова функций использовать можно?

[avva.livejournal.com]

Да.

[(Anonymous)]

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

Короче говоря, можно было просто попросить написать рекурсивный парсер.

[kaathewise.livejournal.com]

Тогда очень скучно, даже непонятно, в чем трудность.

Более того, это проще, чем на самом деле использовать свой стек, без рекурсии.

[dims12.livejournal.com]

Так рекурсию можно использовать?

[deep-econom.livejournal.com]

с рекурсией это самый первый вариант который мне предложил некоторый школьник )
говорит: а рекурсивно можно функции вызывать? )

[ordinary-joe-1.livejournal.com]

есть такой язык брейнфак. я даж в своё время на нем хело ворлд исполнил. было тяжело!

[xxxxx.livejournal.com]

пробежаться раз по строке и найти операцию с наименьшим приоритетом не защищённую скобками, из равных приоритетов выбирать правую. Вызваться рекурсивно вокруг неё и всё.

[(Anonymous)]

Программисты на не-си чешут в затылке. То есть как это? рекурсивные функции можно, а рекурсивные данные нельзя? Это ограничения не имеет никакого смысла вообще. Нет, ну мы умеем кодировать любые структуры данных функциями, конечно, но зачем?

[klvov.livejournal.com]

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

[avva.livejournal.com]

Можно. Написал апдейт специально об этом.

[avva.livejournal.com]

Смотря кому! Я думаю, что люди, которые скажем по долгу службы пишут парсеры, это задачу вообще во сне решат. Рекурсивную версию написать легко тем, кто когда-то уже решал такую рекурсивную задачу и помнит, а другим придется подумать. Есть свои тонкости; самый очевидный способ определить, что возвращает рекурсивный вызов, например, не работает (ну или только у меня не работает, может, это я такой тупой).

[avva.livejournal.com]

Условие сформулировано специально так, чтобы рекурсия в него укладывалась. Но я не хотел специально говорить "напишите рекурсивный парсер", потому что понять, что МОЖНО использовать рекурсию - это часть удовольствия от решения задачи. Не все такие продвинутые и крутые, как вы, аноним!

Кроме того, то, что задачу нельзя решить *без* рекурсии, не столь уж тривиально (да даже и неверно для некоторых видов ухищрений). Например, возьмем более простую задачу проверки правильной вложенности скобок, и более ничего. Понятно, что ее легко решить без рекурсии, просто держа в счетчике число открытых скобок. Формально говоря, это нерегулярный язык и конечный автомат его не может решить, но для решения конкретной задачи "написать код, который проверяет скобки в реальной строке реалистичной длины" это оказывается нерелевантно!

Может, и для более сложной задачи "вычислить выражение" найдется такое решение? А может, нет? Это то, о чем мне хотелось бы, чтобы решатель подумал сам, и решил для себя сам, а не получил от меня на тарелочке.

[avva.livejournal.com]

См. этот комментарий.

[dims12.livejournal.com]

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

[kaathewise.livejournal.com]

Ну как, естественный путь -- это завести две функции, evalSum и evalMul, которые возвращают значение и еще шарят текущее положение в замыкании (мерзкий питон не разрешает менять глобальные переменные, поэтому его нужно обернуть).

А если свой стек писать, то гораздо сложнее получится, состояние еще туда записывать, ну его :)

[a-konst.livejournal.com]

Использование рекурсии алгоритмически равносильно использованию стека, так что это разрешение очень странно.

[avva.livejournal.com]

См. этот комментарий.

[blainemono.livejournal.com]

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

[(Anonymous)]

Вот да, самый красивый подход. Только со степенью засада -- результат может не влезть на место исходного выражения, даже если использовать более плотную кодировку. Например, "9^9" (24 бита, скорее всего) даёт 29-битовое число.

[livelight]

Это если у нас random access строка. А если это stream - то не получится :)

[livelight]

Только для взятия степени. Остальные операции имеют длину результата не больше, чем длина записи исходного (под)выражения.