Умный дизайн математического парсера?

StackOverflow https://stackoverflow.com/questions/114586

  •  02-07-2019
  •  | 
  •  

Вопрос

Каков самый разумный способ создания математического парсера?Я имею в виду функцию, которая принимает математическую строку (например:«2 + 3/2 + (2 * 5)») и возвращает вычисленное значение?Я написал один на VB6 много лет назад, но в итоге он оказался слишком раздутым и не очень портативным (или умным, если уж на то пошло...).Общие идеи, псевдокод или реальный код приветствуются.

Это было полезно?

Решение

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

Другие советы

Я написал несколько сообщений в блоге о разработке математического парсера.Есть общий введение, базовые знания о грамматики, пример реализации, написанный на Ruby и тестирование.Возможно, вам пригодятся эти материалы.

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

В качестве альтернативы вы можете создать настоящий синтаксический анализатор и сгенерировать небольшое дерево синтаксического анализа, которое затем будет использоваться для вычисления выражения.Опять же, это довольно просто для основных выражений.Проверьте codeplex, так как я считаю, что у них там есть математический анализатор.Или просто найдите BNF, который будет включать примеры.Любой веб-сайт, представляющий концепции компилятора, будет включать это в качестве базового примера.

Оценщик выражений Codeplex

Я знаю, что это устарело, но я наткнулся на это, пытаясь разработать калькулятор как часть более крупного приложения, и столкнулся с некоторыми проблемами, используя принятый ответ.Ссылки были ОЧЕНЬ полезны для понимания и решения этой проблемы, и их не следует сбрасывать со счетов.Я писал приложение для Android на Java и для каждого элемента выражения «строка» фактически сохранял строку в ArrayList по мере того, как пользователь вводил ее на клавиатуре.Для преобразования инфикса в постфикс я перебрал каждую строку в ArrayList, а затем оценил вновь организованный постфиксный ArrayList строк.Это было фантастически для небольшого количества операндов/операторов, но более длительные вычисления постоянно отключались, особенно когда выражения начинали вычисляться как нецелые числа.В предоставленной ссылке на Преобразование инфикса в постфикс, он предлагает извлечь стек, если сканируемый элемент является оператором и элемент topStack имеет более высокий приоритет.Я обнаружил, что это почти правильно.Удаление элемента topStack, если его приоритет выше ИЛИ РАВЕН оператору сканирования, наконец, привело к тому, что мои расчеты оказались правильными.Надеюсь, это поможет всем, кто работает над этой проблемой, и спасибо Джастину Поли (и fas?) за предоставление некоторых бесценных ссылок.

Если у вас «всегда включенное» приложение, просто отправьте математическую строку в Google и проанализируйте результат.Простой способ, но не уверен, что это то, что вам нужно, но, я думаю, в некотором смысле умный.

Связанный вопрос Анализатор уравнений (выражений) с приоритетом? также есть хорошая информация о том, как начать с этого.

-Адам

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

ANTLR — очень хороший генератор синтаксического анализатора LL(*).Я очень рекомендую это.

Разработчики всегда хотят иметь чистый подход и пытаются реализовать логику синтаксического анализа с нуля, обычно заканчивая Алгоритм маневровой станции Дейкстры.Результат: код выглядит аккуратно, но, возможно, содержит ошибки.Я разработал такой API, JMEP, это делает все это, но мне потребовались годы, чтобы получить стабильный код.

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

Спустя 11 лет с момента, когда был задан этот вопрос:Если вы не хотите изобретать велосипед, существует множество экзотических математических парсеров.

Есть один, который я написал много лет назад, который поддерживает арифметические операции, решение уравнений, дифференциальное исчисление, интегральное исчисление, базовую статистику, определение функций/формул, построение графиков и т. д.

Это называется ПарсерНГ и это бесплатно.

Вычислить выражение так же просто, как:

    MathExpression expr = new MathExpression("(34+32)-44/(8+9(3+2))-22"); 
    System.out.println("result: " + expr.solve());

    result: 43.16981132075472

Или используя переменные и вычисляя простые выражения:

 MathExpression expr = new MathExpression("r=3;P=2*pi*r;"); 
System.out.println("result: " + expr.getValue("P"));

Или используя функции:

MathExpression expr = new MathExpression("f(x)=39*sin(x^2)+x^3*cos(x);f(3)"); 
System.out.println("result: " + expr.solve());

result: -10.65717648378352

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

MathExpression expr = new MathExpression("f(x)=x^3*ln(x); diff(f,3,1)"); 
System.out.println("result: " + expr.solve());

 result: 38.66253179403897

Что отличает x^3 * ln(x) один раз в точке х=3.Количество раз, которое вы можете дифференцировать, на данный момент равно 1.

или для численного интегрирования:

MathExpression expr = new MathExpression("f(x)=2*x; intg(f,1,3)"); 
System.out.println("result: " + expr.solve());

result: 7.999999999998261... approx: 8

Этот парсер достаточно быстр и имеет множество других функций.

Была завершена работа по портированию его на Swift через привязку к Objective C, и мы использовали его в графических приложениях среди других итеративных вариантов использования.

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ:Автор ParserNG — я.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top