Обход ошибки анализа этого калькулятора
Контекст:
Я ввел выражение 3.24 * 10^10 + 1 в созданный мною калькулятор.
Подход моего калькулятора к решению этой проблемы заключается в следующем: сначала он ищет шаблон number_a^number_b, анализирует 2 числа на двойные с помощью метода Double.parseDouble(), затем выполняет Math.pow(number_a, number_b) и заменяет выражение результатом.
Калькулятор аналогичным образом ищет шаблон number_a * number_b и анализирует его. Пока что наше выражение становится 3.24E10 + 1. А теперь самое сложное. Когда я программировал этот калькулятор, я думал, что калькулятор должен найти шаблон number_a + number_b и проанализировать его. Мой калькулятор действительно делает это и возвращает результат как неожиданно, но оправданно - 3.24E11.0.
Я ищу обходной путь, чтобы сделать мой калькулятор достаточно умным, чтобы обрабатывать такие выражения.
Важная информация - Пример регулярного выражения = ([\\d\\.]+)\\*([\\d\\.]+)
Пример кода -
// here 'expression' is a StringBuilder type
// only a (modified) snippet of actual code.
Matcher m = Pattern.compile ("([\\d\\.]+)\\^([\\d\\.]+)")
.matcher (expression.toString());
while (m.find()) {
Double d1 = Double.parseDouble(m.group(1));
Double d2 = Double.parseDouble(m.group(2));
Double d3 = Math.pow(d1, d2);
expression.replace(m.start(), m.end(), Double.toString(d3));
m.reset(expression);
}
PS: Многие люди, кажется, думают, основываясь на том, как я задал вопрос, что мой калькулятор - неудачная попытка, так как регулярное выражение не уведет меня слишком далеко. Конечно, я согласен, что это правда, и могут существовать гораздо лучшие алгоритмы. Я просто хочу прояснить, что: -
1) Regex используется только для синтаксического анализа выражений в прямой форме. Я не использую регулярное выражение для всего. Вложенные скобки решаются с помощью рекурсии. Регулярное выражение вступает в игру только на последнем этапе, когда вся работа по обработке выполнена, и остается только простой расчет.
2) У меня калькулятор работает нормально. Он может изящно решать вложенные выражения. Доказательство - 2^3*2/4+1 --> 5.0, sin(cos(1.57) + tan(cos(1.57)) + 1.57) --> 0.9999996829318346, ((3(2log(10))+1)+1)exp(0) --> 8.0
3) Не использует слишком много «костылей». Если вы считаете, что я написал тысячи строк кода, чтобы получить желаемую функциональность. № 200 строк и все. И я не собираюсь сбрасывать свое приложение (которое почти завершено).
Вот ваша проблема: «В моем калькуляторе для вычисления выражения используется регулярное выражение». Регулярные выражения - неподходящий инструмент для этого.
Если вы все еще хотите использовать регулярное выражение, ваша группа захвата должна выглядеть так: (\\d+(\\.\\d+)?(e\\d+)?). И ваше последнее регулярное выражение вроде этого: (\\d+(\\.\\d+)?(e\\d+)?)\\^(\\d+(\\.\\d+)?(e\\d+)?)
Вам не нужен обходной путь. Вам нужно решение, и в настоящее время вы используете совершенно неправильную технологию, как заявляет @StephenC. Регулярные выражения не могут обрабатывать приоритет операторов. Решение состоит не в том, чтобы устанавливать обходной путь и иметь часть программного обеспечения на тысяче костылей. Это использование правильной технологии. Поищите «синтаксический анализатор выражения рекурсивного спуска» или алгоритм маневрового двора Дейкстры.
Хорошо, я считаю, что у меня нехватка опыта, что регулярное выражение не подходит для этой конструкции, но вместо того, чтобы издеваться над мной за использование регулярного выражения, я был бы благодарен, если бы вы могли предоставить мне оправдание того, почему регулярное выражение не подходит не привожу это в качестве примера) и что именно делают другие алгоритмы, что делает их лучше. Я настаиваю, потому что мой калькулятор работает нормально, верите вы или нет. Он может обрабатывать сложные вложенные вычисления (не все основано на регулярных выражениях), а также поддерживает математику, такую как sin, cos и т. д.
@Lino, который выглядит многообещающим. Я бы попробовал.
@EJP имейте в виду, что он хорошо обрабатывает пример приоритета операторов (включая скобки) - 2 + 3 / 1.5 * 4 ^ 2 красиво возвращает 34.0
«Тем, кто голосует против, всегда указывайте, почему вы считаете этот вопрос непригодным для этого сайта. Это помогает мне научиться задавать правильный вопрос» - я не голосовал, но я думаю, что сообщение с минимальный воспроизводимый пример и краткое изложение вопроса / проблемы, избегая длинных объяснений, было бы намного яснее.
@ Sarthak123, вам просто нужно изменить, какую группу захвата вы конвертируете в двойную, поскольку я сделал несколько
@ Sarthak123, вы также можете включить отрицательные знаки для основания и экспоненты
@Sarthank Значит, у тебя достаточно костылей для этого. Все, что вам нужно сейчас, - это формальное подтверждение техники. Рекурсивный спуск действует с 1959 года, маневровый - с 1960-61 годов. Неадекватность регулярных выражений для контекстно-свободных грамматик была установлена в 1956 году.
@Lino он работает, и это тоже без особых проблем (только редактирование одной строки)! Спасибо. Вы можете опубликовать это как ответ.
Ответы 2
if you could provide me a justification for why the regex is not a good fit
Истинное регулярное выражение не может правильно анализировать вложенные / сбалансированные скобки. (Хорошо, для этого можно использовать расширенные функции регулярных выражений, но результат чертовски труден для понимания 1.)
Истинное регулярное выражение будет иметь трудности с выражением анализируя с операторами, имеющими другой приоритет. Особенно со скобками. (Я не уверен, что это невозможно, но это определенно сложно.)
После того, как вы использовали свое регулярное выражение (а) для сопоставления выражения, у вас возникнет проблема сортировки «групп», которые вы сопоставили, во что-то, что позволяет вам (правильно) оценить выражение.
Регулярное выражение не может дать никаких объяснений, если ввод синтаксически неверен.
Сложные регулярные выражения часто патологически дороги ... особенно для больших входных строк, которые неверны.
what exactly do the other algorithms have that make them superior.
Правильно написанный или сгенерированный лексер + синтаксический анализ не будет иметь ни одной из перечисленных выше проблем. Вы можете вычислить выражение «на лету» или превратить его в дерево синтаксического анализа, которое можно вычислять многократно; например с разными значениями переменных.
Алгоритм маневровой станции (хотя и имеет более ограниченное применение) также не имеет ни одной из вышеперечисленных проблем.
Речь идет о выборе правильного инструмента для работы. А также о признании того, что регулярные выражения НЕ подходят для каждой работы.
1 - If you want explore the rabbit warren of using regexes to parse nested structures, here is an entrance.
1. Верно. Я даже не использую для этого регулярное выражение. Я рекурсивно решаю вложенные скобки, вручную определяя начальную и конечную позиции скобок (очень просто обнаружить). 2. Может быть? Я тоже этим не пользуюсь. Решить приоритет оператора очень просто. При условии, что все скобки уже были упрощены, сначала проанализируйте все показатели, затем проанализируйте все деления, затем проанализируйте все умножения и так далее. Прекрасно работает, если вы спросите меня. 3. Не знаю, о чем вы говорите, это на самом деле преимущество регулярных выражений (разделение групп) ...
4. Верно. В моем приложении, если возникает ошибка, я согласен с тем, что мой калькулятор не может точно указать, что именно вызвало ошибку (это возможно, но слишком многословно, чтобы писать). .... 5. Я не уверен. Никогда не профилировал мое приложение. Что я знаю, так это то, что он быстрый и точный до степени «отлично».
Я пришел сюда не для обсуждения. Простите. Я просто ответил на вопросы, которые вы задали.
@ Sarthak123 Вы обнаружите, что рекомендованные здесь альтернативные методы работают на несколько порядков быстрее. а также быть более надежным и опираться на шестьдесят с лишним лет теории вычислительной науки. Не делайте шаг назад в темные века.
Согласно вашему комментарию, изменив регулярное выражение из этого:
([\\d\\.]+)\\*([\\d\\.]+)
к этому работает:
(\\d+(\\.\\d+)?(e\\d+)?)\\^(\\d+(\\.\\d+)?(e\\d+)?)
Чтобы объяснить, что я изменил: раньше вам разрешалось вводить числа в формате:
1.5........3.76- и так далее
Чтобы преодолеть это: я добавил необязательный десятичный разряд ((\\.\\d+)?), который позволяет использовать как целые, так и десятичные числа.
Также добавление необязательного научного обозначения ((e\\d+)?) с обеих сторон позволяет записывать числа:
- В виде целых чисел (
2 ^ 5) - В виде десятичных знаков (
2.3 ^ 5.7) - И как научный (
2.345e2 ^ 5e10)
Конечно, можно смешивать все варианты.
Но имейте в виду комментарии под вашим вопросом. Регулярное выражение для небольших битов может быть полезно, но оно может стать довольно неуклюжим, медленным и беспорядочным, чем больше становятся уравнения.
Также, если вы хотите поддерживать отрицательные числа, вы можете добавить дополнительные дефисы перед основаниями и показателями степени:
(-?\\d+(\\.\\d+)?(e-?\\d+)?)\\^(-?\\d+(\\.\\d+)?(e-?\\d+)?)
Если вы разрешите начальные знаки минуса, это помешает распознаванию вычитания.
@rici нет, это плюс. Выражение типа 3--2 оценивается правильно.
@sarthak, это просто, вы можете включить - в следующий номер. Но в 3-2 регулярное выражение по-прежнему будет соответствовать -2, что неверно. Конечно, все это легко разобрать; эффективные и простые алгоритмы хорошо известны, и их можно скопировать из Википедии.
почему регулярное выражение соответствует -2 в 3-2? Регулярное выражение имеет форму <число> <оператор> <число>, оно сначала отдает приоритет оператору сопоставления, а затем отрицательному числу (если присутствует), поэтому 3-2 читается правильно.
@Sarthak: А, я вижу, что там делается. Вы правы, он получит правильный синтаксический анализ отрицательных чисел. Где он (в конечном итоге) потерпит неудачу, так это 3^-(2-3).
@rici да ладно! 3 ^ - (2-3) упрощается до 3 ^ - 1, теперь мой калькулятор не понимает, что делать. Хорошо поймал.
@Sarthak: Это то, что совершенно не проблема, если вы используете стандартный алгоритм. Вы даже не замечаете, что это произошло.
@rici Я согласен и +1 за то, что показал мне реальную разницу между моим и более совершенными алгоритмами. Кстати, есть ли какие-то примеры для тестирования приложения, если оно может обрабатывать все сложные вычисления? Как я чувствую после этого примера, что может быть больше случаев, когда он может потерпеть неудачу. Как вы все это проверяете?
@sarhak: Отличный вопрос, но, к сожалению, я не знаю ни одного. Существуют тысячи калькуляторов, многие из которых содержат ошибки, но каждый из них имеет свой собственный синтаксис, операторы и функции, поэтому трудно понять, как создать универсальный репозиторий тестовых примеров. Одна из причин, по которой я предпочитаю использовать генераторы парсеров на основе контекстно-свободных грамматик, заключается в том, что они позволяют механически генерировать тесты и выполнять статический анализ самой грамматики. (Хорошо написанная грамматика - это также документация; суп из регулярных выражений - нет.)
Тем, кто проголосовал против, всегда указывайте, почему вы сочли этот вопрос неподходящим для этого сайта. Это помогает мне научиться задавать правильные вопросы.