?

Log in

No account? Create an account
программистская задачка - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

программистская задачка [мар. 20, 2018|07:22 pm]
Anatoly Vorobey
[Tags|, ]

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

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

На входе: строка типа "(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:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: livelight
2018-03-20 05:42 pm
А в той памяти, где хранится исходное выражение, шалить можно? :)
(Ответить) (Thread)
[User Picture]From: avva
2018-03-20 05:44 pm
Это извращение мне в голову не приходило, но нет, нельзя :)
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2018-03-20 05:49 pm
Т.е. стек, как структуру данных, использовать нельзя, но стек для вызова функций использовать можно?
(Ответить) (Thread)
[User Picture]From: avva
2018-03-20 05:53 pm
Да.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: ordinary_joe_1
2018-03-20 06:51 pm
есть такой язык брейнфак. я даж в своё время на нем хело ворлд исполнил. было тяжело!
(Ответить) (Thread)
[User Picture]From: ilya_dogolazky
2018-03-20 07:04 pm
пробежаться раз по строке и найти операцию с наименьшим приоритетом не защищённую скобками, из равных приоритетов выбирать правую. Вызваться рекурсивно вокруг неё и всё.
(Ответить) (Thread)
[User Picture]From: a_konst
2018-03-20 08:09 pm
Использование рекурсии алгоритмически равносильно использованию стека, так что это разрешение очень странно.
(Ответить) (Thread)
[User Picture]From: avva
2018-03-20 08:19 pm
(Ответить) (Parent) (Thread)
[User Picture]From: vissarion
2018-03-20 09:42 pm
можно и без рекурсии
если mystring = re.sub(bla, bla, mystring)
за создание новой строки не считается то

https://pastebin.com/tdNw5BB5

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

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



Edited at 2018-03-21 01:20 (UTC)
(Ответить) (Thread)
From: (Anonymous)
2018-03-21 04:17 am
Код подвисает на 2^(-1). На 2^-1, 2^--1 возвращает 1.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: gul_kiev
2018-03-20 10:45 pm
Из классических программистских задач мне нравится "напишите (на произвольном языке) программу, выводящую собственный исходный текст". С очевидными ограничениями: без чтения файлов и т.п.
(Ответить) (Thread)
From: (Anonymous)
2018-03-21 01:57 am
Ещё вариант: есть функция rand(), которая равновероятно возвращает целое от 0 до R–1. Написать функцию random(n), которая равновероятно возвращает целое от 0 до n–1, вызывая rand() в среднем минимально возможное число раз. Желательно получить элегантный код с доказательством оптимальности.
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2018-03-21 04:28 am
https://pastebin.com/0A5kArWf
(Ответить) (Thread)
[User Picture]From: avva
2018-03-21 11:40 pm
Вау, это круто. Мне очень понравилось. Я хотел сделать версию, где рекурсивный вызов возвращает только значение и больше ничего, но когда запутался с приоритетами, плюнул и сделал возвращение оставшейся строки тоже. А у вас получилось. Код для поиска места, где можно разбить, нелегко так сразу понять, но по-моему все работает. Спасибо!
(Ответить) (Parent) (Thread)
WTF? - (Анонимно) Развернуть
Re: WTF? - (Анонимно) Развернуть
WTF 2 - (Анонимно) Развернуть
Re: WTF 2 - (Анонимно) Развернуть
Re: WTF 2 - (Анонимно) Развернуть
[User Picture]From: elfadmin
2018-03-21 07:08 am
А 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
(Ответить) (Thread)
From: (Anonymous)
2018-03-21 09:03 am
> даже с картинками

Пожалуйста, не используйте формат JPEG для изображений, не являющихся фотографиями. Он для этого совершенно не приспособлен.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: amosk
2018-03-21 10:26 am
Если бы не было скобок, то можно было бы обойтись без рекурсии.
В этом случае резервируетя память O(n), где n - количество поддерживаемых операторов, т.е. константа. И потом в цикле можно реализовать преобразование инфиксного выражения в постфиксное с вычислением.

А со скобками - только рекурсивный нисходящий парсер, который слишком прост чтобы было интересно тратить на это время ))
(Ответить) (Thread)
[User Picture]From: litwak
2018-03-21 12:35 pm
(Ответить) (Thread)
From: (Anonymous)
2018-03-22 10:52 pm
1-1-1 = 1
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2018-03-21 04:40 pm
> Запрещено использовать массивы, стеки

Это лицемерие.
Любой вызов функции использует стек, в котором хранится "константное [в пределах функции] количество локальных переменных".
Соответственно, если разрешёно неконстатное количество вызовов функций, то де-факто разрешён стек неограниченного размера.
(Ответить) (Thread)
[User Picture]From: vlad_suh
2018-03-21 05:20 pm
Модифицировать исходную строку заменой тоже нельзя?
(Ответить) (Thread)
[User Picture]From: avva
2018-03-21 08:48 pm
Нет.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2018-03-21 08:21 pm
Анатолий, спасибо за Ваше решение.

Кажется, есть проблемы с лево-ассоциативностью: 1/1/2 валится с делением на ноль. В самом Питоне, скажем, 1/1/2==0, ну или 1.0/1/2 == 0.5.
(Ответить) (Thread)
[User Picture]From: avva
2018-03-21 08:42 pm
Спасибо! Фиксится заменой всех условий типа "if incoming_rank > 1" на >=.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2018-03-21 08:23 pm
evalexpr("-5+1") = -6, печаль.
(Ответить) (Thread)
[User Picture]From: avva
2018-03-21 08:48 pm
Спасибо! Фиксится заменой incoming_rank=1 на incoming_rank=2 в 8-й строке.

Сейчас заменю ссылку в посте на новый пастебин с учетом последних двух комментов.
(Ответить) (Parent) (Thread)
Страница 1 из 2
<<[1] [2] >>