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

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

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

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

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

Средство оценки выражений Codeplex

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

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

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

-Адам

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

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

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

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

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

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

Он называется ParserNG и является бесплатным.

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

    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) один раз при 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 является я.