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

[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]

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

[(Anonymous)]

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

[avva.livejournal.com]

Да.

[ordinary-joe-1.livejournal.com]

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

[xxxxx.livejournal.com]

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

[a-konst.livejournal.com]

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

[avva.livejournal.com]

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

[vissarion.livejournal.com]

можно и без рекурсии
если mystring = re.sub(bla, bla, mystring)
за создание новой строки не считается то

https://pastebin.com/tdNw5BB5

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

можно только с массивом символов

[(Anonymous)]

Код подвисает на 2^(-1). На 2^-1, 2^--1 возвращает 1.

[(Anonymous)]

Выдаёт -1 вместо 0, как будто у + и ^ приоритеты совпадают.

[gul-kiev.livejournal.com]

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

[(Anonymous)]

Ещё вариант: есть функция rand(), которая равновероятно возвращает целое от 0 до R–1. Написать функцию random(n), которая равновероятно возвращает целое от 0 до n–1, вызывая rand() в среднем минимально возможное число раз. Желательно получить элегантный код с доказательством оптимальности.

[(Anonymous)]

https://pastebin.com/0A5kArWf

[avva.livejournal.com]

Вау, это круто. Мне очень понравилось. Я хотел сделать версию, где рекурсивный вызов возвращает только значение и больше ничего, но когда запутался с приоритетами, плюнул и сделал возвращение оставшейся строки тоже. А у вас получилось. Код для поиска места, где можно разбить, нелегко так сразу понять, но по-моему все работает. Спасибо!

[elfadmin.livejournal.com]

А expression tree можно? А то у меня готовый пример к моей библиотеке state machines, ( да, я знаю что грамматика конечным автоматом не описывается :-))
https://github.com/blitvin/fsm4java/tree/master/src/test/java/org/blitvin/statemachine/expressionparser и даже с картинками и описанием https://github.com/blitvin/fsm4java/blob/master/docs/expression_parser.md

[(Anonymous)]

> даже с картинками

Пожалуйста, не используйте формат JPEG для изображений, не являющихся фотографиями. Он для этого совершенно не приспособлен.

[amosk.livejournal.com]

Если бы не было скобок, то можно было бы обойтись без рекурсии.
В этом случае резервируетя память O(n), где n - количество поддерживаемых операторов, т.е. константа. И потом в цикле можно реализовать преобразование инфиксного выражения в постфиксное с вычислением.

А со скобками - только рекурсивный нисходящий парсер, который слишком прост чтобы было интересно тратить на это время ))

[litwak.livejournal.com]

На C
https://pastebin.com/YNz3mRgq

[(Anonymous)]

1-1-1 = 1

[(Anonymous)]

> Запрещено использовать массивы, стеки

Это лицемерие.
Любой вызов функции использует стек, в котором хранится "константное [в пределах функции] количество локальных переменных".
Соответственно, если разрешёно неконстатное количество вызовов функций, то де-факто разрешён стек неограниченного размера.

[vlad_suh]

Модифицировать исходную строку заменой тоже нельзя?

[avva.livejournal.com]

Нет.

[(Anonymous)]

Анатолий, спасибо за Ваше решение.

Кажется, есть проблемы с лево-ассоциативностью: 1/1/2 валится с делением на ноль. В самом Питоне, скажем, 1/1/2==0, ну или 1.0/1/2 == 0.5.

[avva.livejournal.com]

Спасибо! Фиксится заменой всех условий типа "if incoming_rank > 1" на >=.

[(Anonymous)]

evalexpr("-5+1") = -6, печаль.

[avva.livejournal.com]

Спасибо! Фиксится заменой incoming_rank=1 на incoming_rank=2 в 8-й строке.

Сейчас заменю ссылку в посте на новый пастебин с учетом последних двух комментов.

[(Anonymous)]

Мне не нравится, что у вас возведение в степень левоассоциативно, это противоречит общепринятым стандартам.
Вот вариант на C, который это обрабатывает правильно и при желании превращается в правоассоцивный тривиальной заменой 7 символов.
Он даже слегка попроще всех уже приведённых вариантов, заточенных под левую ассоциативность, и вроде без ошибок.

https://pastebin.com/y94RLZVZ

[(Anonymous)]

Пардон, "превращается в левоассоциативный" (сейчас там возведение в степень как раз правоассоциативно).

Интересную задачку я пропустил.

[son-0f-morning.livejournal.com]

>> используя только константное количество локальных переменных.

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

И тогда классическое: построим AST и вычислим (пусть даже через bison + yacc).

ПС
Ну с рекурсией совсем просто -- такая грамматика стековым автоматом разбирается. Наверное надо тряхнуть стариной и написать (естественно интерес представляет время, в 1ю очередь).
Но вот сейчас этого времени вроде как и нет.

[xyli0o.livejournal.com]

Спасибки за задачку
https://github.com/Alexander-Panin/calculator/blob/master/calculator.py

[(Anonymous)]

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

[zz-pten.livejournal.com]

Спасибо, очень интересно.

Объясните в двух словах, в чем смысл вычитания int('0') в 12-й и 14-й строках кода решения автора. Спасибо

[avva.livejournal.com]

Ахаха :)

Нет никакого смысла, это у меня, видимо, был мгновенный глюк и я машинально написал то, что всегда пишут в таких случаях в C/C++. Если бы int(c) было ASCII-кодом цифры c, а не самой цифрой, то это вычитание было бы нужным. А так оно ничего не делает. Спасибо, что заметили!