Рекурсия для мат. выражения

  • 14
  • Недоступна
На вход подается строка - математическое выражение. Выражение включает целые и дробные числа, скобки (), пробелы, знак отрицания -, возведение в степень ^, sin(x), cos(x), tan(x) Для sin(x), cos(x), tan(x) выражение внутри скобок считать градусами, например, cos(3 + 19*3)=0.5 Степень задается так: a
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (160)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
null
Уровень 34, Москва
undefined, 17:13
Лучшие три дня в моей жизни.. Потратил три дня - оказалось, что на >=15 джаве не работает движок нашорн. Соответственно, весь мой код в мусорку(
Артем Инженер по автоматизации в YOKOGAWA
16 октября, 18:16
Задача супер. Рекомендую к решению. Я все нервы истрепал на том, что не подразумевал пробелов в выражениях. Так что рекомендую в вашем алгоритме удалить все пробелы из входной строки.
Yury Korziuk
Уровень 33, Минск, Беларусь
15 сентября, 20:45
Обратная польская нотация рулит. 180 строк говнокода получилось, дебаг 90% времени. Спасибо всем кто выкладывал тестовые примеры, без них было бы 900 проверок, а так только одна. 1756 - решили ... про обратную польскую нотацию
Maks Panteleev
Уровень 41, Москва, Россия
10 июля, 13:41
Как решал: регуляркой искал все вложенные выражения в скобках и по очереди отправлял их на расчет, раскрывая скобки в изначальном выражении путем замены на результат вычислений. У меня было несколько блоков с условиями - первый для раскрытия скобок, второй для подсчета синусов, третий для вычислений без скобок. Ну и последний блок отправлял ответ если считать было нечего. создал 4 вспомогательных метода: 1) public String function(String expression){} эта штука считает синусы косинусы и тангенсы. Мы туда закидываем выражение, регуляркой достаем из него все косинуы синусы и тд, разбиваем их на название функции и ее значение - по первому параметру определяем каким методом считать, по второму - что именно считать) результат возвращаем и заменяем им все синусы в исходном выражении) 2) public int operator(List<String> list, int countOperation) {} тут просто 5 мат операций - +-*/^ - в цикле while в порядке приоритета в переданном выражении (выражение передается через список чисел и операций) мы для каждой операции вызываем следующий метод public int calculate(List<String> list, String operation, int countOperation) {} тут банальные расчеты
4) public List<String> reList() {}
вот это пожалуй самый сложный важный и интересный метод) в нем мы берем выражение которое нашла регулярка в начале, превращаем в массив символов и проходимся по нему циклом. Смысл в том чтоб из массива [8,7,+,43] получить список [87,+,43]. То есть тут мы отделяем знаки и мат операции от чисел. А в предыдущем методе считаем уже на основе такого разделения. то есть [87,+,43] тут ищем плюс, если находим, то складываем число ПЕРЕД плюсом и ПОСЛЕ плюса) тут даже так)
if ((c >= '0' && c <= '9') || c == '.' || chars[0] == '-' || (chars[i] == '-' && String.valueOf(chars[i-1]).matches("[\\(\\+\\-\\*\\\\^]")))
<
Maks Panteleev
Уровень 41, Москва, Россия
10 июля, 13:37
Фух, короче, возился с задачей 4 дня. Да, видел видос по решению такой задачи через лексемы, но остановил его в начале и принципиально решил попробовать пободаться с задачей сам. Задача крутая, сложная, интересная. Пока что самая сложная задача на курсе. Она требует отличного понимания регулярок, рекурсии и алгоритмов. Сразу скажу - мое решение не проходит валидацию - там есть лишние поля, там некоректно счетчик операций, не на каждую операцию прикручено округлению и иногда оно может выдавать некорректный результат, но в большинстве проверок оно справляется) Пробовал разной сложности. Да, решение не самое лучшее, но зато я сам разобрался и очень этому рад) эти 4 дня были полны боли и страданий, но не лишены приятного))
Alexander Kusakin
Уровень 41, Astrakhan
4 июня, 19:47
Поскольку рекурсивная функция имеет тип void и нельзя в косвенную рекурсию, сделал последовательным упрощением: вычисляем значение в самых глубоких скобках (также последовательно упрощая: сначала тригонометрические функции, потом степени, умножение/деление, сложение/вычитание), затем подставляем вычисленное значение в выражение вместо скобок и вызываем функцию рекурсивно для упрощённого выражения, пока не получим выражение без скобок, тогда вычисляем его по вышеуказанному алгоритму. Не совсем удачная задача для изучения рекурсии - такую рекурсию легко можно было бы заменить циклом,
Anonymous #2491313
Уровень 35
3 апреля, 18:47
Уф. Сделал. 155 строчек. Потратил часов 12. Но валидацию не проходит, как по ответу, так и по рекурсивности. Хотя все тесты, что нашел здесь - прошли. Когда начинал вообще не знал даже с какой стороны подойти. В процессе несколько раз полностью переделывал.
Anonymous #2491313
Уровень 35
3 апреля, 16:51
Не совсем понятно как countOperation и результат возвращать рекурсивно.
Flexo Bending Unit #3370318
20 марта, 09:30
Медиум? Да ну нафик! Оставлю-ка на потом, 5-я задача, которую уже так оставил...
Анатолий
Уровень 41
10 марта, 19:19
Задача прошла проверку только после того как на каждом этапе вычисления результат округлялся до двух знаков после запятой! А не только в конце на выводе... Форматирование, чтобы точки вместо запятых ставило, и округляло правильно до 2 знаков:
//Выставляем правильное форматирование
        DecimalFormat df = new DecimalFormat("#.##");
        DecimalFormatSymbols dfs = df.getDecimalFormatSymbols();
        dfs.setDecimalSeparator('.');
        df.setDecimalFormatSymbols(dfs);
        Double doubleResult = 1.3333333;
        String output = df.format(doubleResult);
Примеры на которых я тренировал волю 😅
solution.recurse("sin(2*(-5+1.5*4)+28)", 0); //expected output 0.5 6
solution.recurse("tan(2025 ^ 0.5)", 0); //expected output 1 2
solution.recurse("1+(1+(1+1)*(1+1))*(1+1)+1", 0);  // 12 8
solution.recurse("-2^(-2)",0);  // 0.25 3
solution.recurse("-(-2^(-2))+2+(-(-2^(-2)))",0); // 1.5 10
solution.recurse("(-2)*(-2)",0); // 4 3
solution.recurse("(-2)/(-2)",0); // 1 3
solution.recurse("sin(-30)",0); // -0.5 2
solution.recurse("cos(-30)",0); // 0.87 2
solution.recurse("tan(-30)",0); // -0.58 2
solution.recurse("2+8*(9/4-1.5)^(1+1)",0); // 6.48 6
solution.recurse("tan(44+sin(89-cos(180)^2))",0); // 1 6
solution.recurse("-cos(180)^2",0); // -1 3
solution.recurse("0+0.304",0); // 0.3 1
И вот ещё проверки. Всего эту задачу решили 1394 учеников.
Mark
Уровень 34, Москва, Россия
29 августа, 16:37
Спасибо, помогли ваши проверки. Только в двух примерах, скорее такие ответы: solution.recurse("-2^(-2)",0); // -0.25 3 solution.recurse("-(-2^(-2))+2+(-(-2^(-2)))",0); // 2.5 10
Shamil
Уровень 36, Россия
13 сентября, 17:13
объясните, пожалуйста, почему tan(-45) и другие тригонометрические выражения должны считаться как две операции?